8 パズルの問題があり、空のタイルが 0 とマークされているとします。目標状態は次のとおりです。
- 1 2 3
- 4 5 6
- 7 8 0
初期状態は次のとおりです。
- 0 1 3
- 8 2 4
- 7 6 5
... 私の質問は、A* ツリーの子がその先祖と同じ状態を「コピー」または同じ状態にすることは可能ですか? または、「f(n) = g(h) + h(n)」[ここで、g(h) = 行われた移動の数... h(n) = 各タイルのマンハッタン距離の合計] は、すでにこれを不可能にし、したがって、これについて心配する必要はありませんか?..たとえば、初期状態から:
- 0 1 3
- 8 2 4
- 7 6 5
次に、次の状態が発生するため、A* ツリーにさらに子ノードが作成されます
(アクション: アップ)
- 8 1 3
- 0 2 4
- 7 6 5
アクション: 左
- 8 1 3
- 2 0 4
- 7 6 5
アクション: ダウン
- 8 0 3
- 2 1 4
- 7 6 5
アクション: 右
- 0 8 3
- 2 1 4
- 7 6 5
アクション: アップ
- 2 8 3
- 0 1 4
- 7 6 5
...その後、アクション: 左、下、右、上、左、下、右が発生します...したがって、状態は初期状態に戻ります。
- 0 1 3
- 8 2 4
- 7 6 5
これは 8 パズルの A* 検索で可能ですか? それとも f(n) がこの問題を解決してくれるでしょうか? 答えてくれる人に感謝します。助けていただければ幸いです。