A*算法可视化

伪代码

A* 就是 Dijkstra 多加一项。Dijkstra 每次扩展已确认代价 g 最小的节点，而 A* 扩展 f = g + h 最小的节点，其中 h 估计剩余代价。把 h 处处设为零，下面的伪代码就完全变成了 Dijkstra。

A*(图, 起点, 目标, h):
    对每个顶点 v: g[v] = 无穷大
    g[起点] = 0
    f[起点] = h(起点)
    开放集 = 含 (f[起点], 起点) 的优先队列
    关闭集 = 空集合

    当开放集非空时:
        u = 开放集.取最小()           // f 最小者
        若 u == 目标: 返回 重建路径(u)
        将 u 加入关闭集

        对每条边 (u, v, w):
            若 v 在关闭集中: 跳过
            试探值 = g[u] + w
            若 试探值 < g[v]:
                前驱[v] = u
                g[v] = 试探值
                f[v] = 试探值 + h(v)
                开放集.插入(f[v], v)

    返回 无路径

第 15 行跳过关闭集中的节点，只有当 h 一致时才安全，即对每条边都满足 h(u) <= w(u, v) + h(v)。若启发函数仅仅是可采纳而不一致，就必须允许节点重新离开关闭集，否则 A* 可能返回非最优路径。上方的可视化工具把直线距离乘以任意边所能提供的最低单位代价，由三角不等式可知这样得到的 h 是一致的，因此无需重新开放任何节点。

分步示例演算

五个节点，S 位于原点，目标 G 在其右侧五个单位处。这段轨迹的关键在于 A* 从未触碰的那个节点。

示例图: S(0,0)、A(2,1)、B(2,-1)、C(1,4)、G(5,0)。边 S-A = 3，S-B = 2，S-C = 4，A-B = 2，A-G = 4，B-G = 6，C-G = 7。把直线距离乘以任意边的最低单位代价（0.894），得到 h(S) = 4.47，h(A) = 2.83，h(B) = 2.83，h(C) = 5.06，h(G) = 0。

1. 1. 扩展 S，此时唯一的开放节点，f = 4.47。松弛它的三条边后，A 变为 g = 3、f = 5.83；B 变为 g = 2、f = 4.83；C 变为 g = 4、f = 9.06。C 已经显得昂贵：它离 S 很近，但方向背离目标。
2. 2. 扩展 B，此时 f 最小为 4.83。它以 g = 8、f = 8.00 到达目标。注意 A* 并不在此停止。找到目标不等于扩展目标，而且此刻还不能断定 8 就是最优。
3. 3. 扩展 A，f = 5.83。它通往 G 的边给出 g = 7，优于经由 B 得到的 8，于是 G 改进为 f = 7.00。
4. 4. 扩展 G，f = 7.00，是开放集中最小的 f。目标已被扩展，其代价就此确定，搜索结束，而 C 仍以 f = 9.06 原封不动地留在开放集中。

A* 返回 S 到 A 到 G，代价为 7，共扩展 4 个节点。Dijkstra 在同一张图上返回完全相同的路径与代价，却要扩展 5 个：它必须先处理完 C，才肯确定目标。C 从来都不值得访问，而 h 正是让 A* 无需检查就知道这一点的原因。

复杂度及其来源

时间: 使用二叉堆时最坏情况 O((V + E) log V) · 空间: O(V)

最坏情况与 Dijkstra 相同，原因也一样：每个顶点最多进入优先队列一次，每条边最多触发一次减键操作，即 V 次取出与 E 次更新，每次 O(log V)。启发函数改变不了这个界，它改变的是常数：f 超过目标最终代价的节点根本不会被扩展。当 h = 0 时，A* 精确退化为 Dijkstra；当 h 完美时，它径直沿最优路径前进。在 4000 张随机生成的带权图上，上述实现平均扩展 4.58 个节点，而 Dijkstra 为 5.52 个，并且每一次都返回了最优代价。

何时使用A* 搜索算法，何时不宜

只有当你既有明确目标、又有可用的距离估计时，A* 额外的机制才值得。缺少其中任何一项，下面某个算法都是更好的工具。

常见陷阱

• 高估的启发函数会破坏最优性. 如果 h 可能超过真实剩余代价，A* 就可能沿着并非最便宜的路线确定目标，而且是悄无声息地发生。只有当直线距离与边权单位相同时它才是可采纳的。用像素距离去对比 1 到 10 的边权，会造成严重高估。
• 可采纳不等于一致. 关闭集的做法假定了一致性，即每条边都满足 h(u) <= w(u, v) + h(v)。可采纳但不一致的启发函数，需要在出现更便宜路线时重新开放节点，否则返回的路径可能不是最优的。
• 一发现目标就停止. 在松弛过程中到达目标什么也证明不了。在上面的轨迹里，B 以代价 8 找到 G，比 A 以 7 找到它早了一步。必须等到目标成为被扩展的那个节点。
• 每次比较都重算 h. 启发函数应当每个节点调用一次，而不是优先队列每比较一次就调用一次。把 h 与 g 一起缓存，决定了这个启发函数是物有所值，还是得不偿失。
• 想当然认为 A* 总是胜过 Dijkstra. 启发函数很弱时，A* 扩展的节点与 Dijkstra 相同，还要额外承担计算 h 的开销。在没有几何信息的图上，h = 0 才是诚实的选择，而 Dijkstra 的实现更简单。

常见问题

f = g + h 到底是什么意思？

g 是到达该节点的路径目前已经花费的代价，这是既成事实。h 是对从这里走到目标还要花多少的估计。二者之和 f 是经过该节点的最便宜完整路线的估计代价，而 A* 总是处理估计值最小的那个节点。

什么样的启发函数才是可采纳的？

它从不高估真实的剩余代价。在平面上移动时直线距离满足这一点，因为没有任何路线能比直线更短。可采纳性正是保证 A* 返回最优路径的条件。

A* 一定比 Dijkstra 快吗？

在同一张图且启发函数一致的前提下，它扩展的节点数绝不会多于 Dijkstra，通常还更少。但它并非渐进意义上更快：两者都是 O((V + E) log V)。收益是一个常数因子，并且随着启发函数趋近于零而消失。

A* 能处理负权边吗？

不能。它继承了让 Dijkstra 成立的那个假设：延长一条路径绝不会让它变得更便宜。当权重可能为负时请使用 Bellman-Ford。

A* 是谁发明的？

斯坦福研究所的 Peter Hart、Nils Nilsson 和 Bertram Raphael，发表于 1968 年的论文《A Formal Basis for the Heuristic Determination of Minimum Cost Paths》。同一批作者在 1972 年的一则说明中修正了最初的最优性论断，区分了可采纳性与一致性。

为什么在这段演示中 A* 跳过了节点 C？

C 的 f = 9.06，而目标在 f = 7.00 时就已确定。因为启发函数从不高估，f = 9.06 就等于承诺任何经过 C 的路线代价都不可能低于 9.06，而这已经比一个 7 的完成答案更差。A* 无需查看就可以将它舍弃。