ナイトのツアーグラフを実装し、それをさまざまな検索アルゴリズムで使用する

Question

ナイトツアーを実装し、bfs、dfs、a *などのさまざまな検索アルゴリズムで実行したいと考えています。ユーザーがチェスボード上の場所を選択してから、問題は選択した後、最初の場所から2番目の場所までのすべての可能な移動のように、全体のグラフを作成するか、それを段階的に実行し、アルゴリズムに従って、検索の最初のレベルと次のレベルの子供の子供？私は私の質問がはっきりと私の英語のために申し訳ありませんでした願っています。

Answer 1

各反復では、宛先が到着するまでノードがキューからポップされます。繰り返し移動は、リストを使用して以前の履歴移動を記録することによって放棄されます。実装を簡素化するために、毎回、現在の移動履歴配列もキューにプッシュされます。これは明らかに、最初に発見された経路が最短経路であることを保証するBFS（幅優先探索）アルゴリズムです。

---

あなたはチェス盤を検索しません。配置のスペースを検索：

初期状態：なし騎士が配置されていない

有効な移動：場所

目標の状態任意の空いタイル上の騎士：すべてのタイルは、いずれかの占有または攻撃され

基本アルゴリズム（状態空間のBFS）：

BFSキューに初期状態をプッシュします。 キューに何かがあるときに、 キューから1つの状態を削除します。すべての空きタイルについて ： 現在の状態のコピーを作成します。 そのタイルにナイトを1つ追加します。 新しい状態がキューに存在しない場合： 新しい状態がゴール状態の場合、終了します。 それ以外の場合はキューに追加します。

Answer 2

私が問題を正しく理解した場合、実行可能な状態を生成するという観点からゲームツリーを明示的に表現するのではなく、ボードのインスタンスを保持し、可能なすべてを生成する関数を使って探索を再帰的に実装する移動を実行し、移動を元に戻す。そうすることによって、ゲームツリーの検査された部分は、最後の移動を元に戻し、現在の再帰呼び出しから戻ることによってバックトラッキングステップが実施される間に、コールスタックを使用して暗黙的に表される。