在二维数组中计算曼哈顿距离

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

我的汉明计算是正确的，返回值为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

- Matt

---

那么为什么你的代码里有他们的名字？请清理一下你的注释。 - Bohemian

我猜在发布之前我忘记删除它们了。只是好奇，为什么我的评论内容如此重要？这是我自己的个人笔记，用于与同学核对我是否正确完成任务。 - Matt

另外，我已经找出了问题所在，因此我已经编辑了帖子。 - Matt

好的问题应该简洁明了，尽可能精炼到点子上。杂乱无章或与问题无关的评论对未来的访问者没有任何帮助。另外，请不要在问题中发布答案；将您的答案作为实际答案发布：如果您认为自己的答案比当前发布的答案更好（顺便说一下，我认为当前发布的答案更好），请删除您对问题的“解决方案”，并发布一个答案。 - Bohemian

好的 - 只是想问一下，因为我很好奇你在评论背后的推理是什么。显然，当涉及到StackOverflow时，您比我有更丰富的经验，因此我将采纳您的建议，并将其应用于我在网站上提出的未来问题中。如果我可以提一个建议，我会用一种不那么激烈的方式表达这些问题; 因为它有时可能会比您预期的更加严厉。感谢您的批评，希望您度过愉快的一天。 - Matt

Answer 1

错误出现在距离的更新上。

在写下 distance += Math.abs(blocks[row][column]) + Math.abs(goal[row][column]); 时，你会将初始和目标单元格的所有内容相加。在初始和目标中唯一被排除的是具有与 0 相同坐标的单元格。

在您的示例中，这给出了从 0 到 8 的两倍总和减去 5。 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);
} 

不要取平方根。

- blafasel