我正在使用A *搜索算法并使用“曼哈顿距离”作为启发式方法来实现NxN难题求解器，但遇到了一个奇怪的错误(？)，我无法解决这个问题。
考虑以下难题(0元素为空白):
(初始)1 0 27 5 48 6 3
(目标)1 2 34 5 67 8 0
从初始状态到达求解的最小移动数为11。但是，我的求解器在17个移动中达到目标。
其中存在一个问题-我的谜题求解器主要以正确的(最小)步数来解决可解决的难题，但是对于这个特殊的谜题，我的求解器超出了最小步数，我认为我将问题归结为错误计算在这种情况下的曼哈顿距离
在这个link上，您可以看到我的求解器在做什么(在右侧)以及经过久经考验的求解器在做什么(Brian Borowski出色的求解器，可用here)。
在第一步中，Brian的求解器立即选择将元素5向上推的解决方案，但是我的求解器有其他想法，在stacktrace(给link给出)上，我的求解器选择向左推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;
}
如果您有任何见解或想法，我将不胜感激。
如果需要任何其他代码，我会立即将其发布。
最佳答案
我曾经被困在同一位置，当时我要解决17个 Action ，问题是我只对A *算法使用启发式h(n)，而选择下一个节点A *使用曼哈顿距离(启发式)+路径成本(从根到达节点的成本，称为g(n))进行选择。
将其插入算法后，它就可以像魅力一样工作。
希望这可以帮助陷入困境的人。