問題タブ [sliding-tile-puzzle]

8 パズルの最適な解を見つけるために、幅優先探索を行っています。同じパズルの動きで同じ関数呼び出しを実行しないようにするために、ツリー構造を作成しました。パズルを保存するのではなく、パズルの 9 つのスロットの 9 つの値の経路をツリーに作成するだけです。コードは次のとおりです。

私はこれを広範に使用し、再帰を使用して深さを制限した検索でも使用しました。この構造を使用して、これらのアルゴリズムのすべての可能なソリューションを格納するには、長い時間がかかります。割り当てに時間がかかることと関係があると思います。それが理由ですか？メモリの塊を作成しようと考えていたので、プログラムに任せるのではなく、そのメモリのアドレスをノードに割り当てました。それが最善の解決策でしょうか?どうすればよいでしょうか? (私はこれを複数の検索で使用しましたが、すべて実行に時間がかかるため、そのコードは含めていません。)

私の AI クラスでは、8 マス パズルのソルバーを作成するように割り当てられました。私のプログラムは、解決策を達成するための動きがほとんどない場合 (最大 9 つ) で機能しますが、それを超えると無限再帰が発生します。同じ2つの状態の繰り返しを防ぐために以前の状態を保存しているので、何が問題なのかわかりません。あなたの一人が私を助けることができますか？ありがとう。

解決済み: コードに問題はありません。Python の最大呼び出しスタック サイズが小さすぎます。私はそれを反復的にしました、そしてそれはうまくいきます。中心的な問題は、プログラムが指数関数的な時間の複雑さを持っていることであり、('while True:' を使用して) 反復処理を行うと、その問題が解決されます。

私はパズル ゲームを作成しており、8 個のピース​​を 3x3 グリッドにランダムに配置していますが、すべての画像が HashMap に追加されているわけではありません。誰かが理由を見ますか？

パズルを整理するために使用するコードは次のとおりです。

これは、ロード時にコンソールに出力されるものです。

puzzle.size()8 ポイントがリストされているため、ランダムな BufferedImage を使用して 8 ポイントが追加されpuzzle、その後削除されるため、8 を返さない理由がわかりません。同じ画像を 2 回選択することはありません。

編集：私はこれを解決しました。アセットが正しく読み込まれませんでした。お時間を無駄にして申し訳ありません。

これはおそらく非常に基本的なことですが、何時間も試してみましたが、まだ自分でこれを理解することはできません. だから今、私は AI クラスの 8 パズル ゲームをやっています。「032 145 678」などの一連の数字を入力する必要があり、これを 3x3 マトリックスに格納するだけでよく、0 は基本的に空のブロックを表します。したがって、そのユーザー入力を取得して、{{032},{145},{678}} のように 3x3 行列として格納する必要があります。

編集：

だから私は 8puzzle と目標状態である配列の初期状態を持っています

斜めに行かずに、初期状態と目標状態の間の距離を把握しようとしています。誰でも私を助けることができますか？(注: この配列を 2 次元配列に変更してもかまいません。これにより物事が単純になり、すべての距離を知りたいだけです)。

私がオンラインで見るところはどこでも、昇順の goalPuzzle 状態を期待しています。これは私の問題には当てはまりません。

したがって、現在の状態が与えられるこの 3x3 ゲームに取り組んでいます。たとえば、次のようになります。

1 5 6

3 7 b

2 8 4

そして、次の目標状態に到達したいと考えています。

b 1 2

3 4 5

6 7 8

そのため、以下に投稿したコードに他のすべてのメソッドを記述しました。私が今抱えている問題は、実際の A* 検索にあります。私は 2 つのヒューリスティックを使用したいと考えています。1 つは間違った場所にあるピースの数をチェックするものであり (たとえば、ヒューリスティック関数は、現在の状態で H=8 ピースが間違った場所にあることを示します)、もう 1 つはどのくらい離れているかを計算するヒューリスティックです。ピースの合計は (つまり、私の現在の状態では、ピース 1 は 1 移動分、ピース 2 は 3 移動分、など、すべての合計が H 値になります) です。gameBoardそのため、文字列の配列に記録しています。

