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

Question

我对使用A*和曼哈顿距离度量的网格中的对角线移动感到有些困惑.有人可以解释为什么使用对角线运动使其不可接受吗？不会进行对角线移动找到一个更好的最佳解决方案,因为采取较少的步骤来达到目标​​状态而不是向上向左下方或我错过了什么？

Answer 1

就像烧杯的评论所表达的那样,曼哈顿距离将高估一个州与对角线可以接近的州之间的距离.根据定义,超出估计距离的启发式算法是不可接受的.

现在,为什么会这样呢？

让我们假设你的曼哈顿距离程序看起来像这样:

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,这实际上不是对实际距离的过高估计.