問題タブ [sliding-tile-puzzle]

私はプロジェクトとして私たちから要求された 8 パズル ソルバー -ベスト ファースト サーチ + ハミング距離(タイルの位置ずれ) ヒューリスティックを使用する - に取り組んでいます。

最初に、ヘッダー ファイルで次のように分離された cpp ファイルでStat Struct を定義しました。

次は main.cpp ファイルです:

次のようなサンプル入力を使用してプログラムを実行すると、次のようになります。

それはパズルを解決し、すべてが良いです.しかし、他のすべての入力を試してみると、それらのパズルの解決策があるという事実にもかかわらず、目標に到達する前にオープンセットが空になりました.

編集: オープン セットに入った統計を確認しようとしましたが、そうではなかったので、以下の入力をサンプルとして使用し、得たもの:

オープンに入力された統計:

パズルを解くために必要な手順はどれですか。

クローズドで見つからず、オープンにならなかった統計:

したがって、Open セットは、上記の統計が Open に存在し、それらの入力を拒否すると述べていますが、Open にはそのような統計はなく、それらの状態のヒューリスティック値は Open(4,4,5,5,5,5) で異なります。その他(6,6,5,7)。

オープンがそれらの統計を既に存在するかのように入力することを拒否する理由を誰か教えてください. 前もって感謝します。

私はこの問題を RNG を使ってブルート フォースで解決することができました。作業グリッドが 3x3 であっても、最適なソリューションを見つけるのに約 4 ～ 5 秒かかります。

ブルートフォースなしでブルートフォースが見つけたのと同じ動きを生成できるようにする方法を知りたいです。

2 つの例とブルート フォースで見つかった解決策をリストします。ソリューションを分析して、なぜそれらが選択されたのかを調べようとしましたが、何もわかりません。

このゲームは、(左から右) と (右から左) の両方向に循環回転を使用して動作します。

左から右への循環回転はこれを行います
If [a, b, c] then [b, c, a]
右から左への循環回転はこれを行います
If [a, b, c] then [c, a, b]

ゲームデータはこれだと言えます（1から9までの任意の順列である可能性があります）
たとえば
Data = 7, 2, 6, 1, 5, 4, 3, 8, 9

テーブルの上のピースを 8 つの異なる方法で動かすことができます。
1) 行に基づく巡回ローテーション (左から右)。
2) 行に基づく巡回ローテーション (右から左)。
3) 列に基づいて上から下へ。
4) 列に基づいて下から上へ。
5 ～ 8 は斜めに設定されているため、Column または Row は必要ありません。
5) 左上から右下 (左から右)。
6) 左上から右下 (右から左)。
7) 右上から左下 (左から右)。
8) 右上から左下 (右から左)。

データは次のようにロードされます

• 007 | 002 | 006
• 001 | 005 | 004
• 003 | 008 | 009

総当たり解決法:
1)。[右上] から [左下] (右から左)
2)。下から上、列: 0
3)。左から右、行: 1

これがシミュレートされたソリューションです

1)。[右上] へ [左下] (右から左)

• 007 | 002 | 003
• 001 | 006 | 004
• 005 | 008 | 009

2)。下から上、列: 0

• 001 | 002 | 003
• 005 | 006 | 004
• 007 | 008 | 009

3)。左から右、行: 1

• 001 | 002 | 003
• 004 | 005 | 006
• 007 | 008 | 009

これは解決するのに 6 回の移動が必要な例 2 です。

• 009 | 008 | 007
• 006 | 005 | 004
• 003 | 002 | 001

解決方法: (6 手)
1)。[右上] から [左下] (右から左)
2)。上から下、列:1
3)。下から上、列:0
4)。[左上] から [右下] (左から右)
5)。左から右、行:1
6)。右から左、行:2

とても単純なパズルですが、効率的な解決策を見つけるのは簡単ではありません。誰かが私を正しい方向に導くことができますか？

反復的な深化 a-star 検索 (8 パズル問題用ですが、他の問題を受け入れることができます) を実装し、入力に対して実行しました。2時間実行できませんでした。ゴール ノードに近い単純な入力の場合は、正常に機能します。他の人は、この入力で機能するようになりました。私の実装が単に非効率なのか、それとも無限ループに陥っているのかはわかりません

PuzzleSolver.java$ida

PuzzleSolver.java$CheckDup

開始状態 (失敗):

目標状態:

(1 3 4 8 6 0 7 5 2 で動作) Node.java は含まれていません。なぜなら、ベスト ファーストや dfs などの他の検索アルゴリズムを実行した後に動作することを確信しているからです。SCCE を提供するのは難しいので、ida 実装の明らかなバグを見つけるための助けを求めています。

編集:問題は解決しましたが、目標に到達できない場合の終了条件を見つけようとしています。IDA* は探索されたノードのリストを保持していません。では、ソリューション空間全体をカバーしたかどうかをどのように確認できますか?

私は Ant Colony Optimization による 15 パズル ソルバーを実装しており、各状態を効率的に数値にハッシュする方法を考えているため、バイトの無駄遣いを最小限に抑えています。

状態は、0 から 15 までの 16 個の数字のリストで表されます (0 は穴)。

お気に入り：

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]

そのため、その州を識別するための一意の番号を作成したいと考えています。すべての数字を 16 進数に変換できますが、あまり効率的ではないと思います。

ありがとう