問題タブ [sliding-tile-puzzle]

何らかの理由で、distance機能を動作させることができません。誰かが私が間違っていることを説明してもらえますか?

主な機能：

マンハッタン距離計算！

8 つのパズル状態の線形競合を見つける必要があります。状態は int[8] で表され、目標状態は {1,2,3,4,5,6,7,8,0} です。線形競合は、その行にあるはずの 2 つのタイルが逆になっている場合に発生します。たとえば、目標状態で最初の行が 1,2,3 である場合、その状態で最初の行が 2,1,3 の場合、それはタイル 2 と 1 によって行われた 1 つの線形競合です。

私のコードは機能しますが、長すぎて厄介です。ここにあります：

より短く、より不器用に行う方法は誰でも知っています。このような方法を続けていると、私のコードは非常に読みにくくなります。

私は 8 パズル ソルバーを書こうとしていますが、まだできませんでした: マンハッタンの優先度関数を使用していますが、優先度の値が等しい場合、子孫ボードの配置をどのように選択するのか疑問に思います。

例えば：

これは最初のボード配置です:

およびその子孫の取締役会の取り決め:

マンハッタン距離 + 移動数 = 10

マンハッタン距離 + 移動数 = 12

マンハッタン距離 + 移動数 = 10

プログラムはどのボード配置を選択する必要がありますか? IまたはIII???

シミュレーテッド アニーリング アルゴリズムで解くための 8 パズル問題を定式化するにはどうすればよいですか?

いろいろ考えましたが、解決策が見つかりませんでした!!

ブロックを順番にスタックに配置するために、最終的に各ノード (要素 0 ～ 8 の int[]) をパスに格納する 8 パズル ソルバーを実行しています。int[,] を表示する WPF GUI があります。

GUI に最初のボードが表示され、[解決] をクリックすると、最終的な (順序どおりの) ボードが正しく表示されます。私がやりたいことは、ボード上の各ノードをしばらく表示し、最終的に順序どおりのボードに到達することです。Thread.Sleep を使用すると、GUI は最終ノードを表示する前に設定された時間だけ一時停止します。このコードが各ノードで 500ms ごとにボードを表示しない理由について何か考えはありますか?

参考までに、ノードの Console.Write からの出力例を次に示します。
4,2,3,6,1,0,7,5,8
4,2,0,6,1,3,7,5,8
4 ,0,2,6,1,3,7,5,8
4,1,2,6,0,3,7,5,8
4,1,2,0,6,3,7,5,8
0,1,2,4,6,3,7,5,8
1,0,2,4,6,3,7,5,8
1,2,0,4,6,3,7,5, 8
1,2,3,4,6,0,7,5,8
1,2,3,4,0,6,7,5,8
1,2,3,4,5,6,7,0 ,8
1,2,3,4,5,6,7,8,0

この例http://ai.ia.agh.edu.pl/wiki/pl:prolog:pllib:sliding_puzzleの 8 パズル問題でマンハッタン距離を計算する方法を誰か説明してもらえますか?

これを計算する方法：

a(0,0)。a(1,0)。(2,1)。(3,2)。(4,3)。(5,4)。(6,3)。(7,2)。(8,1)。b(0,0)。b(1,1)。b(2,0)。b(3,1)。b(4,2)。b(5,3)。b(6,2)。b(7,3)。b(8,2)。c(0,0)。c(1,2)。c(2,1)。c(3,0)。c(4,1)。c(5,2)。c(6,3)。c(7,4)。c(8,3)。d(0,0)。d(1,1)。d(2,2)。d(3,3)。d(4,2)。d(5,3)。d(6,2)。d(7,2)。d(8,0)。e(0,0)。e(1,2)。e(2,1)。e(3,2)。e(4,1)。e(5,2)。e(6,1)。e(7,2)。e(8,1)。f(0,0)。f(1,3)。f(2,2)。f(3,1)。f(4,0)。f(5,1)。f(6,2)。f(7,3)。f(8,2)。g(0,0)。g(1,2)。g(2,3)。g(3,4)。g(4,3)。g(5,2)。g(6,2)。g(7,0)。g(8,1)。h(0,0)。h(1,3)。h(2,3)。h(3,3)。h(4,2)。h(5,1)。h(6,0)。h(7,1)。h(8,2)。
i(0,0)。i(1,4)。i(2,3)。i(3,2)。i(4,1)。i(5,0)。i(6,1)。i(7,2)。i(8,3)。

