曼哈顿距离（A *）

Question

我正在使用A *搜索算法并使用“曼哈顿距离”作为启发式方法来实现NxN难题求解器，但遇到了一个奇怪的 错误 （？），我无法解决这个问题。

考虑以下难题（0元素为空白）：（
初始）

1 0 2
7 5 4
8 6 3

（目标）

1 2 3
4 5 6
7 8 0

从初始状态到达求解的最小移动数为11。但是，我的求解器在17个移动中达到目标。

其中存在一个问题-
我的谜题求解器主要以正确的（最小）步数来解决可解决的难题，但是对于这个特殊的谜题，我的求解器超出了最小步数，我认为我将问题归结为错误的计算在这种情况下的曼哈顿距离。

在此链接中，您可以看到我的求解器在做什么（在右侧）以及一个经过n次测试的求解器在做什么（Brian
Borowski出色的求解器，可在此处找到）。

第一步，Brian的求解器立即选择将元素5向上推的解决方案，但是我的求解器有其他想法，在stacktrace（在链接上给出）上，我的求解器选择向左推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;
}

如果您有任何见解或想法，我将不胜感激。

如果需要任何其他代码，我会立即将其发布。

Answer 1

我有时被困在同一位置，当时我在17个动作中解决了这个问题。问题是我只对A 算法使用启发式h（n），而选择下一个节点A

使用曼哈顿距离（启发式）+路径成本（从根到达节点的成本，称为g（n））进行选择。将其插入算法后，它就可以发挥作用。

希望这可以帮助陷入困境的人。