チェス盤の2点間の最短経路を見つけるにはどうすればよいですか？

馬（または騎士）などと呼ばれる特定のピースの動きのルールが与えられている場合、現在のピースとチェス盤の別のポイントとの間の最短経路はどのように計算されますか？チェス盤の2点間の最短経路を見つけるにはどうすればよいですか？

私はコードを探しているのではなく、考えています。私はアルゴリズムを探しています。

ありがとうございました。

2016-10-24 Water Cooler v2

cs.stackexchange.comでこれを尋ねるか、追加の詳細を提供することを検討することができます。既存の作品だけを扱うか、任意の動きで新しい作品を定義できますか？特定の場所に到達できない場合はどうすれば対応できますか？（例えば、黒のビショップを白い目的地に近づけようとしている）グリッドの大きさの境界は何ですか？ – ilim

ありがとうございます。良い点。私は私の頭の中に答えを持っていますが、私はこれらの詳細を記入するために質問を編集します。 –

パス検索アルゴリズムとしてBFSを使用できます。ここでは、各ステップで次のストップがそのピースのすべての可能な移動になります。

出典

2016-10-24 10:36:24

しかし、DFSは最短パスを検出しません。私は彼がBFSだけを必要とすると思う –

DFSのビットの変更は問題を解決するだろうが、それはもっと混乱を招くだろうと思う。コメントありがとう。 –

A *（ヒューリスティックスを伴うDFS）は単一の最短パスを返します。しかし、私は騎士のために可能な限り最短のパスを生成するときに2つの出発点BFSを使用しました（CSコースの割り当て）。ランタイムが目立つようになる前に、UIの可能なすべてのルートを一覧表示するためにメモリが不足しているため、BFSは十分に高速でした（1Mの最短ルートに近い20の正方形の距離が生成されます）。 –

チェス盤の2点間の最短経路を見つけるにはどうすればよいですか？

答えて

関連する問題