このコードで？

ノードの有効なネイバーを計算しようとしています

配列には次のような要素が含まれています[2,8,3,0,1,4,7,6,5]

マトリックス：

8パズルロジックに似ています。上記の行列では、0 を 2 または 1 または 7 と交換できます。-1、+1、-3、+3 で試しました。ただし、0 は 3 と交換できないため、-1 や +1 は使用できません。また、配列内の位置を更新する必要があります。これを達成するためのロジックは何ですか。

コード (3x3 マトリックス) について質問があります。2 つの方法 (水平または循環) で勝つ必要があります。

また

「0」は空白

今のところ、私は 1 行にコメントしています (そして、一度に 1 つの方法でしか勝つことができません)。私の質問は、説明されている 2 つの方法で勝つために何を実装できますか? どうもありがとうございます。

これらのヒューリスティックで A* 検索を使用して 8 パズルを解こうとしています: - h1: 間違って配置されたタイルの数 - h2: マンハッタンの合計距離 - h3: 上記の合計

移動タイルは 0 として知られています。

私の目標は、これらのセットを解決することです:

と

私が抱えている問題は、現在の A* の実装では、最初の問題は解決できますが、2 番目の問題は解決できないということです。

だから、私のA *コードの何が問題なのかを理解するのを手伝ってください：

int[,] current = コンソールから文字列 (412583706) として入力され、パズルを表す 2D int に変換されます。正しい場合も同じで、0 は右下隅にあります。

最初の問題は 7 つのステップで解決されます。私がテストした別のプログラムによると、次の問題は 32 ステップで解決できます。

私のプログラムが他のプログラムと異なる点は、最初の 4 つのステップが同じで、他のプログラムが別のルートを選択することです。私のプログラムが最も安いノードを選択したように見えるので、何が悪いのか理解できません。

経路探索アルゴリズムは初めてなので解いてみたいと思います。私はこの問題を 3 日間抱えていて、多くの解決策を試したような気がしますが、どれもうまくいきません T_T

よろしくお願いします。

----編集----- 追加コード:

---------編集 2-------- 私のコードを少し変更しましたが、パズルのセットアップ/ノードとそのヒューリスティックはすべて PuzzleNode オブジェクトにあります。

// 現在のノードから次に可能な移動のリストを返します。// closedNodeList 内で見つかった移動は含まれません。

-----------編集3----------------

ところで、A* のさまざまなステップの実装が正しく理解されているかどうかを尋ねたいと思います。現時点では、私のプログラムの A* 検索はこれを行います:

1. 初期リスト OPEN および CLOSED を作成し、開始ノードを OPEN に追加します
2. ループを開始し、OPEN から最も安価なノードを削除し、CLOSED に追加します *最も安価なノードは、そのマンハッタン距離値によって決定されます。
3. ノードを使用して隣人/子供/次の動きを見つけ、これらを SUCCESSOR リストに追加します。
4. SUCCESSOR リストを探索し、それらのいずれかに目標状態が含まれているかどうかを確認し、そうでない場合は OPEN リストに追加します
5. 2 ～ 4 を繰り返し、リスト内のノードを調べます。

Q1 でこれらの手順を試すと、7 つの手順で解決策が得られます。これは正しいです。これも手探りで発見。しかし、第 2 四半期では、OPEN リストが空になり、他に探索するものがなくなるまで続きます。それで、私は何が欠けていますか？