問題タブ [sliding-tile-puzzle]

nパズルの問題を解決するプログラムを実装しようとしています。
タイルを表す行列によって特徴付けられる問題の状態を持つJavaでの簡単な実装を作成しました。また、開始状態を示すすべての状態のグラフを自動生成することもできます。グラフでは、BFSを実行して、目標状態へのパスを見つけることができます。
しかし、問題は、メモリが不足していて、グラフ全体を作成することさえできないことです。2x2タイルで試してみましたが、機能します。また、3x3もあります（開始状態とグラフ内のノード数によって異なります）。しかし、一般的にこの方法は適切ではありません。
そこで、検索中に実行時にノードを生成してみました。動作しますが、遅いです（数分経ってもまだ終了しておらず、プログラムを終了する場合があります）。
ところで：私は開始状態として解決可能な構成のみを与え、重複した状態を作成しません。
そのため、グラフを作成できません。これが私の主な問題につながります。A*アルゴリズムを実装する必要があり、パスコスト（つまり、各ノードの開始状態からの距離）が必要ですが、実行時に計算できないと思います。グラフ全体が必要ですよね？A *はグラフのBFS探索に従わないため、各ノードの距離を推定する方法がわかりません。したがって、A*検索を実行する方法がわかりません。
なにか提案を？

編集

State:

Solver:

基本的にここに私がすることはあります：
- Solver'ssolveには。がありSortedSetます。要素（States）は、に従ってソートされます。これはComparator1、を計算しますf(n) = g(n) + h(n)。ここg(n)で、はパスコストでありh(n)、はヒューリスティック（誤って配置されたタイルの数）です。
-開始構成を示し、すべての後継者を探します。
-サクセサがまだアクセスされていない場合（つまり、グローバルセットにない場合States）、キューとに追加しStates、現在の状態を親およびparent's path + 1パスコストとして設定します。
-デキューして繰り返します。

次の理由で機能するはず
です。-訪問したすべての状態を保持するので、ループしません。
-また、現在のノードの後継をすぐに保存するので、無駄なエッジはありません。例：AIからBとCに移動でき、BIからもCに移動できる場合、エッジB-> Cは存在しません（パスコストは各エッジで1であり、A->BはAよりも安いため） -> B-> C）。-A *に従って
、パスを最小で拡張することを選択するたびに。 しかし、それは機能しません。または、少なくとも、数分経っても解決策を見つけることができません（この場合はかなりの時間がかかると思います）。 A *を実行する前にツリー構造を作成しようとすると、それを構築するためのメモリが不足します。 編集2 これが私のヒューリスティック関数です：f(n)

単純な欲張りアルゴリズムを使用すると、両方が機能します（マンハッタン距離の使用は非常に高速です（解決策を見つけるために約500回の反復）が、タイルの配置が間違っている場合は約10k回の反復が必要です）。A *（パスコストも評価）を使用すると、非常に遅くなります。

コンパレータは次のようなものです。

編集3

少しエラーがありました。修正したところ、A*が機能するようになりました。または、少なくとも、3x3の場合、700回の反復で最適なソリューションが見つかった場合。4x4の場合はまだ遅すぎます。IDA *を試してみますが、1つの質問です。A*を使用して解決策を見つけるのにどのくらい時間がかかりますか？分？時間？私はそれを10分間放置しましたが、それは終わりませんでした。

A *検索アルゴリズムを使用し、ヒューリスティックとしてマンハッタン距離を使用してNxNパズルソルバーを実装していますが、頭を包むことができない奇妙なバグ（？）に遭遇しました。

