我在使用A*搜索算法实现NxN拼图解算器，并使用曼哈顿距离作为启发式函数时，遇到了一个奇怪的bug（？），我无法理解它。

考虑这些拼图（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向左推的解决方案（因为那个棋盘的曼哈顿距离更低，该棋盘位于优先级队列的前端）。我看不出问题出在哪里，也不能责怪我的曼哈顿距离计算，因为它正确地解决了许多其他3×3拼图。

这是我如何计算给定棋盘的曼哈顿距离：

/** * 计算此棋盘的曼哈顿距离之和，并将其存储在私有字段中以促进不可变性。 */private void calculateManhattanDistance() {    int manhattanDistanceSum = 0;    for (int x = 0; x < N; x++) // x维度，遍历行（i）        for (int y = 0; y < N; y++) { // y维度，遍历列（j）            int value = tiles[x][y]; // tiles数组包含棋盘元素            if (value != 0) { // 我们不计算元素0的MD                int targetX = (value - 1) / N; // 预期的x坐标（行）                int targetY = (value - 1) % N; // 预期的y坐标（列）                int dx = x - targetX; // 到预期坐标的x距离                int dy = y - targetY; // 到预期坐标的y距离                manhattanDistanceSum += Math.abs(dx) + Math.abs(dy);             }         }    manhattanDistance = manhattanDistanceSum;}

我很感激你能提供任何见解或想法。

如果需要更多代码，我会立即发布。

回答：

我之前也曾卡在同样的地方，当时我在17步内解决了这个问题。问题在于我只使用了启发式函数h(n)来进行A*算法，而在选择下一个节点时，A*使用曼哈顿距离（启发式函数）+路径成本（从根节点到达该节点的成本，称为g(n)）来做出选择。一旦你将这个因素加入算法中，它就会运作得非常好。

希望这能帮助那些卡在同样问题上的人。