我正在编写一个A *算法，它可以解决Java中的8-puzzle，到目前为止，我已经使用了多少个瓷块实现了DFS，BFS，A *，我只需要使用曼哈顿距离的启发式实现它 .
您可能已经意识到曼哈顿距离是每个瓦片位移相对于其当前位置和目标状态下的索引的总和 .
我已经google了一下，发现这些堆栈的流程主题：
Calculating Manhattan Distance Manhattan distance in A*
其中返回了以下代码：
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);
}
}
这是我不明白的，鉴于这个董事会和这个目标状态：
初始董事会：
1,2,5
3,0,4
6,7,8
目标状态：
0,1,2
3,4,5
6,7,8
如果我键入board [0] [0]的值，其值为1，恰好是1离开其正确的位置，我得到这些结果：
x = 0;
y = 0;
value = 1;
targetX = (value -1)/3; // 0/3 = 0
targetY = (value -1)%3 //0%3 = 0
int dx = x - targetX; // 0 - 0
int dy = y - targetY; // 0 - 0
manhattanDistanceSum += Math.abs(dx) + Math.abs(dy);
最终产生0 0，这显然是不正确的，因为它应该返回值1 .
有没有其他方法，例如：
for(int i = 0; i < 3 i ++){
for(int j =0; j < 3; j ++){
int value = currentBoard[i][j];
int goalValue = getLocationOfValueInGoalState(value);
/* caluclate the value's X distance away from the returned goal state location for said value, then do the same for the Y */
}
}
希望有人理解我的问题，我现在有点困惑，诚实 .
2 回答
目标状态对您来说是一个很好的区别，以及您正在查看的参考实现的目标状态 .
对于参考实现，如果目标状态如下所示：
在您的情况下，您需要曼哈顿距离：
快速解决方法是简单地将您的目标状态重新定义为前者 .
但是，如果后者是您真正想要的，那么将targetX / Y更改为不从值减去1 .
曼哈顿距离是定义为沿对角线移动棋子时距离增加的距离 . 如果可移动的瓷砖位于右上角，要将工件移动到左下角，则无法沿对角线直接移动 . 你必须顺序左移然后向下移动 . 增加的是曼哈顿距离 . 有趣的部分是改组算法 . 曼哈顿距离在数学上也被称为出租车驾驶室距离http://en.wikipedia.org/wiki/Taxicab_geometry .