CSCI3230 L10 · Part 3/4 A-star search

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2025T1 本讲：L10，第 3 部分 / 共 4 部分 · 原件 L10-Informed-Search-2025T1.pdf（本地课件） p.26–45 定位：兼顾已走成本和未来下界，保护更便宜的候选路径。前后：上一份 Greedy best-first search · 下一份 Summary

版本边界：本篇依据2025T1旧课件作预习与基础补课，不表示2026T1已经讲到这里；今年范围以今年教师公告为准。页码均为原PDF页号。

A*的计算与保证

把已经付的与预计还要付的接起来（p.26–28）

p.26为分节页。贪心只看剩下多远，可能为了最后1公里先绕100公里；UCS只看已经走多远，又可能盲目向四面扩张。A*把两种信息放在一个分数里：

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

$n$ 是一个带有到达路径的搜索节点； $g(n)$ 是该路径已经付出的精确成本； $h(n)$ 是从当前状态到目标的剩余成本估计； $f(n)$ 是经当前路径继续到目标的估计总成本。三者均为标量且单位相同。精确的是当前路径的g，不是说它已经是到该状态的全局最小成本。

补充算一遍：A已花9、估剩1，分数10；B已花2、估剩5，分数7，所以先B。这不是只因B离起点近，也不是只因B离终点近，而是总预算更有希望。

p.28对照三种排序：UCS用g，贪心用h，A用g+h。把所有h设0，A直接变UCS；要再等同BFS，还需要等步成本与相容的平局约定。

课件有向小图：每个数字属于哪里（p.29–31）

图（p.29–31）：有向边S→a为1，a→b为1，b→c为1，a→d为3，a→e为8，e→d为1，d→G为2。启发为S6、a5、b6、c7、d2、e1、G0。看什么：节点旁h与边上成本不是一回事；e→d不能倒过来当d→e。

先根S： $g=0,h=6,f=6$ 。取S生成a， $g(a)=0+1=1$ ；a的h从图读取5，所以 $f(a)=1+5=6$ 。取a后逐项计算：

后继	累计g的来源	图给h	相加得到f
b	1+1=2	6	8
d	1+3=4	2	6
e	1+8=9	1	10

因此选d，不是选g最小的b，也不是选h最小的e。课件p.31正文把h(d)+g(d)写成4+2，而图明确h(d)=2、g(d)=4；总和6没变，但符号对应要纠正。

完整frontier与正确停止点（p.32）

下表括号顺序一律为(g,h,f)，frontier按f从小到大。

取出	新生成	处理后frontier
—	起点	[S(0,6,6)]
S	a(1,5,6)	[a(1,5,6)]
a	b/d/e三条路径	[d(4,2,6),b(2,6,8),e(9,1,10)]
d	到G成本4+2=6	[G(6,0,6),b(2,6,8),e(9,1,10)]
G	目标取出，停止	b/e留待处理但已无需继续

恢复父链S→a→d→G，成本1+3+2=6。b的g虽然只有2，但估计未来还要6，分数8；e未来估计1，却已经花9，分数10。表中两个未取出的候选解释了A*为何没有把它们丢掉：如果新信息改变成本，它们还可能有用。

不要在生成目标的瞬间无条件停止。与UCS相同，生成只能说明找到一条可行路；适当条件下的最优性保证来自目标按最小f被取出时。

“乐观”具体是哪一个不等式（p.33–34）

定义 $h^{\ast}(n)$ 为从状态n到最近目标的真实最低剩余成本。**可采纳（admissible）**要求

0\le h(n)\le h^{\ast}(n).

左边保证不报负的剩余成本；右边保证不高估。“乐观”就是认为所需花费不比实际最低价多。它不是说h越小越准确：真实余程10，估0和估8都不高估，但8信息更多。

给定一条到n的路径， $g(n)$ 已经付出，不是估计；所以两边同时加同一个g，得到

g(n)+h(n)\le g(n)+h^{\ast}(n).

