2

まず、stackoverflowやその他のインターネット検索で見つけたすべてのスレッドを読みました。私はさまざまな側面について学びましたが、それは私が必要としているものではありません。

サイズが8X8タイル以下のラッシュアワーパズルを解く必要があります。

タイトルで述べたように、A *を使用したいので、ヒューリスティックとして使用します。赤い車（取り出す必要がある車）のパスをブロックしている車の数を減らすか、同じままにする必要があります。

ラッシュアワーのBFSソリューションを読みました。

どのように始めればいいのか、どのような手順を踏むべきかわかりません。

誰かが説明を必要とする場合のために、ここにタスクへのリンクがあります：

http://www.cs.princeton.edu/courses/archive/fall04/cos402/assignments/rushhour/index.html

これまでのところ（特に多遺伝子潤滑剤の回答から）、初期段階と「成功」段階を含む段階のグラフを生成し、A *アルゴリズムを使用して初期から最終までの最小経路を決定する必要がありますか？

すべての可能な（有効な）動きを生成するためにバックトラッキング関数を作成する必要がありますか？

前に述べたように、実装に問題があるのではなく、実行する必要のある手順の概要を説明するための支援が必要です。

編集：可能なすべての動きを生成してグラフノードに変換する必要がありますか？それは時間がかかりませんか？10秒以内に8X8パズルを解く必要があります

4

1 に答える 1

2

A*はグラフを検索するためのアルゴリズムです。グラフはノードとエッジで構成されます。したがって、問題をグラフとして表す必要があります。

パズルの可能な各状態をノードと呼ぶことができます。2つのノードは、1回の移動で互いに到達できる場合、それらの間にエッジがあります。

ここで、開始ノードと終了ノードが必要です。 どのパズル状態が開始ノードと終了ノードを表しますか？

最後に、A *にはもう1つ必要なものがあります。それは、許容距離ヒューリスティックです。パズルが完了するまでに必要な移動数の推測です。この推測の唯一の制限は、実際の移動数よりも少なくなければならないということです。したがって、実際に私たちが探しているのは最小限界です。ヒューリスティックを0に設定するとこれは満たされますが、より適切な最小範囲を考え出すことができれば、アルゴリズムはより高速に実行されます。 パズルを完了するために必要な移動回数の最小制限を考え出すことができますか？

于 2012-08-21T19:56:52.697 に答える