1

2つのヒューリスティックを使用して24パズル（5x5グリッド）を解決するプログラムを書いています。1つ目は、間違った場所のブロック数を使用し、2つ目は、ブロックの現在の場所と目的の場所の間のマンハッタン距離を使用します。

プログラムには、A *と欲張り検索を使用して各ヒューリスティックを使用し、結果を比較するさまざまな機能があります（合計で4つの異なる部分）。

私のプログラムが間違っているのか、それともパズルの限界なのか知りたいです。パズルはランダムに生成され、ピースが数回動かされ、ほとんどの場合（〜70％）、ほとんどの検索で解決策が見つかりますが、失敗することもあります。

欲張りが完全ではないので失敗する理由は理解できますが、A *が完全であると見ると、コードにエラーがあると思います。

それで、誰かがこれが私の思考の誤りなのか、それともパズルの限界なのか教えてもらえますか？言い回しが悪い場合は申し訳ありませんが、必要に応じて言い換えます。

ありがとう

編集：

ですから、私はそれが私が間違っていることだとかなり確信しています。これが私が検索を行っている方法の段階的なリストです、ここで何か問題がありますか？

  • 使用されているヒューリスティックでソートされた、フリンジの新しいリストを作成します
  • 訪問したノードを保存するセットを作成する
  • パズルの初期状態をフリンジに追加します
  • フリンジが空ではない間。
    • フリンジから最初の要素をポップします
    • 以前にノードにアクセスしたことがある場合は、スキップしてください
    • ノードが目標の場合は、それを返します
    • 訪問したセットにノードを追加します
    • ノードを展開し、すべての子孫をフリンジに追加します
4

4 に答える 4

3

スライディングパズルを意味する場合：これは、実用的なソリューションから2つのピースを交換する場合に解決可能です。したがって、ソリューションが見つからない場合、アルゴリズムの正確性については何もわかりません。

それはあなたの種に欠陥があるだけです。

編集：解決策から始めて（ランダムな）合法的な動きをする場合、正しいアルゴリズムが解決策を見つけます（順序を逆にすることが解決策であるため）。

于 2010-08-22T08:26:03.917 に答える
2

誰がそれを発明したかは完全には明らかではありませんが、サムロイドは19世紀後半に5x5の4x4バージョンである14-15パズルを普及させました。

ウィキペディアの記事から、パリティの議論は、可能な構成の半分が解決できないことを証明しました。検索が失敗したときに、おそらく似たようなものに遭遇しています。

于 2010-08-22T13:49:51.067 に答える
0

リストした手順は少し不完全に見えますが、A *が解決策に到達することを保証するのに十分なリストを作成しました（ノードをスキップするだけの場合は最適ではありませんが）。

パズルの生成に欠陥があるか、アルゴリズムが正しく実装されていないようです。パズルの生成を簡単に確認するには、パズルの生成に使用した手順を保存し、逆に実行して、パズルを検索ルーチンに送信する前に、結果が解決状態であるかどうかを確認します。無効なパズルを生成した場合は、パズルと予想される手順をダンプして、問題がどこにあるかを確認してください。パズルが成功し、アルゴリズムが失敗した場合、少なくとも問題のある場所を絞り込んでいます。

アルゴリズムであることが判明した場合は、たとえば評価関数を実行するときや、キューとして機能するリスト。これにより、実装内の問題を簡単に特定できるようになります。

于 2010-08-26T14:10:33.693 に答える
0

あなたのコードは正しく、すべてのアルゴリズムとヒューリスティックを正しく実装していると仮定します。

これにより、パズルの初期化の「ランダムに生成された」部分が残ります。パズルの正しい状態を生成していますか? 違法な状態を生成すると、明らかに解決策はありません。

于 2010-08-22T08:30:26.807 に答える