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。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 展开 S | A:g=2,f=4;B:g=1,f=2 | 估计引导先看 B |
| 展开 B | G:g=7,f=7 | 只是暂定路径 |
| 展开 A | G 改为 g=4,f=4 | 重新加入更好记录 |
| 弹出 G | 返回 4 | 不能在首次发现 G 时就返回 7 |
窄屏可左右滑动表格,阅读完整计算与理由。
启发式可以不完美,但不能将首次发现目标当作最优。
04为什么这个方法成立
- 每个 g 来自真实路径,改善后记录更短前缀。
- 可采纳 h 使最优路径上的未展开前沿 f 不大于真正最优代价。
- 目标被最小 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
h 全为 0 会怎样?
需要一点提示
优先级只剩 g。
查看解析与答案
变成 Dijkstra 的堆式搜索。
为什么发现终点时不马上返回?
需要一点提示
本例先发现代价 7。
查看解析与答案
仍可能有尚未展开的路径改善为 4,应在合法前提下等目标最小优先级弹出。
四邻格允许穿越障碍计算曼哈顿距离,会不会高估?
需要一点提示
忽略障碍只会让路更短。
查看解析与答案
不会,它是忽略障碍后的最短步数下界,因而可采纳;但可能估计较弱。