A* 寻路 - 欧几里得距离启发式的表现比对角线距离差

Question

我根据这个实现了 A* 寻路算法：https : //www.redblobgames.com/pathfinding/a-star/introduction.html

我的网格有很多障碍（一万多），而且很大。我明白，为了得到最短路径之一，我需要实现一个可接受的启发式，所以它不会高估当前点和目标之间的距离。理论上，欧氏距离必须始终小于或等于。但是，使用它，我根本没有得到最短路径，因为使用对角线（切比雪夫或八分位数）距离我得到了更短的路径。这是为什么？我错过了什么吗？这是代码：

graph.cost 总是返回 1

graph.neighbors 返回 8 个相邻位置（如果有障碍物则更少）

def a_star_search(graph, start, goal):
    frontier = PriorityQueue()
    frontier.put(start, 0)
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0

    while not frontier.empty():
        current = frontier.get()

        if current == goal:
            break

        for next in graph.neighbors(current):
            new_cost = cost_so_far[current] + graph.cost(current, next)
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + heuristic(goal, next)
                frontier.put(next, priority)
                came_from[next] = current

    return get_path(came_from, start, goal)

def heuristic(a, b):
    dx = abs(b[0] - a[0])
    dy = abs(b[1] - a[1])
    D = 1
    #with D2 = 1 it's even slower but more accurate
    D2 = math.sqrt(2)
    #Diagonal distance - this is more accurate
    #return D*(dx + dy) + (D2 - 2*D)*min(dx, dy)
    #Euclidean distance - this is faster and less accurate
    return math.sqrt(dx*dx + dy*dy)

Answer 1

问题是因为邻居都是8个相邻的网格点，而且它们之间的代价都是1，所以欧氏距离高估了对角点之间的代价。

对角点之间的实际距离：1

估计距离：sqrt(2) = 1.41421356237

因此，您的图表不允许使用欧几里得距离！