反復深化アルゴリズムによって「ラッシュアワーのパズル」を解かなければなりません。ここで、stackoverflow とインターネットで多くのトピックを読みました。反復深化アルゴリズムについて理解できたと思います。基本的には、ツリーを深く掘り下げて解決策を見つけようとするだけです。
パズルからグラフまたはツリーを作成する必要があると考えましたが、方法がわかりません。また、ツリーがあれば、何かが有効な移動か最終状態かをどのように判断できますか?
結節は可能な手であり、エッジは一手で到達できる結節の間であるという回答がありました。私はこれを想像することができますが、どういうわけか、これがどのように役立つか、またはより良い方法で問題を解決できるかを理解するのに苦労しています.
助けてください。完全な解決策やコード サンプルを求めているわけではありません。問題の簡単な説明が必要なだけです。
深化アルゴリズムを使用する必要があるのには理由があります。各車に A、B、C、D という名前を付けたとします。ツリーのルート ノードは、ボードの初期状態です。次に、車 A を移動します。ツリーのノードを 1 つ下ります。車Aを後ろに移動します。あなたは初期状態にいますが、ここにたどり着くまでに 2 つの移動を行ったので、ツリーの 2 つ下のノードにいます。何度も繰り返します。最終状態に到達することはありません。
ツリーのルート ノードは、ボードの初期状態です。そのノードを指定して、考えられるすべての有効な移動に対して子ノードを追加します。したがって、各子ノードは、1 回の移動後に最初のツリーがどのように見えるかになります。ここで、これらの子ノードのそれぞれについて、同じことを行います。各ノードが元の子ノードから 1 つ移動する子ノードを作成します。
最終的に、パズルの解決策にたどり着きます。その場合は、ルート ノードからソリューションの子ノードへの移動を出力して終了します。このアルゴリズムにより、移動回数が最も少ないソリューションを確実に見つけることができます。