これらのパズルを考えてみましょう（0要素は空白です）:(
初期）

1 0 2
7 5 4
8 6 3

（ゴール）

1 2 3
4 5 6
7 8 0

初期状態から解に到達するための最小移動回数は11です。しかし、私のソルバーは17回の移動で目標に到達します。

そしてそこに問題があります-私のパズルソルバーはほとんど正しい（最小）移動数で解決可能なパズルを解決しますが、この特定のパズルでは、私のソルバーは最小移動数をオーバーシュートし、問題を誤算に突き止めたと思いますこの特定の場合のマンハッタン距離の。

このリンクで、私のソルバーが実行していること（右側）と、試行錯誤されたソルバーが実行していることを確認できます（Brian Borowskiの優れたソルバー、ここで入手可能）。

最初の動きで、ブライアンのソルバーは要素5を押し上げるソリューションをすぐに選択しますが、私のソルバーには他のアイデアがあり、スタックトレース（リンクで指定）で、ソルバーは2を左にプッシュするソリューションを選択します（そのボードのマンハッタンから）距離が短い場合、ボードは優先キューの先頭にあります）。他の多くの3x3パズルを正しく解くので、何が問題なのかわからず、マンハッタン距離の計算を非難することもできません。

特定のボードのマンハッタン距離を計算する方法は次のとおりです。

私はあなたが持っているかもしれない洞察やアイデアをいただければ幸いです。

追加のコードが必要な場合は、すぐに投稿します。

n-パズル ソルバーに問題があります。うまくいっていると思っていましたが、解決できないパズルを解いていることがわかりました。私はそれを追跡しようとしましたが、それは多くの追跡であり、今のところ不正行為は見られません. 溶解度を決定するためのアルゴリズムを理解していると思います。私の実装は、Web からのいくつかの例の奇数/偶数パリティと一致しています。すべてのタイルに対して、空白のタイルの行インデックスを追加すると、他の人が取得したのと同じ奇数または偶数が得られます。

そこでふと浮かんだ考え。私のモデル、たとえば 8 パズルでは、解の状態は次のようになります。

それよりも

または

他のいくつかの製剤にあるように。これは、解けるパズルと解けないパズルに影響しているのでしょうか?

ありがとう！

z。

私は、 8パズル問題の解決策を見つけるために、反復深化深さ優先探索の実装に取り​​組んでいます。私は実際の検索パス自体を見つけることに興味はありませんが、プログラムの実行にかかる時間を計るだけです。（私はまだタイミング機能を実装していません）。

ただし、実際の検索機能を実装しようとすると問題が発生します（下にスクロールして表示）。これまでに持っているすべてのコードを貼り付けたので、これをコピーして貼り付けると、実行することもできます。これは、私が抱えている問題を説明するための最良の方法かもしれません...たとえば、最初の展開が必要なパズル2（p2）のテストで、再帰中に無限ループが発生する理由がわかりません。解を生成します。コード行の1行の前に「Return」を追加しないことと関係があるのではないかと思いました（以下にコメントがあります）。リターンを追加すると、パズル2のテストに合格できますが、パズル3のようなより複雑なものは失敗します。これは、コードが左端のブランチのみを展開しているように見えるためです...

何時間もこれにいて、希望をあきらめました。私はこれについて別の目で見ていただければ幸いです。私の誤りを指摘していただければ幸いです。ありがとうございました！

タイトルが示すように、私は最良優先探索を使用して8パズルを解くプロローグプログラムを作成する必要があります。私はプロローグとAIに慣れていないため、苦労しています。

今のところ私が持っているのは移動ルールです：

（リストを使用するより簡単な方法があることは知っていますが、これが私にとってうまくいったことです）

そして私がインターネットで見つけた最高の最初のコード：http ：//www.cs.unm.edu/~luger/ai-final/code/PROLOG.best.html

しかし、その最良の最初のコードには、実行されないこのヒューリスティック関数があります。

問題によってヒューリスティックが変化するため、どこにも定義されておらず、自分で定義する必要があるためだと思います。

そこで、マンハッタン距離などよりもコーディングが簡単に聞こえるので、8パズルに「タイルがずれている」ヒューリスティックを使用することを考えました。しかし今、私はそれをプログラムする方法に固執しています、私はリストを比較する方法と変数を追加する方法についてどこでもグーグルで検索しました、そして私はちょっとこれを作りました、それは私がうまくいくかどうかわかりません：

私の考えでは、スタートリストのすべての要素を検索し、それをゴールリストと比較します。次に、それらが異なる場合は、Hに1を加算し、Hは場違いのタイルの数になります。

私が「同じ場所のタイルのルール」も定義したことについて：

しかしもちろん、「エラー：ヒューリスティック/ 3：引数が十分にインスタンス化されていません」というメッセージが表示されます。これは、Hを初期化したことがないことを意味すると思います。

コードの残りの部分が実際にどのように機能するかはわかりません。最良の最初のアルゴリズムは幅優先のようなものですが、キューを単に追加するのではなく、ヒューリスティックに従って並べ替えます。

私の質問は次のとおりです。-私は正しい方向に進んでいますか、それともそこにあるその「ヒューリスティック」機能が何を意味するのかを完全に読み違えましたか？-Hを初期化するにはどうすればよいですか？-私の「ヒューリスティック」関数コードは構文的に正しいですか？

長い投稿で申し訳ありませんが、ルールは私がたくさんの情報を与えるべきだと言っています。私はあなたがこれで私を助けてくれることを願っています、どんな助けでもありがたいです、それであなたがこれをする他の方法を知っているならそれらを自由に投稿してください、私は初心者です。

前もって感謝します。

シンプルなスライド パズル (Loyd) ソルバーを書いています。3 x 3 以上の寸法のパズルの任意の解決可能な構成を解決したいと考えています。しかし、再帰の実装に行き詰まりました。私はツリーとスタックを持っています。

スタックには静的サイズがあります。今、私は解決策を見つける方法を持っています。しかし、再帰を実装する方法と、作成されたノードを保存してパスを見つける方法がわかりません。これまでのところ、私は持っています：

ではどうすればいいのか、例えば。y = 0 なので、新しい左構成を作成できません。私は戻る必要があります。しかし、そうすると、無限ループに陥ります。任意のサイズのパズル > 2 を解きたいことに注意してください。

そして、スタック内の重複を検索する私の関数は次のとおりです。

誰でも助けることができますか？お時間をいただきありがとうございます。:)

