Python下改造Dijkstra最小堆实现A*算法的正确性校验

我正在将基于最小堆（优先队列）实现的Dijkstra算法改造为带启发函数的A算法，参考了标准Dijkstra实现方案。目前我在多组测试图上运行代码都能得到符合预期的结果，想确认下面的a_star函数是不是A的正确实现。

按照f = g + h的公式定义，我调整了优先队列的存储结构，使用(f, g, vertex)格式的元组存储条目，保证每次执行heappop()时取出的是f值最小的节点；另外我新增了visited集合做访问标记，具体实现代码如下：

import heapq

# 时间复杂度O(V+ElogE) / 空间复杂度O(E)
def a_star(graph, start, dest, heuristic):
    # 初始化距离字典 时间O(V)/空间O(V)
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0

    # 初始化父节点字典，用于还原路径 时间O(V)/空间O(V)
    parent = {vertex: None for vertex in graph}

    visited = set()

    # 优先队列初始化 空间O(E)
    pq = [(0 + heuristic[start], 0, start)]

    while pq: # 总时间复杂度O(ElogE)
        curr_f, curr_dist, curr_vert = heapq.heappop(pq) # 单次操作时间O(logE)

        if curr_vert not in visited:
            visited.add(curr_vert)

            for nbor, weight in graph[curr_vert].items():
                distance = curr_dist + weight  # 起点到当前邻居的实际距离，即g值
                f_distance = distance + heuristic[nbor] # f = g + h

                # 仅当新路径f值更优时考虑该路径
                if f_distance < distances[nbor]:
                    distances[nbor] = f_distance
                    parent[nbor] = curr_vert

                    if nbor == dest:
                        # 基于启发函数找到路径直接返回
                        return distances, parent

                    heapq.heappush(pq, (f_distance, distance, nbor)) # 单次操作时间O(logE)

    return distances, parent

# 测试用图
graph = {
    'A': {'B':3, 'H':4, 'F': 1},
    'B': {'A': 3, 'C':5  },
    'C': {'B':5, 'D':6, 'I':2},
    'D': {'C':6, 'E':1},
    'E': {'D':1, 'I':2, 'G':20},
    'F': {'A':1, 'G':1},
    'G': {'F':1, 'E':20},
    'H': {'A':4, 'I':8, },
    'I': {'H':8, 'C':2, 'E':2},
}
# 测试用启发函数
heuristic = {
    'A': 20,
    'B': 19,
    'C': 16,
    'D': 12,
    'E': 0,
    'F': 13,
    'G': 11,
    'H': 15,
    'I': 10,
}

start = 'A'
dest= 'E'
distances,parent = a_star(graph, start, dest, heuristic)

回答 #

你的实现不属于正确的A*算法，测试能跑通只是刚好测试用例符合你代码的触发条件，换场景就会返回错误结果，核心问题有4个：

• 距离字典存储值错误。你现在distances里存的是f值（g+h的估计值），但A*中这个字典必须存储从起点到当前节点的真实最短路径长度（即g值）。启发函数h是人为定义的估计值，不是真实路径开销，用f值做松弛判断，只要启发函数不满足单调性，就会直接过滤掉实际更优的路径。
• 提前返回时机错误。你在遍历邻居节点时，只要发现邻居是终点就直接返回结果，但A*的正确性保证有明确前提：只有当终点节点被从优先队列中弹出时，才能确认找到了到终点的最短路径。刚把终点推入队列时，队列中完全可能存在f值更小、实际路径更短的条目，此时返回的结果不一定是最优解。
• visited集合的使用缺少前提。你现在的逻辑是节点一旦被弹出队列就标记为已访问，后续不再处理，这个逻辑仅在启发函数满足一致性（即满足三角不等式：对任意节点n和其邻居n'，h(n) ≤ 边n->n'的权重 + h(n')）时才成立。如果你的启发函数是可采纳但不满足一致性的，同一个节点可能被多次推入优先队列，第一次弹出的路径不一定是最短路径，直接标记visited会拦截后续的更优路径。
• 复杂度标注错误。二叉堆实现的A*最坏时间复杂度为O(E log V)，不是你注释里写的O(E log E)。

修正思路 #

你可以按以下逻辑调整代码：

1. 把distances字典的语义改为存储节点的g值（起点到该点的真实最短距离），起点初始g值设为0，其余节点初始为无穷大
2. 松弛判断时，仅比较新路径的g值和已记录的g值，只有新g值更小时，才更新父节点、计算f值将节点推入优先队列
3. 把终点判断逻辑移到弹出堆节点的环节：每次弹出节点后先判断是否为终点，是则直接返回结果，不要在遍历邻居时做判断
4. 如果需要兼容可采纳但不一致的启发函数，可以直接去掉visited集合：弹出节点后先对比当前条目的g值和distances中存储的已知最短g值，如果当前条目g值更大，直接跳过不处理即可。

你当前的测试用例里给出的启发函数刚好满足一致性，且第一次推入终点的路径恰好就是最短路径，所以能跑出正确结果，本质是歪打正着，并没有实现A*的正确逻辑。 #

内容的提问来源于stack exchange，提问作者Ryan