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

Question

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

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

graph.cost 总是 returns 1

graph.neighbors returns相邻的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

所以欧几里德距离对于您的图表来说不可接受！

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

A* pathfinding - Euclidean distance heuristic behaving worse than Diagonal distance

python

heuristics

a-star

path-finding