7

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パズルを正しく解くので、何が問題なのかわからず、マンハッタン距離の計算を非難することもできません。

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

/**
 * Calculates sum of Manhattan distances for this board and stores it in private field to promote immutability.
 */
private void calculateManhattanDistance() {
    int manhattanDistanceSum = 0;
    for (int x = 0; x < N; x++) // x-dimension, traversing rows (i)
        for (int y = 0; y < N; y++) { // y-dimension, traversing cols (j)
            int value = tiles[x][y]; // tiles array contains board elements
            if (value != 0) { // we don't compute MD for element 0
                int targetX = (value - 1) / N; // expected x-coordinate (row)
                int targetY = (value - 1) % N; // expected y-coordinate (col)
                int dx = x - targetX; // x-distance to expected coordinate
                int dy = y - targetY; // y-distance to expected coordinate
                manhattanDistanceSum += Math.abs(dx) + Math.abs(dy); 
            } 
        }
    manhattanDistance = manhattanDistanceSum;
}

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

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

4

2 に答える 2

4

17回の移動でこれを解決していたときと同じ場所で立ち往生していました。問題は、A *アルゴリズムにヒューリスティックh（n）のみを使用していたのに対し、次のノードを選択するためにA *はマンハッタン距離（ヒューリスティック）を使用することでした。 ）+ pathcost（g（n）と呼ばれるルートからノードに到達するためのコスト）を選択します。これをアルゴリズムにプラグインすると、魅力のように機能します。

これが同じ場所で立ち往生している誰かを助けることを願っています。

于 2017-11-04T16:13:24.327 に答える
1

ヒューリスティックが許容できる場合（そして、これを確認してください）、A*は常に最適なソリューションを返します。遅くなったり速くなったり（ノードを多かれ少なかれ拡張する）できますが、最適なソリューションが返されます。

したがって、ヒューリスティックが許容できるので、問題はA*アルゴリズムの実装にある必要があります。

さらに、その最初のステップが最適なステップとは異なるという事実は無意味です。アルゴリズムはバックトレースを正しく実行して、将来的に正しいソリューションパスを取得できます。現在のノードの子だけでなく、開いているすべてのノードが次のステップの候補になります。

于 2012-09-22T10:25:42.650 に答える