为什么允许对角线移动会使A*和曼哈顿距离不可接受？ [英] Why allowing diagonal movement would make the A* and Manhattan Distance inadmissible?

问题描述

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

推荐答案

正如贝克的评论所表明的那样，曼哈顿距离将高估一个州与其对角可访问的州之间的距离。根据定义，超出估计距离的启发式是不允许的。

现在，到底为什么会这样？

假设您的曼哈顿距离程序如下所示：

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

这篇关于为什么允许对角线移动会使A*和曼哈顿距离不可接受？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！