4

8パズルのゲームソルバーをC++でコーディングしようとしていますが、それを実行しているときに多くの問題が発生します。プログラムは現在機能していますが、パズルを解くには手順が多すぎます。つまり、最適なソリューションを見つけることができる場合もあれば、それを解決するのに400ステップもかかる場合もあります。私の主な疑問は次のとおりです。私がこの図を持っていると想像してください（これは単なるドラフトです）：

ここに画像の説明を入力してください

ヒューリスティック関数としてマンハッタン距離を使用しています。最初のステップの後、f（n）= 5の2つの状態があるので、ツリーを展開しました。展開した後でも、f（n）=2の2つの状態があります。ここに私の疑問があります。一意の最低f（n）が得られるまで、ツリーを拡張する必要がありますか？

前もって感謝します！

4

2 に答える 2

3

それでもツリーを拡張する必要がありますか

このパズルを貪欲に解決することはできません。ヒューリスティックな値が低いブランチを常に取得しても、毎回最終的な解決策にたどり着くわけではありません。したがって、バックトラックのために他の状態を維持する必要があります。単純なBFSであろうとヒューリスティックベースのA*であろうと、それらを拡張する順序はあなた次第です。

于 2013-03-26T21:04:15.683 に答える
1

ここでは、A*アルゴリズムを使用して初期状態から目標状態までの最短経路を見つける処理アプレットを見つけることができます。アプレットのコードは無料で入手できます。

于 2013-04-03T09:49:59.253 に答える