07 · 启发式与 A*
⏱ 48 分钟 | 阅读参考 · 已经走了多远,再加上还要走多远的估计。
本章可以分两次读:先学会读地图上的g、h、f;想知道“为什么保证最优”,再继续到条件和反例。
🎯 一句话
A* 把已经花掉的代价g,加上剩余代价的估计h,用两者之和f安排候选路线的先后。
$$f(n)=g(n)+h(n)$$
这不是“估得差不多就保证最优”。本页主实验使用不重开的闭集图搜索,需要一致的h作为最优保证;后面会演示正确重开节点后,怎样使用只满足可容许性的h。
在同一张罗马尼亚地图上,UCS得到418公里、展开12次;本页A*也得到418公里、展开5次。少检查了一些分支,但没有改变最小公里数这个目标。
- 先认符号:g、h、f各在说什么。
- 想逐步看选择:6次取出的地图记录。
- 自己写A*前必看:闭集为什么可能挡掉更便宜的路。
🧭 一、启发式函数h是什么
h是对“从当前状态到目标,最便宜还要花多少”的估计。 这样的估计叫启发式,不是已经发生的支出。
| 符号 | 看哪一段 | 本章单位 |
|---|---|---|
| g(n) | 当前候选路径从Arad走到n,已经花了多少 | 公里 |
| h(n) | 从n到Bucharest,还要多少的估计 | 公里 |
| f(n) | 沿这条候选路线继续到目标,总共可能需要多少 | 公里 |
同一个城市可以有不同的候选路径,因此g可能不同。h在本章只根据城市和目标确定。
一个现成估计:到目标的直线距离
如果路的代价是公里数,城市到Bucharest的直线距离可以作为h。我们用 $h_{SLD}$ 表示这张表,SLD是straight-line distance的缩写。
单位必须对齐。 如果想最少花费的是时间,就不能直接把“公里数”加到“分钟数”上。可以在条件成立时用直线距离除以最大可用速度,构造时间下界。
先在两个候选之间选一次
从Arad经Sibiu出来后,RimnicuVilcea的g=220、h=193;Fagaras的g=239、h=178。
贪婪只看h,会选Fagaras;A*看g+h,会先选RimnicuVilcea,因为413小于417。
frontier = [
("RimnicuVilcea", ["Arad", "Sibiu", "RimnicuVilcea"], 220),
("Fagaras", ["Arad", "Sibiu", "Fagaras"], 239),
]
H = {"RimnicuVilcea": 193, "Fagaras": 178}
GREEDY = lambda f: min(range(len(f)), key=lambda i: H[f[i][0]])
ASTAR = lambda f: min(range(len(f)), key=lambda i: f[i][2] + H[f[i][0]])
for name, pick in [("Greedy", GREEDY), ("A*", ASTAR)]:
state, path, g = frontier[pick(frontier)]
print(name, state, "g=", g, "h=", H[state], "f=", g + H[state])
输出中,Greedy选择Fagaras、f=417;A*选择RimnicuVilcea、f=413。这个小程序只演示已有候选的排序,下面才是完整路径搜索。
主实验的搜索版本与计数
- 使用同一张有限地图、非负路长,邻居顺序与第6章一致。
- 贪婪取最小h;A*取最小f。优先级相同时,先入队先取出。
explored是全局集合,已经展开的状态不再展开;这称为本页的不重开版本。expanded只计执行后继生成的非目标节点,不含取出的目标,也不含跳过的重复项。- 主实验的H以Bucharest为目标,目标h=0;H在这张图上满足后面定义的一致性。
直接运行完整实验:不用先读第5、6章
整段复制到空文件即可运行,不需要安装库。先看贪婪与A*两行,再看末尾只改变Pitesti估计的两次对照。
ROMANIA = {
"Arad": [("Zerind", 75), ("Sibiu", 140), ("Timisoara", 118)],
"Zerind": [("Arad", 75), ("Oradea", 71)],
"Oradea": [("Zerind", 71), ("Sibiu", 151)],
"Sibiu": [("Arad", 140), ("Oradea", 151), ("Fagaras", 99), ("RimnicuVilcea", 80)],
"Timisoara": [("Arad", 118), ("Lugoj", 111)],
"Lugoj": [("Timisoara", 111), ("Mehadia", 70)],
"Mehadia": [("Lugoj", 70), ("Dobreta", 75)],
"Dobreta": [("Mehadia", 75), ("Craiova", 120)],
"Craiova": [("Dobreta", 120), ("RimnicuVilcea", 146), ("Pitesti", 138)],
"RimnicuVilcea": [("Sibiu", 80), ("Craiova", 146), ("Pitesti", 97)],
"Fagaras": [("Sibiu", 99), ("Bucharest", 211)],
"Pitesti": [("RimnicuVilcea", 97), ("Craiova", 138), ("Bucharest", 101)],
"Bucharest": [("Fagaras", 211), ("Pitesti", 101), ("Giurgiu", 90), ("Urziceni", 85)],
"Giurgiu": [("Bucharest", 90)],
"Urziceni": [("Bucharest", 85), ("Hirsova", 98), ("Vaslui", 142)],
"Hirsova": [("Urziceni", 98), ("Eforie", 86)],
"Eforie": [("Hirsova", 86)],
"Vaslui": [("Urziceni", 142), ("Iasi", 92)],
"Iasi": [("Vaslui", 92), ("Neamt", 87)],
"Neamt": [("Iasi", 87)],
}
def search(graph, start, goal, pick):
"""有限非负代价图上的不重开版本;A*的保证另依赖h一致。"""
if any(cost < 0 for edges in graph.values() for _, cost in edges):
raise ValueError("本章比较只使用非负边代价")
frontier = [(start, [start], 0)]
explored, expanded = set(), 0
while frontier:
state, path, g = frontier.pop(pick(frontier))
if state == goal:
return path, g, expanded
if state in explored:
continue
explored.add(state)
expanded += 1
for nxt, cost in graph[state]:
if nxt not in explored:
frontier.append((nxt, path + [nxt], g + cost))
return None, None, expanded
H = {"Arad": 366, "Bucharest": 0, "Craiova": 160, "Dobreta": 242, "Eforie": 161,
"Fagaras": 178, "Giurgiu": 77, "Hirsova": 151, "Iasi": 226, "Lugoj": 244,
"Mehadia": 241, "Neamt": 234, "Oradea": 380, "Pitesti": 98,
"RimnicuVilcea": 193, "Sibiu": 253, "Timisoara": 329, "Urziceni": 80,
"Vaslui": 199, "Zerind": 374}
GREEDY = lambda f: min(range(len(f)), key=lambda i: H[f[i][0]])
ASTAR = lambda f: min(range(len(f)), key=lambda i: f[i][2] + H[f[i][0]])
for name, pick in [("Greedy", GREEDY), ("A*", ASTAR)]:
path, cost, expanded = search(ROMANIA, "Arad", "Bucharest", pick)
print(name, "代价=", cost, "展开=", expanded, " -> ".join(path))
for estimate in (100, 150):
changed_h = dict(H, Pitesti=estimate)
pick = lambda f: min(range(len(f)), key=lambda i: f[i][2] + changed_h[f[i][0]])
path, cost, expanded = search(ROMANIA, "Arad", "Bucharest", pick)
print("h(Pitesti)=", estimate, "代价=", cost, "展开=", expanded)
第一组输出:Greedy 450公里、展开3次;A* 418公里、展开5次。两个估计修改的输出分别是 100→418公里/5次,150→450公里/6次,后文会解释为什么不同。
这里仍用列表扫描最小项,方便对照 g、h、g+h。后面独立的重开例子会用最小堆;不把两种实现的执行时间混作同一个基准。
🍰 二、贪婪最佳优先:只看剩余估计
贪婪最佳优先每次从整个frontier里挑h最小的候选。 它不是只在当前节点的孩子中选一个,也不是执行一条动作之后永远无法回头。
本次结果是Arad → Sibiu → Fagaras → Bucharest,450公里,比418多32公里。只展开3次确实少,但这是“较少搜索工作换来较差路线”的一个例子,不是快与慢的普遍排名。
不考虑g,会遗漏什么
Fagaras的剩余估计178,比RimnicuVilcea的193小;但走到Fagaras已经花了239,比走到RimnicuVilcea的220多。
贪婪不把这份已花代价加入排序。即使h是剩余代价的合理下界,只看h也不一般保证总代价最小。
循环例子必须说明搜索版本和目标
以Iasi、Neamt、Fagaras为例,先明确:目标现在是Fagaras,不能继续把前面到Bucharest的直线距离表当成到新目标的距离表。
为了单独演示循环,暂时使用下面的人造h,而不是声称它们是真实地理距离:
| 状态 | 人造h值 |
|---|---|
| Iasi | 3 |
| Neamt | 2 |
| Vaslui | 4 |
| 目标Fagaras | 0 |
罗马尼亚图中,Iasi的邻居是Vaslui与Neamt,Neamt只连回Iasi。不查重复的树搜索会反复选:Iasi生成Neamt,Neamt生成Iasi,再生成Neamt……,因为它们的2或3总排在Vaslui的4前面。
本章带全局 explored 的有限图实现则不会无限重复展开这两个状态;最终会检查其他候选。无限状态空间中,即使防止重复,也可能有无限多个h较小的新状态,使目标一直排不到。
所以应分开记:贪婪不一般最优;其完备性还取决于状态空间和重复处理,不能把树搜索的循环直接套在本页有限图代码上。Poole 与 Mackworth:贪婪最佳优先
⭐ 三、A*:在地图上手算每次选择
这一段只问:此刻队列里,谁的g+h最小? 不需要先背最优性证明。
下面“加入frontier”只列实际通过全局闭集过滤的孩子;返回已展开城市的边仍会被检查,但不会重新入队。
| 次序 | 取出的候选及f | 实际加入frontier的候选:g+h=f |
|---|---|---|
| 1 | Arad,366 | Zerind:75+374=449;Sibiu:140+253=393;Timisoara:118+329=447 |
| 2 | Sibiu,393 | Oradea:291+380=671;Fagaras:239+178=417;RimnicuVilcea:220+193=413 |
| 3 | RimnicuVilcea,413 | Craiova:366+160=526;Pitesti:317+98=415 |
| 4 | Pitesti,415 | Craiova:455+160=615;Bucharest:418+0=418 |
| 5 | Fagaras,417 | Bucharest:450+0=450 |
| 6 | Bucharest,418 | 是目标,返回;不计作展开 |
结果是Arad → Sibiu → RimnicuVilcea → Pitesti → Bucharest:418公里,5次非目标展开。
哪些返回边被闭集过滤,没有加入队列
这些算术仍可用来检查每一步,但父状态已经在闭集中,所以并未真正加入本代码的frontier。
| 在哪里考察到 | 返回已展开城市的候选g+h=f |
|---|---|
| Sibiu | Arad:280+366=646 |
| RimnicuVilcea | Sibiu:300+253=553 |
| Pitesti | RimnicuVilcea:414+193=607 |
| Fagaras | Sibiu:338+253=591 |
考察邻居不等于入队,入队不等于展开。 使用不查重复的树搜索时,这些候选可能留在队列;不能把那种树图的所有孩子说成本代码都已入队。
看懂这三件事,就能读懂整张表
① 第4次之后已经看见目标,仍不能立刻停。 Bucharest的候选代价418已经入队,但Fagaras的f=417更小。按当前估计,那个分支仍可能通向更便宜的路线,要先检查。
② 同一状态确实可以有两个候选。 第5次生成另一个Bucharest,g=450。目标状态相同,路线与总代价不同;最后返回的是418那个。
③ 先展开Fagaras不等于会“上当”。 将h(Pitesti)从98改为100时,它的f变为417,与Fagaras并列;由于Fagaras更早入队,会先展开它。但随后仍会检查Pitesti,最终返回418。
这次安全不是因为Pitesti“恰好抢先2”。正确的下界、重复处理和目标终止条件,才让算法不会因为先看到一条450的路线就直接接受它。
🧮 四、可容许性:估计不能高估
可容许h给的是剩余代价的下界:允许估少,不允许估多。 本章采用非负估计的约定。
$$0\le h(n)\le h^*(n)$$
- $h(n)$:算法现在采用的估计。
- $h^*(n)$:从n到目标的真实最小代价。
- 在目标处,已经不用再走,因此 h(goal)=0。
为什么直线距离可以
本章优化的是公里数,允许的公路路线不会比同一对地点间的直线更短。因此到目标的直线距离是不高估的估计。
例如Fagaras到Bucharest:h=178,而最短公路代价为211;Pitesti的h=98,而最短公路代价为101。
这两个例子帮助理解;要声称整张表可容许,条件必须对所有相关状态成立,而不是只验两个点。若目标改了,h也要对应新目标。Berkeley CS188:可容许与目标估计
高估在这里确实会返回错路
若把h(Pitesti)改成150,它的f就从415变为 317+150=467。Fagaras会生成代价450的目标候选,而该目标会在Pitesti之前被取出。
前面的独立实验返回450公里,错过418公里。这证明本次高估会破坏结果,不是说任意一点高估都必然在每个实例上出错。
为什么把h(goal)=0也写出来,不只写“不高估”
如果只写h≤h*而允许任意负值,就可能把目标估成-100。假设S→G代价3,另一条S→A→G代价1+1;将h(S)=0、h(A)=1、h(G)=-100,直达G的f=-97会被先取出,返回3而非2。
这些h都满足“没有超过真实剩余代价”这个单独上界,却不满足本章的非负、目标0约定。最优性证明使用f(goal)=g(goal),必须说明这个前提。
📐 五、A*为什么能返回最优路线
先限定这段证明的使用范围:h可容许、目标h=0,而且不会把最优路线上的正确候选错误剪掉。
不查重复的A*树搜索保留这些候选;本页主实验通过“一致h”保证永久闭集不误删;稍后的可重开版本则允许更优g重新进入搜索。
还要有找到解的终止条件。对无限空间,有限分支和正的单步代价下界是一组常见充分条件;不能仅凭可容许就忽略无限搜索的可能。
一句话的理由
还有一条可能更便宜的路线等着检查时,较贵的目标就不是f最小的候选。
把这句话写成四行不等式
令G表示总代价最小的目标路径,G2表示某条更贵的目标路径。最优路径还没走完时,在它上面取一个仍在frontier中的正确前缀节点n。
| 关系 | 为什么成立 |
|---|---|
| $f(G_2)=g(G_2)$ | 目标的h是0 |
| $g(G_2)>g(G)$ | G2比最优路线更贵 |
| $g(G)=g(n)+h^*(n)$ | n携带的是这条最优路线的前缀代价 |
| $g(n)+h^*(n)\ge g(n)+h(n)=f(n)$ | h可容许,不高估剩余代价 |
合起来,$f(G_2)>f(n)$,所以不会先取出G2并把它作为答案。继续这个过程,先返回的是某条最优目标路径。
这里的关键不只是最后一个不等式:正确的前缀n必须仍有机会被搜索到。 下一节正好展示永久闭集如何把它误删。
更精确地说,次优目标候选可以被生成,但在这些条件下不会先被取出作为返回结果。 地图里450公里的Bucharest就是这样的候选。
本页代码对任何目标都直接返回、不生成它的孩子;因此这里刻意区分“取出并返回”和计数器里的“展开”。
🔺 六、一致性:防止永久闭集挡掉好路线
一致性要求:直接估计的剩余代价,不比“先走一条边,再从邻居估计”更大。 本章继续采用非负h、目标h=0的约定。
$$h(n)\le c(n,n')+h(n')$$
- $c(n,n')$是从n到邻居n′这条边的实际代价。
- 这条不等式要对每条有向边都成立,而不是只挑一条方便的边。
以RimnicuVilcea→Pitesti为例:193≤97+98=195。直线距离满足三角不等式,且道路长度不短于两地直线,因此这张h表是一致的。
它带来两个结果
- 一致推出可容许:沿通向目标的路径连续使用这条不等式,最后h(goal)=0,得到h不超过这条路径的代价;最便宜的路径也一样。
- 沿一条候选路径,f不下降:走一步增加的实际代价,至少补上h可能下降的那部分。A*首次取出某个状态时,可以保证该候选的g已是到该状态的最小代价,于是永久关闭它是安全的。
可容许只比较“到终点的总下界”;一致还检查“每一步之间是否协调”。所以可容许不自动推出一致。Poole 与 Mackworth:一致性与多路径剪枝
⚠️ 可容许但不一致:不重开版本确实会出错
看一个四节点例子。目标是G,边代价如下:
| 边 | 代价 |
|---|---|
| S→A | 2 |
| S→B | 4 |
| A→B | 1 |
| B→G | 4 |
| 状态 | h | 真实最小剩余代价h* |
|---|---|---|
| S | 0 | 7 |
| A | 5 | 5 |
| B | 1 | 4 |
| G | 0 | 0 |
每行h都没有高估,所以可容许。但在A→B上,5>1+1,所以不一致。
不重开,会发生什么
| 步骤 | 发生的事 |
|---|---|
| 1 | 展开S:A的g=2、f=7;B的g=4、f=5 |
| 2 | 先展开B,把它放入闭集;生成G,g=8、f=8 |
| 3 | 展开A,发现经A到B只需g=3;但B已关闭,这条更便宜的候选被丢弃 |
| 4 | 取出G,返回8 |
真正最优路线是 S→A→B→G,2+1+4=7。返回8看起来能走通,却贵了约14.3%。错在“永久不再考虑B”这个决定,而不是算术或路径合法性。
两个修法,分别解决什么
- 要求h一致:第一次展开状态时g已最优,不再需要后来用更低g重开它。这是本页罗马尼亚主实验的保证方式。
- 发现更低g时允许重开:记录到各状态的当前最佳g;发现严格更小的g就更新并重新入队;旧的较贵候选取出时跳过。这能保住被更便宜路线改善的状态。
独立运行同一反例:不重开得8,重开得7
这个小程序用最小堆取f最小项;递增序号保证同f时FIFO。reopen=False只用于展示不一致h加永久闭集的失败。
from heapq import heappop, heappush
from itertools import count
GRAPH = {"S": [("A", 2), ("B", 4)], "A": [("B", 1)], "B": [("G", 4)], "G": []}
H = {"S": 0, "A": 5, "B": 1, "G": 0}
def astar(graph, start, goal, h, reopen=True):
if any(cost < 0 for edges in graph.values() for _, cost in edges):
raise ValueError("这个例子只处理非负边代价")
if h[goal] != 0 or any(value < 0 for value in h.values()):
raise ValueError("这个例子要求非负h,且目标h=0")
serial = count()
frontier = [(h[start], next(serial), start, 0, [start])]
best_g, closed, expanded = {start: 0}, set(), []
while frontier:
_, _, state, g, path = heappop(frontier)
if g != best_g[state]:
continue
if state == goal:
return path, g, expanded
if not reopen and state in closed:
continue
closed.add(state)
expanded.append((state, g))
for nxt, cost in graph[state]:
if not reopen and nxt in closed:
continue
new_g = g + cost
if new_g < best_g.get(nxt, float("inf")):
best_g[nxt] = new_g
heappush(frontier, (new_g + h[nxt], next(serial), nxt, new_g, path + [nxt]))
return None, None, expanded
for reopen in (False, True):
path, cost, expanded = astar(GRAPH, "S", "G", H, reopen=reopen)
print("重开=", reopen, "代价=", cost, "路径=", path)
print("非目标展开记录:", expanded)
不重开:返回8,展开S、B(g=4)、A。
允许重开:返回7,展开S、B(g=4)、A、B(g=3)。第二次展开B是必要的改善,不应因为“一个状态展开了两遍”就视为错误。
输入检查没有自动证明h可容许。这里之所以能保证可重开版本的最优性,是因为表中给出了真实h*供核对,且小图满足相应搜索条件;不能把任意模型预测当作已证明的下界。
记住真正的分界:不重开版本用一致性保护闭集;正确重开的版本可以在相应条件下使用可容许但不一致的h。 不能把“所有图搜索都必须一致”当作不可变规则。
📊 七、A*的性质,与低内存的IDA*
先看保证,不背绝对口号
| 问题 | 有条件的结论 |
|---|---|
| 一定找到解吗 | 本章有限图正确处理重复状态时,可以找到可达目标;无限空间还需排除无限低f候选等情况 |
| 找到的一定最便宜吗 | 需要可容许h、目标0和正确重复处理;不重开版本以一致性作为保证 |
| 一定很快吗 | 不保证;h较弱、存在很多等f候选或生成后继很贵,都可能需要大量时间 |
| 内存花在哪里 | frontier、最佳g/闭集、路径或父指针等记录;它们可能很大,并非所有生成过的对象都必须永久保留 |
更准确的h常有助于排除不可能更好的候选,但搜索规模还受图结构、并列规则和重复状态影响。不能只用“相对误差×解长”给所有A*问题统一套一个指数时间公式。
A*可能同时受时间和内存限制。内存是重要瓶颈,不是“只会OOM,绝不会慢”的唯一死因。
贪婪的指数数量级,在哪个模型下使用
若搜索树的最大深度为有限的m、分支上界为b,并把处理定长节点视为常数工作,贪婪最坏可能检查$O(b^m)$个节点,frontier空间也可能达到$O(b^m)$数量级。
这说明贪婪没有一般的高效保证,不是说它在每个实例上都会检查这么多。带全局去重的有限图可按顶点/边数量另行分析;本页列表扫描、堆操作与路径复制也都有额外成本。
A*的下界可以排除部分候选,但最坏搜索规模仍可能随解深度指数增长。比较启发式时,还要固定并列规则与是否重开,不能只换h后把不同实现的计数直接相除。
IDA*:把深度门槛换成f门槛
IDA*用多轮深度优先探索降低搜索记录的内存占用。 它与第6章IDS的区别在于截止标准。
- 首轮门槛设为f(start)=h(start),因为起点g=0;从起点开始深度优先检查候选。
- 先检查f是否超过门槛。超过就截止这条分支;没有超过,才检查是否目标,或继续检查后继。
- 本轮没有找到解,但有被门槛挡住的候选,就把下轮门槛提高到“本轮被挡住的最小f”,再从起点搜索。
- 找到未越界的目标就返回;若本轮既没有解,也没有被挡住的候选,就已穷尽可继续的路线,可报告无解。
初始门槛与检查顺序不是任意设置:若第一轮就给一个过大的门槛,深度优先找到的第一条路线未必最便宜。逐轮使用最小越界f,是为了不跳过仍可能包含更便宜解的搜索范围。JAIR研究论文:IDA*的门槛更新与空间
一组明确的充分条件是:分支有限、每步代价至少为固定的$\epsilon>0$、h非负可容许且目标h=0。存在解时,按上述规则增加门槛的IDA*能找到最小代价解;正确的路径防环可以避免环上的重复候选。
省掉的是搜索记录,不是所有内存
理想深度优先实现只保留当前路径、各层迭代信息,搜索空间随深度线性增长;如果另外加载大型模式数据库,那张表的内存必须另外计算。
代价是重复计算。只有在各轮工作量增长够快、最后一轮占主导等条件下,前面轮次才主要增加常数倍开销。 状态数很多,并不单独保证IDA*和带全局去重的A*一样快;重复制状态、缓慢增加的f阈值和昂贵h都可能让它慢得多。Poole 与 Mackworth:深度优先搜索与全局去重的取舍
下一章的模式数据库会用离线计算改善h;它和低内存搜索可以搭配,但不存在“免费、更准、又总是更快”的保证。
🔗 这一章连到哪里
| 去哪 | 带着什么区别去看 |
|---|---|
| 强化学习基础 03 · 价值函数与贝尔曼方程 | h常估计到目标的剩余代价;V描述策略下或最优策略下的期望回报。比较时需统一代价/回报符号、折扣与转移条件,不按“手写或学习”简单划分;学习得到的h也不自动可容许。 |
| 强化学习基础 07 · 探索与利用 | 贪婪搜索是在已给定图中安排候选顺序;强化学习探索是在收集未知环境反馈。二者都要警惕不可靠估计,但问题和修法不完全一样。 |
| 代码题拆解 04 · 二分、排序与堆 | 本页主实验用列表扫描最小f,反例代码用heapq。去那里理解最小堆怎样减少取最小候选的开销,以及为什么还要考虑并列和过期项。 |
✅ 检查点
- 贪婪如何排序?本次地图中展开多少、走多少公里、比最优多多少?为什么不能把树搜索的循环结论直接套给有限图闭集实现?
- A*的g、h、f分别是什么?为什么单位要相同?本次A*与UCS分别展开多少次,路径长度是否相同?
- Bucharest的418候选已经生成,为何还检查Fagaras的417候选?同一Bucharest为何还能有450候选?若两者前驱改变取出顺序,是否必定返回错路?
- 什么叫本章的可容许h?目标处取多少?直线距离为什么适用于公里代价?把h(Pitesti)改为150,在本例中发生什么?
- 最优性证明中的n是什么?哪里用到可容许?为什么还必须保证正确的最优前缀没有被剪掉?
- 一致性检查什么,和可容许有什么关系?原四节点例不重开返回多少、最优多少,哪个操作挡住了更便宜的路线?
- 不重开与正确重开版本对h的保证条件有何不同?A*的时间/内存问题是什么,IDA*省掉什么、又付出什么?
对照答案:先对条件,再对结果
- 按h最小排序。本次展开3次、450公里,比418多32公里。不查重复的树搜索能反复生成环上的新节点;有限图全局去重会阻止重复展开,不能说它也必然无限循环。贪婪仍不一般保证最小代价。
- g是当前候选已花代价,h是剩余代价估计,f=g+h是经该候选到目标的总估计,必须使用可相加的同一单位。本次A*展开5次,UCS12次,均返回418公里。
- 417仍低于418,存在更便宜路线的可能;不能生成目标就停。相同状态可由不同路线到达,所以有g=418与450两个候选。先展开Fagaras不等于出错;h(Pitesti)=100时它先展开,仍返回418。
- 对相关状态有$0\le h\le h^*$,目标h=0。公路长度不短于两地直线,因此公里单位下直线距离是下界。改成150使Pitesti的f=467;本次450的目标先被取出,错过418。高估不等于每个实例必错,但失去一般保证。
- n是最优路径上仍可搜索、携带正确前缀代价的候选;最后一步用$h(n)\le h^*(n)$。若错误闭集已删掉该候选,队列里“总有一个这样的n”就未必成立。结论是次优目标可被生成,但不会在满足条件时先被返回。
- 一致要求每条边满足$h(n)\le c(n,n')+h(n')$;在本章目标0约定下,一致推出可容许,反之不成立。反例不重开返回8,最优是7;B先以g=4关闭,使后来A带来的g=3被拒绝。
- 不重开版本以一致h保证安全关闭;正确记录best_g、改善时重开并跳过过期项的版本,在相应搜索条件下可使用可容许但不一致的h。A*可能耗时也耗内存;IDA*降低搜索记录空间,但重复探索,额外PDB内存也不会消失。
本节回顾
走神救援:先记这四点。
- A*按g+h排序,既看已经花掉的,也看剩余估计。
- 可容许是剩余代价下界;本章约定非负、目标0。
- 永久闭集需要安全依据;正确重开能保留后来发现的更低g。
- 生成目标不等于可以停止;少展开也不等于一定更快或更省全部内存。
下一节 👉 08-启发式怎么设计.md