artificial-intelligence - 为什么允许对角线移动会使 A* 和曼哈顿距离 Not Acceptable ？

Question

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

Answer 1

正如 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。因此，在这种情况下，曼哈顿距离将不能作为一种可接受的启发式方法。

在允许对角移动的游戏板上，通常使用 Chebyshev Distance 代替。为什么？

考虑这个新程序:

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，这确实不是对实际距离的高估。