计算二维数组内的曼哈顿距离

Question

我正在编写一个程序来解决 nxn 8 拼图问题。我的曼哈顿计算函数与我正在测试我的程序的难题相差两个，我遇到了困难。这最终将扩展为使用 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

我的汉明计算是正确的 returns 5，但是我的曼哈顿 returns 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

Answer 1

错误在于距离的更新。

在写作 distance += Math.abs(blocks[row][column]) + Math.abs(goal[row][column]); 时，您添加了初始单元格和目标单元格的所有内容。 initial 和 goal 中只排除一个与 initial.

中坐标相同的单元格 0

在您的示例中，这给出了从 0 到 8 减 5 的 2 倍总和。2 * 36 -8 = 64。然后你取 8 的正方形。

曼哈顿 - 如 Wiktionary 所述，是按行距离加上列距离计算得出的。

你的算法必须像这样锁定（小心，前面是伪代码！）

for (cell : cells) {
    goalCell = findGoalcell(cell.row, cell.col);
    distance += abs(cell.row - goalCell.row);
    distance += abs(cell.col - goalCell.col);
}

并且不求平方根。

计算二维数组内的曼哈顿距离

Calculating Manhattan Distance within a 2d array

java

distance

a-star