左边f是“沿这条已走路径继续”的乐观预算，右边是在这条前缀固定后，最佳继续方式的真实成本。它不等于所有到目标路径的全局下界：若当前前缀已经绕远，f也可以大于全局最优解。

直线距离在道路成本为长度时可做下界，因为绕路不会短于直线。p.33的煎饼图则必须核对动作成本；单位翻转成本下“最大错位编号”未必是下界，详见Part 1。不要因例子出现在定义旁就跳过条件。

两个安全估计怎样合并（p.35）

若对每个状态都满足 $h_1(n)\ge h_2(n)$ ，说 $h_1$ 支配 $h_2$ ：在都不高估的前提下，前者下界至少一样紧。这是对所有状态的关系，不是只在一个节点比较两个数。

若两者各有擅长位置，取

h(n)=\max\{h_1(n),h_2(n)\}.

因为两者都不超过真实余程，选其中较大的也不会超过；同时它自然不小于任一个。补充取真实余程10，两个下界6和8，max为8仍安全；相加却成14，破坏不高估。若另一状态两估计为9和7，则max自动改选9，不必全图只选同一个函数。

信息更强常减少需要扩展的候选，但计算h本身也可能更贵；相同分数时的顺序也会影响工作量，所以不能把“更强”直接等同每次实际运行都更快。

有限预算内不能塞进无限多节点（p.36–37）

p.36有状态0、1、2、3……，0另可直接到目标G，成本2；链上相邻边依次为1、1/2、1/4、1/8……，全部h为0。走一、二、三、四步后，成本分别1、1.5、1.75、1.875，始终小于2。因此目标G2一直排在链上新节点之后，有限时间内轮不到它。

每条边都正，为何还不够？因为正数越来越小，没有统一正下界。p.37采用有限分支、每动作至少某个固定 $\epsilon>0$ 的条件，排除无限廉价前缀；结合可采纳非负h和有限成本解，可保证A*最终轮到目标。p.36末句写“0 to S”，按该页目标定义应为“0到G”。

最优性证明，先用预算直觉读（p.38–40）

假设一个次优目标B已经在frontier，成本12；另有最优路线总成本10。最优路线还没完成，但在它上面一定还有一个尚待处理的前沿n——否则就已经全部走到最优目标了。

沿最优路线到n已付4，最佳剩下6。可采纳h至多6，所以n的f至多10，而次优目标B的h为0，f就是12。算法每次取最小f，不可能越过n先取B。展开n后，把这个“仍有希望不超过10”的保证传给最优路上的后续前沿，就最终到达最优目标。

把相同思路写成通用符号：令 $C^{\ast}$ 为最优目标成本，B是严格更贵目标，则

\begin{aligned} f(n)&=g(n)+h(n)\\ &\le g(n)+h^{\ast}(n)\\ &=C^{\ast}\\ &<g(B)=f(B). \end{aligned}

第一步是定义；第二步用不高估；第三步要求n位于最优路径且保留了正确的路径前缀；第四步用B是次优目标及目标h为0。每个理由都不可省，尤其第三步不是任意候选都满足。

p.38–41原证明的字母对应也可逐条核对：A为最优目标，B为严格次优目标，n为A路径上尚在fringe的祖先。于是 $f(n)=g(n)+h(n)\le g(A)=f(A)<f(B)$ ；中间的 $g(A)=f(A)$ 与最后对B的比较都用到目标启发为0。图中的灰色区域表示已经探索的部分，n位于尚待展开的边界；红色圈分别强调n与A、A与B以及最终n与B的排序关系。

图搜索为什么还要关心重新打开（p.41与补充）

p.41完成上述证明。树搜索保留不同路径，自然保留最优路径前沿；图搜索为了省事合并同一状态，若合并规则错误，可能把证明需要的便宜路径扔掉。

**一致性（consistency，补充）**要求每条合法边满足

h(n)\le c(n,n')+h(n').

