🏠 总目录📚 本教程 07 · 启发式与 A* ← →

A* 的估计要满足什么条件,才能保住最优路线?

读后可检查:手算 g+h 的选择,并区分可容许性、一致性与闭集处理的作用。

📑 本页目录(点开跳转)

07 · 启发式与 A*

⏱ 48 分钟 | 阅读参考 · 已经走了多远,再加上还要走多远的估计。

本章可以分两次读:先学会读地图上的g、h、f;想知道“为什么保证最优”,再继续到条件和反例。


🎯 一句话

A* 把已经花掉的代价g,加上剩余代价的估计h,用两者之和f安排候选路线的先后。

$$f(n)=g(n)+h(n)$$

这不是“估得差不多就保证最优”。本页主实验使用不重开的闭集图搜索,需要一致的h作为最优保证;后面会演示正确重开节点后,怎样使用只满足可容许性的h。

在同一张罗马尼亚地图上,UCS得到418公里、展开12次;本页A*也得到418公里、展开5次。少检查了一些分支,但没有改变最小公里数这个目标。


🧭 一、启发式函数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重新进入搜索。

还要有找到解的终止条件。对无限空间,有限分支和正的单步代价下界是一组常见充分条件;不能仅凭可容许就忽略无限搜索的可能。

次优目标G2为什么不会先于最优目标被取出并返回 起点 n G G2 最优路径的前半段 剩下的最优路径 某条次优的解 还在队列里没展开 最优目标 次优目标
看绿色路径上的n:在候选未被错误剪掉、h可容许且目标h=0时,它的f不超过最优代价,因此排在次优目标G2前面。

一句话的理由

还有一条可能更便宜的路线等着检查时,较贵的目标就不是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表是一致的。

它带来两个结果

  1. 一致推出可容许:沿通向目标的路径连续使用这条不等式,最后h(goal)=0,得到h不超过这条路径的代价;最便宜的路径也一样。
  2. 沿一条候选路径,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的区别在于截止标准。

  1. 首轮门槛设为f(start)=h(start),因为起点g=0;从起点开始深度优先检查候选。
  2. 先检查f是否超过门槛。超过就截止这条分支;没有超过,才检查是否目标,或继续检查后继。
  3. 本轮没有找到解,但有被门槛挡住的候选,就把下轮门槛提高到“本轮被挡住的最小f”,再从起点搜索。
  4. 找到未越界的目标就返回;若本轮既没有解,也没有被挡住的候选,就已穷尽可继续的路线,可报告无解。

初始门槛与检查顺序不是任意设置:若第一轮就给一个过大的门槛,深度优先找到的第一条路线未必最便宜。逐轮使用最小越界f,是为了不跳过仍可能包含更便宜解的搜索范围。JAIR研究论文:IDA*的门槛更新与空间

一组明确的充分条件是:分支有限、每步代价至少为固定的$\epsilon>0$、h非负可容许且目标h=0。存在解时,按上述规则增加门槛的IDA*能找到最小代价解;正确的路径防环可以避免环上的重复候选。

省掉的是搜索记录,不是所有内存

理想深度优先实现只保留当前路径、各层迭代信息,搜索空间随深度线性增长;如果另外加载大型模式数据库,那张表的内存必须另外计算。

代价是重复计算。只有在各轮工作量增长够快、最后一轮占主导等条件下,前面轮次才主要增加常数倍开销。 状态数很多,并不单独保证IDA*和带全局去重的A*一样快;重复制状态、缓慢增加的f阈值和昂贵h都可能让它慢得多。Poole 与 Mackworth:深度优先搜索与全局去重的取舍

下一章的模式数据库会用离线计算改善h;它和低内存搜索可以搭配,但不存在“免费、更准、又总是更快”的保证。


🔗 这一章连到哪里

