CSCI3230 L10 · Part 4/4 Summary

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2025T1 本讲：L10，第 4 部分 / 共 4 部分 · 原件 L10-Informed-Search-2025T1.pdf（本地课件） p.46–48 定位：搜索算法的保证由排序、成本、启发和去重共同决定。前后：上一份 A-star search

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

全课程搜索部分收束

先用一句话区分三种优先级（p.46–47）

p.46是分节页，p.47回顾启发、贪心与A*。UCS问“已经花多少”；贪心问“看起来还剩多少”；A*问“沿这条路线总共可能花多少”。三者都维护frontier，不是三个互不相干的程序概念。

记住输入输出： $g(n)$ 是沿已记录路径的精确累计成本； $h(n)$ 是从当前状态估计剩余成本； $f(n)$ 是一个用于排队的标量。输出仍是一条合法动作路径，不是f最小的节点名单。

方法	排序分数	会忽略什么	最低成本保证要看什么
UCS	$f=g$	不估计未来方向	非负/正成本条件、正确松弛与目标出队
贪心	$f=h$	已付成本	一般不保证最低成本
A*	$f=g+h$	不直接知道真实余程	启发不高估、图搜索去重/重开、停止时机等条件

同一补充小图走出三种不同顺序

下面数字专为比较选取，非讲义原题。有向边S→A为2、A→G为8，S→B为5、B→G为1。给h(S)=6、h(A)=8、h(B)=1、h(G)=0。这些估计恰好等于各点真实最佳余程，因此可采纳且一致。

算法	S展开后完整frontier	下一步	最终路线
UCS	[A:g2,B:g5]	取A，得G10；仍有B5；取B更新G6	S→B→G，6
贪心	[B:h1,A:h8]	取B，得G:h0；取G	S→B→G，6
A*	[B:(g5,h1,f6),A:(g2,h8,f10)]	取B，得G:f6；取G	S→B→G，6

本例三者最终答案相同，却不说明它们算法等价：UCS多试A，贪心碰巧选对。把A→G改为1、h(A)随之改1、h(S)改为3、h(B)仍1，并约定h平局先B，则贪心会先B返回6，而最优S→A→G成本3；A*则比较A的f3与B的f6，先A返回3。这个变化说明贪心连“启发恰好等于真实余程”也不能自动补回已经走过的成本。

两个保证别混在一句“启发很好”里

可采纳只问每个状态的h是否不超过真实余程。它是对估计偏差的要求。一致性还问相邻状态的估计是否和一步成本相容；它限制沿边的变化。

补充小数例：X到G真实最低为5，Y到G为3，X→Y成本2。若h(X)=5、h(Y)=0，两者都不高估，但5大于2+0，违反一致性。为什么重要？沿这条边走后，f可能突然降低，使一个已经关闭的状态后来仍值得重新打开。

所以正确表述不是“A*用了启发就最优”，而是“在适当成本、启发、保留/重开路径和目标取出条件下有保证”。本讲p.45课堂图的h甚至在起点高估；它需要具体运算，不可冒称满足整张定理条件。

算图时按一个固定顺序自查

第一步确认题给的是状态图还是搜索树。图中同一状态可能由不同路线到达，需要比较g；树中重复标签可能代表不同路径节点。再确认边方向，无向边可反走，箭头边不可倒过来。

第二步写明平局规则、目标检验时机、去重策略。第三步每次都列完整frontier，包括暂时被拖后的候选；不能只在最新节点的邻居里选。第四步算新路径g，再读取h，再相加f；不要把父节点f加边权当作新g，那会把启发混进实际成本。

第五步到目标后沿父链恢复，独立累加边权。若总成本与目标节点g不相同，检查是否漏更新父指针。最后才说明最优性：已经算出的一个好答案，不能代替对算法一般保证的证明。

继续阅读时把难点对准（p.48）

p.48给AIMA第4.1节和CS188作为阅读入口。若现在跟不上，先回到L09建模弄清节点/状态/路径，再做UCS的G11→G10更新；理解这一步后，再加一个h分量去读A*完整表。不必先把所有复杂度背熟才动手算。

读完应能解释“为什么取这个候选”以及“什么条件改变会让保证消失”。这些是可迁移的方法，而非2026T1具体考试范围的声明。

补充 · 把最优性拆成一份可以反驳的声明（通识讲解；演示数据不属于原题）。

“这个算法得到最优解”至少可能指两件事：在这次具体小图中，返回路径恰好最便宜；或对满足某些条件的一整类问题都有保证。前者可以通过枚举其他路线核对，后者需要算法规则与假设的论证。某一次高估启发碰巧找到最佳路线，不能证明高估总是安全。

因此检查答案时先重算实际返回路径的成本，再检查声明的保证是否有对应条件：边成本、启发性质、重复状态策略、停止时机。若题目只让写扩展顺序，还要保留平局约定；两种合法平局可能顺序不同但最优成本相同。把“顺序、路径、成本、保证”分别写出，比一行“答案是A*”更完整。

p.48完整阅读条目为Stuart J. Russell与Peter Norvig《Artificial Intelligence: A Modern Approach》第4.1节，以及CS188 Introduction to Artificial Intelligence（Summer 2021）讲义。课件列的三个复习主题依次是informed search与heuristics、greedy best-first、A*；一致性和重开机制在本笔记明确作为理解图搜索所需的补充条件。

补充：为什么多个一致启发取最大仍然一致

设每个 $h_i$ 对同一动作成本都一致。对某条边 $n\to n'$ ，选择在n处取得最大值的编号j，则 $h(n)=h_j(n)\le c(n,n')+h_j(n')\le c(n,n')+\max_i h_i(n')$ ，最后一项就是 $c+h(n')$ 。虽然最大值在后继处可能由另一个编号取得，第二个不等号仍然成立，所以结论不要求全图一直选同一个启发。

自取边成本2，在父节点两个估计为4、3，子节点为2、4；各自满足4≤2+2、3≤2+4，最大值分别4与4，也满足4≤2+4。两者若都在目标为0，最大值也为0；结合各自不高估，得到既可采纳又一致的组合。

相加则没有同样保证：真实剩余成本5，两个下界各为4，相加8已经高估。只有能另证它们对应可相加且不重复计算的成本部分，才可能安全相加。记住max的证明，而不是只记符号，有助于在换启发时知道哪些条件需要重查。

本讲核心考点

同一输入换排序规则，过程改变应能从g/h/f解释（p.47，C级）。
可采纳与一致性不同，图搜索要保护更低g的改进（p.47联系前文及补充，C级）。
先完整frontier，后父链，再成本核验；不能用探索形状代替证明（p.47，C级）。

附录

补充检查：某候选n的g为4、h为7，边n→m成本2，m的h为3。新g和f分别多少？若有人写g(m)=13，混淆了什么？

参考答案

新g是4+2=6，新f是6+3=9。13来自把父节点f=4+7=11再加边权2，错误地把父节点“预计未来7”也算成已经支付。真正走到m后，应该重新读取m的余程估计3，而不是继承n的估计作为实际花费。

来源与证据

原件：L10-Informed-Search-2025T1.pdf（本地课件），具体页码标在各节。原课件保留本地。
例子标为“补充”时是为帮助理解而选取，不是教师题目或2026T1要求。
考试证据：本轮只核对上述讲义，没有据此预测今年考题；练习与自检均为通识（C级）。