java计算二维数组中的曼哈顿距离
我正在写一个程序来解决一个NXN8难题。我在测试我的程序时,曼哈顿计算函数与谜题之间的距离有两个偏差,这让我感到很困难。这将最终扩展到使用A*寻路算法,但我还没有做到
以下是我的职能(基于董事会的初始状态,不考虑迄今为止采取的行动量):
// sum of Manhattan distances between blocks and goal
public int Manhattan() // i don't think this is right yet - check with vince/thomas
{
int distance = 0;
// generate goal board
int[][] goal = GoalBoard(N);
// iterate through the blocks and check to see how far they are from where they should be in the goal array
for(int row=0; row<N; row++){
for(int column=0; column<N; column++){
if(blocks[row][column] == 0)
continue;
else
distance += Math.abs(blocks[row][column]) + Math.abs(goal[row][column]);
}
}
distance = (int) Math.sqrt(distance);
return distance; // temp
}
这就是我正在研究的例子:
8 1 3 1 2 3 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
4 2 4 5 6 ---------------------- ----------------------
7 6 5 7 8 1 1 0 0 1 1 0 1 1 2 0 0 2 2 0 3
initial goal Hamming = 5 + 0 Manhattan = 10 + 0
我的汉明计算是正确的,返回5,但我的曼哈顿返回8而不是10。我做错了什么
这是我的程序的输出:
Size: 3
Initial Puzzle:
8 1 3
4 0 2
7 6 5
Is goal board: false
Goal Array:
1 2 3
4 5 6
7 8 0
Hamming: 5
Manhatten distance: 8
Inversions: 12
Solvable: true
# 1 楼答案
错误在于距离的更新
在编写
distance += Math.abs(blocks[row][column]) + Math.abs(goal[row][column]);
时,添加initial和goal单元格的所有内容。只有一个在initial和goal中被排除的单元格与initial中的0
坐标相同在您的示例中,这给出了从0到8减去5的2倍总和
2 * 36 -8 = 64
。然后取8的正方形曼哈顿-如Wiktionary所述,通过行中的距离加上列中的距离来计算
您的算法必须像锁一样锁定(注意,前面有伪代码!)
不要取平方根