8 パズルは、[[9,1,3]、[5,2,6]、[4、[9,1,3]、[5,2,6]、[4、 7,8]]

可能性 解決策: 8 パズルの初期位置の半分しか解けない。パズルを解けるかどうかを最初から知ることができる公式があります.8 パズルが解けるかどうかを判断するには、値 N を含む各正方形について、現在のセルの後に N より小さい数がいくつあるかを計算します。たとえば、初期状態に:

• 1 以下の数字なし = 0
• 空 (9) - 続いて 3,5,2,6,4,7,8 = 7 にする必要があります
• 3 持っている = 1 対 2
• 5 はその後 2,4 = 2 になりました
• 2 その下に数字がない場合 = 0
• 6はその後 4 = 1
• 4 以下の数字なし = 0
• 7 後にマイナー番号なし = 0
• 8 以下の数字なし = 0

その後、空の位置と位置の間のマンハッタン距離を計算します (3.3)。上記の例では、空のボックスは位置 (1.2) にあるため、マンハッタン距離は次のようになります: d = abs (3-1) + abs (3-2) = 3 最後に、すべての計算値を合計します。結果が偶数の場合はパズルが解けることを意味しますが、解けない場合は奇数です。0 +7 +1 +2 +0 +1 +0 +0 +0 +3 = 14

このソリューションは、ボード上の数字のすべての可能な状態を含む知識ベースを作成するように設計されており、現在の位置の後に N 未満の数字がいくつあるかを確認します。

これが私のコードです：

問題は、複数の選択肢を持つことができる状況があるため、私が間違いを犯していることです。

posC(C,Pc) の正しい解は posC(3,1)、つまり 1 です。しかし、時々誤った出力を引き起こす他の影響があります...コードで何が間違っているのですか?どうすればそれを変更できますか?

幅優先探索を使用して 8 パズル ソルバーを作成しました。ここで、ヒューリスティックを使用するようにコードを変更したいと思います。次の2つの質問に答えていただけるとありがたいです。

可解性

8 のパズルが解けるかどうかをどのように判断しますか? （開始状態と目標状態が与えられた場合）これはウィキペディアの言うことです：

不変量は、16 個の正方形すべての順列のパリティに、空の正方形の右下隅からのタクシー距離 (行数と列数) のパリティを加えたものです。

残念ながら、私にはその意味が理解できませんでした。理解するのは少し複雑でした。誰かがそれをもっと簡単な言葉で説明できますか?

最短ソリューション

ヒューリスティックが与えられた場合、A* アルゴリズムを使用して最短の解を与えることが保証されますか? より具体的には、オープン リストの最初のノードには、オープン リストに存在するすべてのノードの深さの最小値である深さ (または非常に太った動きの数) が常にありますか?

ヒューリスティックは、上記のステートメントが真であるために何らかの条件を満たす必要がありますか?

編集:許容可能なヒューリスティックが常に最適なソリューションを提供するのはどうしてですか? そして、ヒューリスティックが許容できるかどうかをどのようにテストするのでしょうか?

ここにリストされているヒューリスティックを使用します

Eyal Schneider からの説明:

私はプロローグが初めてで、8パズルのヒューリスティックに問題があります。2 つのリスト (ゴールとスタート) を比較して、自分の h 値を計算する方法がわかりません。私がやろうとしているのは、compare_list の 2 つのリストに目標を送信して開始することです。各ヘッドを比較し、等しくない場合は合計に1を追加し、それ以外の場合は自己再帰的に呼び出します。プロローグの if else ステートメントの実行方法がわかりません。

8パズルのゲームソルバーをC++でコーディングしようとしていますが、それを実行しているときに多くの問題が発生します。プログラムは現在機能していますが、パズルを解くには手順が多すぎます。つまり、最適なソリューションを見つけることができる場合もあれば、それを解決するのに400ステップもかかる場合もあります。私の主な疑問は次のとおりです。私がこの図を持っていると想像してください（これは単なるドラフトです）：

ヒューリスティック関数としてマンハッタン距離を使用しています。最初のステップの後、f（n）= 5の2つの状態があるので、ツリーを展開しました。展開した後でも、f（n）=2の2つの状態があります。ここに私の疑問があります。一意の最低f（n）が得られるまで、ツリーを拡張する必要がありますか？

前もって感謝します！