曼哈顿距离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次移动中达到目标.

其中存在的问题是 - 我的解谜手段主要解决了正确(最小)移动数量的可解决难题,但对于这个特殊的谜题,我的求解器超过最小移动次数而且我认为我已经将问题确定为错误计算在这种特殊情况下的曼哈顿距离.

在这个链接中,你可以看到我的求解器在做什么(在右边)以及经过试验的求解器正在做什么(Brian Borowski的优秀求解器,可在此处获得).

在第一步中,Brian的解算器立即选择推动元素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;
}

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

如果需要任何其他代码,我会马上发布.

Answer 1

我被困在同一个地方，当时我用 17 步解决了这个问题。问题是我只对 A* 算法使用启发式 h(n)，而选择下一个节点 A* 使用曼哈顿距离（启发式) + 路径成本（从根到达节点的成本，称为 g(n)）来做出选择。一旦你将其插入到算法中，它就会像魅力一样发挥作用。

希望这可以帮助那些被困在同一个地方的人。