专题进阶 · 图算法推荐总顺序 · 第 59 / 148 课

将已走代价 g 与剩余估计 h 分开,理解可采纳性、一致性与重新展开。

先学会这些,再进入本课 Dijkstra 优先队列
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 图算法

A* 搜索A* Search

以 g+h 选择候选;启发式的可采纳性与一致性影响最优性和重复展开处理。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

将已走代价 g 与剩余估计 h 分开,理解可采纳性、一致性与重新展开。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

在有障碍的网格中找从起点到终点的最短路径。普通 Dijkstra 向四面扩散,怎样让搜索更有方向?

02一步步得到方法

估计只负责安排优先顺序

g(v) 是目前找到的起点到 v 的真实路径代价,h(v) 是 v 到终点的估计,优先级 f=g+h。h 不能随意当作真实距离加进最终答案,答案仍由 g 记录。

可采纳要求 h 不超过真实剩余最短代价,且目标 h=0。一致性进一步要求 h(u)≤w(u,v)+h(v)。四邻网格、每步成本 1 时,曼哈顿距离满足这两个条件;若允许廉价对角移动,这个估计可能过大。

不要永久关闭仍可能改善的节点

一致启发式可支持节点出队后永久关闭。若只保证可采纳而不一致,需要允许更短 g 到来时重新入队。本代码不设永久 closed,而是用过期距离检查跳过旧记录,支持重新展开。

在可采纳、目标估计为零、非负边权等前提下,目标以当前最小 f 弹出时,其 g 已最优。h=0 时算法退化为 Dijkstra;启发式强弱决定实际扩展量,不能承诺总是更快。

优先值不是已走距离

A* 用 f=g+h 排序,g 是已经付出的真实代价,h 是剩余代价估计。若把 h 当作已走距离累加,会重复计算估计量,破坏最短路语义。

一致启发式满足 h(u)≤w(u,v)+h(v),使 f 沿路径不下降;只有可采纳而不一致时,已经扩展的点可能需要重新打开。本课保留最佳 g 并跳过过期记录,而不永久锁死首次发现路径。

03把一个小例子完全算清楚

路径 S→A:2、A→G:2、S→B:1、B→G:6;h(S)=3,h(A)=2,h(B)=1,h(G)=0。

步骤计算与状态为什么这样做
展开 SA:g=2,f=4;B:g=1,f=2估计引导先看 B
展开 BG:g=7,f=7只是暂定路径
展开 AG 改为 g=4,f=4重新加入更好记录
弹出 G返回 4不能在首次发现 G 时就返回 7

窄屏可左右滑动表格,阅读完整计算与理由。

启发式可以不完美,但不能将首次发现目标当作最优。

04为什么这个方法成立

  1. 每个 g 来自真实路径,改善后记录更短前缀。
  2. 可采纳 h 使最优路径上的未展开前沿 f 不大于真正最优代价。
  3. 目标被最小 f 弹出时 g=f,不可能比仍隐藏的最优路径更差;不一致时需要保留重新展开能力。

05把推导翻译成代码

Python · 可独立运行的教学实现

import heapq
def astar(adj, start, goal, h):
    best = {start: 0}
    queue = [(h[start], 0, start)]
    while queue:
        estimate, g, u = heapq.heappop(queue)
        if g != best.get(u):
            continue
        if u == goal:
            return g
        for v,weight in adj.get(u, []):
            assert weight >= 0
            candidate = g + weight
            if candidate < best.get(v, float("inf")):
                best[v] = candidate
                heapq.heappush(queue, (candidate+h[v], candidate, v))
    return float("inf")

逐个理解关键决定

g != best.get(u)
较差旧记录可能仍留在堆里,弹出时忽略。
candidate+h[v]
f 只作优先级,真实距离仍为 candidate。

06时间、空间与实现范围

一致启发式和常见堆实现下,可按边松弛分析为 O((V+E)log(V+E)) 上界;实际常更少展开。

仅可采纳且不一致时可能多次重新展开,不能沿用每点一次的界。本代码节点为可比较编号,图有限且边权非负。

07改变条件,检查哪里会出错

高估距离也声称必得最短路

高估可能跳过真正更好的方向,必须重新说明是否接受近似解。

在目标首次入队时立即返回

目标第一次被发现未必通过最优路径,应按算法条件在合适的出队时机结束。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

h 全为 0 会怎样?

需要一点提示

优先级只剩 g。

查看解析与答案

变成 Dijkstra 的堆式搜索。

练习 2 · 边界与辨析

为什么发现终点时不马上返回?

需要一点提示

本例先发现代价 7。

查看解析与答案

仍可能有尚未展开的路径改善为 4,应在合法前提下等目标最小优先级弹出。

练习 3 · 变式与迁移

四邻格允许穿越障碍计算曼哈顿距离,会不会高估?

需要一点提示

忽略障碍只会让路更短。

查看解析与答案

不会,它是忽略障碍后的最短步数下界,因而可采纳;但可能估计较弱。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 图算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。