0

反復深化検索を使用してラッシュアワーの問題を解決する必要があります。すべての移動に対して新しいノードを生成しています。すべてを計算するのに時間がかかりすぎることを除いて、すべてが正常に機能します。これは、重複したノードを生成しているためです。重複をチェックする方法はありますか？

最初にルートから開始し、次にすべての車を移動できるかどうかをチェックする方法があります。はいの場合、現在のノードから新しいノードが作成されますが、有効な移動がある1台の車が新しい座標を持つ新しい車に置き換えられます。

問題は、アルゴリズムが深くなるほど、重複する動きが増えることです。

車を交換しないようにしたのですが、ルートノードで使用したのと同じコレクションを使用しましたが、車は一方向にしか動いていませんでした。

どういうわけか車のコレクションを結ぶ必要があると思いますが、どうすればいいのかわかりません。

コード

複製をやめる方法はありますか？

オフトピック：私はC＃を初めて使用します（いくつかのチュートリアルを読んでから2日間使用しています）。それで、私が間違っていること、またはすべきでないことを教えてください。

4

1 に答える 1

1

反復深化に固執したい場合、最も簡単な解決策はハッシュテーブルを作成することかもしれません。次に、新しいノードごとに行う必要があるのは、次のようなものです。

NewNode = GenerateNextNode
if not InHashTable(NewNode) then
  AddToHashTable(NewNode)
  Process(NewNode)

あるいは、RushHourで可能な位置（ノード）の数はかなり少なく（標準のボード寸法を使用していると仮定）、すべての可能な（そして不可能な！）ボードをかなり簡単に生成することができます。次に、反復深化ではなく、「ソリューション」状態から開始して、開始状態に到達するまで逆方向に作業します（すべての可能な「親」状態をチェックします）。可能な状態のテーブルで作業することにより、重複を生成することはありません。また、一度アクセスすると各状態にタグを付けることで、状態に再度アクセスすることはありません。

于 2013-03-24T22:47:49.730 に答える