去哪 带着什么区别去看
强化学习基础 03 · 价值函数与贝尔曼方程 h常估计到目标的剩余代价;V描述策略下或最优策略下的期望回报。比较时需统一代价/回报符号、折扣与转移条件,不按“手写或学习”简单划分;学习得到的h也不自动可容许。
强化学习基础 07 · 探索与利用 贪婪搜索是在已给定图中安排候选顺序;强化学习探索是在收集未知环境反馈。二者都要警惕不可靠估计,但问题和修法不完全一样。
代码题拆解 04 · 二分、排序与堆 本页主实验用列表扫描最小f,反例代码用heapq。去那里理解最小堆怎样减少取最小候选的开销,以及为什么还要考虑并列和过期项。

✅ 检查点

  1. 贪婪如何排序?本次地图中展开多少、走多少公里、比最优多多少?为什么不能把树搜索的循环结论直接套给有限图闭集实现?
  2. A*的g、h、f分别是什么?为什么单位要相同?本次A*与UCS分别展开多少次,路径长度是否相同?
  3. Bucharest的418候选已经生成,为何还检查Fagaras的417候选?同一Bucharest为何还能有450候选?若两者前驱改变取出顺序,是否必定返回错路?
  4. 什么叫本章的可容许h?目标处取多少?直线距离为什么适用于公里代价?把h(Pitesti)改为150,在本例中发生什么?
  5. 最优性证明中的n是什么?哪里用到可容许?为什么还必须保证正确的最优前缀没有被剪掉?
  6. 一致性检查什么,和可容许有什么关系?原四节点例不重开返回多少、最优多少,哪个操作挡住了更便宜的路线?
  7. 不重开与正确重开版本对h的保证条件有何不同?A*的时间/内存问题是什么,IDA*省掉什么、又付出什么?
对照答案:先对条件,再对结果
  1. 按h最小排序。本次展开3次、450公里,比418多32公里。不查重复的树搜索能反复生成环上的新节点;有限图全局去重会阻止重复展开,不能说它也必然无限循环。贪婪仍不一般保证最小代价。
  2. g是当前候选已花代价,h是剩余代价估计,f=g+h是经该候选到目标的总估计,必须使用可相加的同一单位。本次A*展开5次,UCS12次,均返回418公里。
  3. 417仍低于418,存在更便宜路线的可能;不能生成目标就停。相同状态可由不同路线到达,所以有g=418与450两个候选。先展开Fagaras不等于出错;h(Pitesti)=100时它先展开,仍返回418。
  4. 对相关状态有$0\le h\le h^*$,目标h=0。公路长度不短于两地直线,因此公里单位下直线距离是下界。改成150使Pitesti的f=467;本次450的目标先被取出,错过418。高估不等于每个实例必错,但失去一般保证。
  5. n是最优路径上仍可搜索、携带正确前缀代价的候选;最后一步用$h(n)\le h^*(n)$。若错误闭集已删掉该候选,队列里“总有一个这样的n”就未必成立。结论是次优目标可被生成,但不会在满足条件时先被返回。
  6. 一致要求每条边满足$h(n)\le c(n,n')+h(n')$;在本章目标0约定下,一致推出可容许,反之不成立。反例不重开返回8,最优是7;B先以g=4关闭,使后来A带来的g=3被拒绝。
  7. 不重开版本以一致h保证安全关闭;正确记录best_g、改善时重开并跳过过期项的版本,在相应搜索条件下可使用可容许但不一致的h。A*可能耗时也耗内存;IDA*降低搜索记录空间,但重复探索,额外PDB内存也不会消失。

本节回顾

走神救援:先记这四点。

  • A*按g+h排序,既看已经花掉的,也看剩余估计。
  • 可容许是剩余代价下界;本章约定非负、目标0。
  • 永久闭集需要安全依据;正确重开能保留后来发现的更低g。
  • 生成目标不等于可以停止;少展开也不等于一定更快或更省全部内存。

下一节 👉 08-启发式怎么设计.md

打卡记录保存在你的浏览器里,首页能看到总进度