如果使用欧几里德距离启发式的A *搜索允许对角移动，它仍然是最优的吗？

Question

因此，如果我在10x10迷宫中进行了A *搜索并且有10个障碍物并允许在此范围内进行对角移动，那么它仍然是最佳的吗？

我的答案是它仍然是最优的，这是因为欧几里德距离已经计算出两点之间的直线距离，所以无论如何它都会在对角线上超过搜索空间，所以我认为它不会有所作为，甚至可能会让它变得更好？不确定我是否正确思考。

Answer 1

这取决于对角线移动的成本。

考虑统一的成本情况：对角线移动的成本与非对角线（Chebyshev distance）的成本相同。

在这种情况下，绿色和红色点之间的距离是6。一般来说：

def chebyshev_distance(node):
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return max(dx, dy)

而欧氏距离启发式：

def heuristic(node):
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return sqrt(dx * dx + dy * dy)

给heuristic ≅ 6.71并高估了路径的成本，导致不可接受的启发式（可能找不到最佳路径）。

一般来说：

max（| dx |，| dy |）= | Max | = sqrt（Max2）≤sqrt（Max2 + min2）= sqrt（dx2 + dy2）