学校の課題で、ラッシュアワー ゲームのソルバーを作成する必要があります。ラッシュ アワーに慣れていない場合は、次のリンクを確認してください: http://www.puzzles.com/products/rushhour.htm
このソルバーでは、A* 検索アルゴリズムを使用する必要があります。インターネットを少し調べたところ、アルゴリズムがどのように機能するかをよく理解できたと思います..ソルバーでそれを実装する方法が本当にわかりません。 . また、車のグリッドをどのように構築する必要があるか.. 誰かがこれに関するヒント/ヘルプを教えてもらえますか? 完全な解決策ではありません..
車のグリッドを表すには、各セルが整数でマークされているセルの長方形配列を使用します。0 は「空」を示し、各車には特定の番号があるため、グリッド内のさまざまな車が現れます。同じ番号の連続したセルとして自分自身。
この時点で、特定のグリッドから可能なすべての「移動」を返す関数を記述できるはずです。ここで、「移動」は、あるグリッド状態から別のグリッド状態への遷移です。おそらくその必要はありません。それよりも動きのより良い表現をエンコードします。
A* を実装するには、どの動きが最初に試すべきかがわかるように、動きの見栄えを把握する単純なヒューリスティックが必要です。最初は、ターゲットの車をゴールに近づけるか、スペースをターゲットの車の前に近づける動きがより良い候補の動きになる可能性があることをお勧めします. Will A がコメントで言ったように、1000x1000 の Rush Hour ボードを解決していない限り、これはおそらく大したことではありません。
それは私が考えることができるすべてのトリッキーな部分です。
mquander または Will がすでに指摘しているように、A* アルゴリズムは問題に対して少し過剰適合している可能性があります。
問題を解決するために他のアルゴリズムを使用できるヒントをいくつか紹介します。これらのアルゴリズムがどのように機能するかについては説明しません。インターネットで多くの優れた説明を見つけることができるからです。ただし、ご不明な点がございましたら、お気軽にお問い合わせください。
「情報に基づかない検索」の種類に属するいくつかのアルゴリズムを使用できます。たとえば、幅優先検索、深層優先検索、均一コスト検索、深さ制限検索、反復深化検索などがあります。幅優先検索または均一コスト検索を使用する場合、これらのアルゴリズムは指数関数的な空間の複雑さを持っているため、使用可能なメモリ空間の問題に対処する必要がある場合があります (また、検索空間全体をメモリに保持する必要があります)。したがって、ディープ ファースト検索 (空間複雑度 O(b*m)) を使用すると、最初にアクセスするツリーの左側の部分が解を含まない場合は省略できるため、よりメモリに優しくなります。深さ制限検索と反復深化検索はほとんど同じですが、反復深化検索では、ツリーの検索レベルを繰り返し増加させます。
時間の複雑さを比較すると (b = ツリーの分岐係数、m = ツリーの最大深さ、l = 深さレベル制限、d = ソリューションの深さ):
幅優先: b^(d+1)
一律料金：b^?
深拳:b^m
深さ制限: b^l if (l>d)
反復深化: b^d
したがって、反復的な深化または幅優先検索が非常にうまく機能することがわかります。深さ制限検索の問題は、ソリューションが検索レベルよりも深い場所にある場合、ソリューションが見つからないことです。
次に、ベストファースト検索、欲張り検索、a*、ヒル クライミング、シミュレーテッド アニーリングなどのいわゆる「インフォームド検索」があります。つまり、ベストファースト探索では、「望ましさ」の推定値として各ノードの評価関数を使用します。貪欲探索の目的は、目標に近づくノードを拡張することです。ヒル クライミングとシミュレーテッド アニーリングは、 Stuart Russell は、ヒル クライミングを次のように説明しています (私はとても気に入っています...): ヒル クライミングのアルゴリズムは、記憶喪失で濃い霧の中でエベレストに登るようなものです。それは単純に、値が増加する方向に継続的に移動するループです。したがって、評価関数が増加する方向に「歩く」だけです。
実装が非常に簡単なので、統一された検索アルゴリズムの1つを使用します（ツリーをプログラムして正しくトラバースするだけです）。優れた評価関数があれば、通常、情報に基づいた検索のパフォーマンスが向上します...お役に立てば幸いです...