0

8パズルの小さいバージョンである3パズル（3ブロックと空白）を解くプログラムを作っています。黒に隣接するブロックを空白に移動してツリーを構築しようとしています。したがって、すべての状態で2つの状態を指定できます（分岐係数= 2）。私は幅優先探索を使用してツリーを解決していますが、ツリーをトラバースするには、最初に作成（拡張）する必要があります。永遠にツリーを拡張し続けることはできないので、ツリーを特定の深さまで拡張してからトラバースするための何らかの手段が必要です。したがって、トラバーサルが最後のレベルに達すると、expand（）関数が呼び出されてさらに展開されます。誰かがこのアイデアを実行するための明確なメソッドまたはアルゴリズムを教えてもらえますか？または、私の問題を解決する別の方法はありますか？

4

1 に答える 1

1

setすべての異なるボード状態を保持します。2 つのボードの状態は、いずれかの位置に異なるピース (空白はピースとして数えます) がある場合、異なります。一貫した順序ですべての数字を連結することにより、状態を表す文字列を作成できます。ほとんどの言語/ライブラリは文字列のセットを直接サポートしています。

未訪問のボード状態のみを展開する必要があります。初めて州を訪れるときはいつでも、それを「訪問した州」に追加する必要がありますset。状態を展開する前に、それが既に存在するかどうかを確認してください。

完全なアルゴリズム (一般的な幅優先、重複のない検索) は次のとおりです。

place initial state into "pending" (a queue)
place initial state into "visited" (a set)
while "pending" is not empty,
   extract its first state, called "next"
   if it is not present in "visited",
      if it is the goal, report success, ending the algorithm
      otherwise, add all its children at the end of "pending"    
if you reach this point, there is no way to reach a goal state from a start state
于 2012-09-10T10:42:40.063 に答える