15 パズルを解くための A* アルゴリズムを実装しました。私は実行可能または許容可能なヒューリスティックを見つけるための調査を行い、迅速な解決策を探しました。ヒューリスティックとして 4*Manhattan Distance を使用すると、常に 15 パズルを 1 秒未満で解決できることがわかりました。私はこれを試してみましたが、効果的に機能します。私はそれに対する答えを見つけようとしましたが、見つけることができません。
誰でもこれを説明できますか？
質問する
970 次
1 に答える
3
4 *マンハッタン距離はヒューリスティックでは許容されません。これにより、アルゴリズムは最初に貪欲に「近く」動作します（アルゴリズムはヒューリスティック関数のみに基づいて開発するノードを選択します）。これにより、アルゴリズムは、幅と最適性よりもソリューションの深さと探索を優先する場合があります。
この考え方は、A *-Epsilonで発生することと似ています。ここでは、アルゴリズムを高速化するために、A *が特定の境界まで最適なノードを開発できないようにします。実際には、同じ（または同様の結果）が得られると思います。マンハッタン距離と。でA*-イプシロンを実行する場合epsilon = 3。（私が正しければ、これにより、で囲まれた変更されたヒューリスティックで見つけたソリューションが作成されます4*OPTIMAL。ここで、OPTIMALは最適なパスの長さです）
于 2012-10-25T19:07:35.203 に答える