だから今、私の実際の問題に。以下に示すように、私の A* 以外のすべてが現在機能しています。

まず、現在の状態と目標の状態を比較できるようにsetFinalGoalState()、変数を作成する whichを呼び出します。finalGoalState

次に、各ノードが G 値 (G はツリー内の距離)、H 値、親への参照、および現在の状態を持つ s の であるpriorityQueueべきa を作成します。ArrayListNode

最初にイニシャルを呼び出してhuesticOneHValue()、最初の状態の H 値を取得します。次に、"h1" のステートメントを実行しますif(後で別の方法を追加すると述べたように、これは最初のヒューリスティックな方法です)。Root次に、ツリー内の最初のノードとなる初期ノードを作成し、これを優先キューに追加する必要があります。

次に、優先キューを通過する必要があります。現在のノードを の最初の要素として取得しpriorityQueue、キューから削除します。現在のノードとgameBoard同じ状態としてmy actual を設定します。gameBoard次にArrayList、可能な移動の を作成します (これは を呼び出しisValidMoves()、実際に上下左右に移動できるかどうかを確認し、それをリストに入れます)。次に、可能な移動のサイズを実行する for ループを作成し、move()メソッドを呼び出して実際の移動を行います (現在の状態で b を上に移動できるため、最初の呼び出しでint i = 0は move "up" が呼び出されます)。次に、をNode含む子を作成する必要がありますgValue私がどこにいるのか（1に等しいはずです）、新しいH値（場合によってはこれは同じままかもしれませんが、H値を下げる方向に取り組んでいるはずです）、その親（私はそうあるべきだと思いますcurrentNodeか？）、そしての状態currentNode(ボードの外観)。

次に、次の for ループ チェックで、優先度キューのどこに配置する必要があるかが確認されます。値が小さいノードg+hはキューの先頭に配置する必要があります。最初にそれらをチェックして、目標状態に到達したかどうかを確認する必要があるためです。そのため、キューが空の場合は初期条件を設定して先頭に追加し、そうでない場合はpriorityQueueatが子よりもj大きいかどうかを確認し、大きい場合は子が(および他のすべてg+hのインデックスに追加されます)j最後に、すべての移動が完了した後、priorityQueueフロント ノードの状態が目標状態と等しいかどうかを確認し、そうでない場合は while ループの先頭に戻り、再び実行されます。

最終的には、ノードで何かを台無しにしていると思います。デバッグを実行すると、子を作成するたびに、親ノードの状態が子の状態に更新されることがわかりました。これは、子が親の特定の動き (上、下、左、または右）。ノードクラスを作成するか、ノードを作成してキューに追加する方法を台無しにしたと思います。priorityQueue子供をatに追加しようとすると、 indexOutOfBounds も取得します

私のコードの残りの部分は以下の通りです：

EightPuzzle クラス

ノード クラス

Java で 8 パズル問題の深さ優先検索 (再帰) を実装しました。

反復的な深化深度検索に変換するために何を変更する必要があるのか​​ わかりません。深さはラウンドごとに増加するため、深さに制限がないことはわかっています。これを試しました：

必要なIDSに変更する方法を知っている人はいますか? 前もって感謝します！

8 パズルのマンハッタン距離で A スター アルゴリズムを実装しています。【解決策はらせん状】

場合によっては、A から B に移動するのに、B から A に移動するのと同じ数のステップが必要ではありません。

これは、同じコストの場合、オープンリストで同じ状態を選択しないため、同じノードを展開しないためだと思います。

から

マンハッタン距離を使用すると、どちらも同じ値になります。すべてのパスを同じ値で探索する必要がありますか? または、ある種のタイブレーカーを持つようにヒューリスティックを変更する必要がありますか?

ここにコードの関連部分があります