意思是：“我现在的余程估计”不能比“走这一步的真实成本，加上下一站的余程估计”还大。它使沿路的f不下降：用 $g(n')=g(n)+c(n,n')$ ，右边加g后可得 $f(n)\le f(n')$ 。这是支持“节点关闭后无需再打开”的重要条件。

若h可采纳但不一致，已处理状态后来仍可能有更便宜g。此时应更新父指针/成本并重新打开，让改进继续传给其后继；不能照搬“见过一次永不再管”。下方课堂图正适合练这件事。不是每道手算题都必须证明一致性，但不能在宣称一般最优保证时省掉实现条件。

补充 · 一致性怎样让沿路的 f 不下降（通识讲解；演示数据不属于原题）。

对边 $n\to n'$ ，一致性写为 $h(n)\le c(n,n')+h(n')$ 。若子节点沿这条路线获得 $g(n')=g(n)+c(n,n')$ ，两边加 $g(n)$ ，得到

f(n)=g(n)+h(n)\le g(n)+c(n,n')+h(n')=f(n').

所以沿同一条生成路径，预算下界不会突然下降。演示 $g(n)=3$ 、边代价2、 $h(n)=4$ 、 $h(n')=3$ ：一致性4≤5，父f为7、子f为8。若把子h改为0，父f仍7、子f变5，一致性在这条边失败；即使两个h各自都不超过真实余程，也可能发生这种下降。

这一局部性质解释了为什么一致启发让“已取出状态无需重开”的标准图搜索论证更顺畅。若只知道可采纳而不一致，便要保留更便宜路线的更新与重开机制。这里的代数是在解释性质，不改变原课堂图实际不满足全部条件的事实。

补充：全部启发都不高估，仍然需要重新打开的例子

自编有向图S→A成本2，S→B成本1，B→A成本0.5，A→G成本2。令 $h(S)=0,h(A)=0,h(B)=2,h(G)=0$ 。真实剩余成本分别为3.5、2、2.5、0，因此这些启发全都可采纳。但B→A上 $2>0.5+0$ ，不一致。

取出节点	动作	frontier，按f排序
S	生成A与B	A(g2,f2)，B(g1,f3)
A	首次展开A，生成G	B(g1,f3)，G(g4,f4)
B	经B到A只需1.5，改善已关闭A	A(g1.5,f1.5)，G(g4,f4)
A（重开）	把改善传到G，父指针更新	G(g3.5,f3.5)
G	弹出目标	返回S→B→A→G，成本3.5

若B展开时因A“已经访问”而丢掉改进，则G仍以成本4返回，错过3.5。这里没有负边，也没有高估，错误只能归到未传播更便宜前缀。表中的f从3降到1.5正是不一致启发允许出现的现象。

父链与g必须一起更新；只把G的数值改小却留下旧父链S→A→G，会得到“报告3.5，实际路线4”的不一致结果。每次练习结束把父链边权重新相加，是与队列排序独立的一项验算。

时间、空间和搜索形状（p.42–44）

课件以最大深度m、分支数b写最坏 $O(b^m)$ 时间与空间：h可能没有提供有效区分，仍需处理指数多的候选。h为0且等步成本时，A*行为可退化为BFS。不能因为它“朝目标集中”就说只存一条路径或一定是多项式时间。

p.44比较UCS向各方向按已付成本扩展、贪心追低h、A*兼顾g+h。这里图像是行为直觉，真正证明必须回到frontier、不等式和去重条件。

同一课堂题，两种算法为什么不同（p.45）

p.45 If the initial node is node B, what is the solution if use A∗ search?

同页题干说明节点旁数为启发、边数为成本。原选项A.BEFHG、B.BCFHG、C.BCDHG、D.BADHG。它与p.25是同一无向带权图，完整输入和每一步见下面的课堂计算表。

先把完整过程自己算一遍，再展开下面的答案。这题的重要限制是：给定h不全可采纳、也不一致；本例能得到最优路线，不等于“任何h的A*都最优”。

课堂图的完整输入、更新与父链（p.45）

图（p.45）：无向图。起点B、目标G；启发A12/B19/C13/D6/E6/F4/H3/G0。边BA6、BC5、BE10、AD6、CD6、CF7、EF6、DH4、FH6、HG3。与p.25图逐边一致，边上没有单向箭头。

约定最小f先取，相同f按字母序；发现更低g就松弛，已关闭节点必要时重新打开。你可以先只抄输入，遮住下面表格自算。

参考答案

表中每个候选写成“状态(g,h,f)”，列出完整frontier。父节点在更小g到来时一起更新。

取出	新候选/改进为何成立	之后完整frontier
B	A的g6，C的g5，E的g10	[E(10,6,16),A(6,12,18),C(5,13,18)]
E	F的g=10+6=16	[A(6,12,18),C(5,13,18),F(16,4,20)]
A	D的g=6+6=12	[C(5,13,18),D(12,6,18),F(16,4,20)]
C	D的新g=5+6=11；F的新g=5+7=12	[F(12,4,16),D(11,6,17)]
F	H的g=12+6=18	[D(11,6,17),H(18,3,21)]
D	H的新g=11+4=15，更新父节点为D	[H(15,3,18)]
H	G的g=15+3=18	[G(18,0,18)]
G	目标取出，停止	[]

成本没有更小的返回边候选均跳过。例如F回C成本19，比已有5大；D回A成本17，比已有6大。恢复父链G←H←D←C←B，正向B→C→D→H→G，成本5+6+4+3=18，选C。F曾被展开，但最后不在成功父链中。

为什么F的f能从20变16？同一状态的h始终4，改变的是从B经C到F的g由16降为12。更新g不是“更改题给启发表”。

若f18的平局先选D而不是C，D会先以g12处理，后来C发现g11，必须重开D。否则H可能沿旧成本16留下，再到G19，错过18。这个反例把“便宜路径要传播出去”的必要性具体化。

校验启发条件：B到G实际最低为18，而h(B)=19，起点已高估；C→D边成本6、h(D)=6，但h(C)=13大于6+6=12，不一致。本例初态必被取出，所以起点高估未改变第一步；不能因此说高估普遍安全。返回18是本次完整运算的结论，不是从不满足条件的定理硬推出来的。

补充检查：若所有h改0，表格首步会先取A、C还是E？

参考答案

先C，因为g分别为6、5、10，h全0后f就等于g。A*变UCS，不能继续照抄原表先E。最终最优路线成本仍是18，但搜索顺序可以不同。

本讲核心考点

g来自沿路累加，h从当前状态估未来，f才是队列优先级（p.27–32，C级）。
可采纳性为固定前缀提供乐观预算；证明还需保留最优路径前沿（p.33–41，C级）。
不一致图搜索需正确松弛/重新打开，不要用简单visited掩盖改进（p.41补充、p.45，C级）。

附录

同图在历年卷中的选项字母（非讲义内容）

题面（ESTR-Final-Exam-2023T1.pdf · Part I Q6 · p.3，扫描件视觉核对）问起点B时A*得到哪条路径，节点启发与无向边成本与正文课件图一致。卷中选项是E.BEFHG、F.BCFHG、G.BCDHG、H.BADHG。

参考答案

父链仍是BCDHG、成本18，但卷上的字母是G，课件p.45的字母才是C。相同路径用不同字母列出时，要依当前题面作答，不要背字母。这是ESTR2023的历史考题证据，不是2026T1 CSCI3230范围承诺。

回到正文

来源与证据

原件：L10-Informed-Search-2025T1.pdf（本地课件），具体页码标在各节。原课件保留本地。
例子标为“补充”时是为帮助理解而选取，不是教师题目或2026T1要求。
考试证据（沿用既有笔记的历史核对记录）：视觉核对 ESTR-Final-Exam-2023T1.pdf p.3–5中本篇引用的搜索题；仅证明ESTR旧卷相应问法出现过（A级，扫描件），不据此预测今年CSCI3230考题。补充练习与自检均为通识（C级）。