为什么允许对角线移动会使A*和曼哈顿距离变得不可接受？

我对在网格中使用A*和曼哈顿距离度量时的对角线移动有些困惑。能有人解释一下为什么使用对角线移动会使其不可接受吗？难道对角线移动不会找到更优的解决方案吗？比如说，比上下左右移动更少的步骤就能到达目标状态，还是我错过了什么？

回答：

正如beaker的评论所指出的，曼哈顿距离会高估一个状态与其对角线可达状态之间的距离。根据定义，高估距离的启发式是不被接受的。

那么，为什么会这样呢？

假设你的曼哈顿距离程序看起来像这样：

function manhattan_dist(state):     y_dist = abs(state.y - goal.y)    x_dist = abs(state.x - goal.x)    return (y_dist + x_dist)

现在，考虑将该程序应用于状态(1,1)，假设目标在(3,3)。这将返回值4，这高估了实际距离2。因此，在这种情况下，曼哈顿距离作为可接受的启发式是不适用的。

在允许对角线移动的游戏棋盘上，通常使用切比雪夫距离。为什么呢？

考虑这个新的程序：

function chebyshev dist(state):     y_dist = abs(state.y - goal.y)    x_dist = abs(state.x - goal.x)    return max(y_dist, x_dist)

回到之前的例子(1,1)和(3,3)，这个程序将返回值2，这确实不是对实际距离的高估。

学技术