曼哈顿距离在A *
我正在使用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;
}
如果您有任何见解或想法，我将不胜感激。
如果需要额外的代码，我会马上发布。
我被困在同一个地方，在17次移动中我解决了这个问题。问题是我只使用启发式h（n）作为A *算法，而选择下一个节点A *使用曼哈顿距离（启发式）+ pathcost（从根到达节点的成本，称为g（n））进行选择。 一旦你插入到算法中，它就像魅力一样。
希望这可以帮助那些陷入同一个地方的人。
如果你的启发性是可以接受的（就是检查这个），而不是A *总是返回最优解。 可以更慢或更快（扩展更多或更少的节点），但它会返回最佳解决方案。
所以，导致你的启发式是可接受的问题必须在A *算法实现中。
另外，它的第一步与最优步骤不同的事实是没有意义的：该算法可以正确地执行回溯以在未来获得正确的解决方案路径。 所有开放节点都是下一步的候选对象，不仅是当前节点的子节点。
链接地址: http://www.djcxy.com/p/11233.html