CSCI3230 L09 · Part 3/7 Uniform-cost search

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2025T1 本讲：L09，第 3 部分 / 共 7 部分 · 原件 L09-Uninformed-Search-2025T1.pdf（本地课件） p.34–40 定位：按累计成本g取最小，目标要在出队时确认。前后：上一份 Breadth-first search · 下一份 Depth-first search

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

成本优先于步数

不再问“几步”，改问“已经花了多少”（p.34–35）

p.34为分节页。上一份的BFS在一条公路特别昂贵时会选错成本目标。UCS（一致代价搜索）保留frontier，但每次挑其中累计成本最小的路径，而非加入最早者。

累计成本记为 $g(n)$ ：从起点沿当前这条路线走到节点 $n$ 的实际花费。输入是一个路径节点，输出是一个数；若边标公里， $g$ 也用公里。它不是最后一条边的价格。走到后继 $n'$ 时更新

g(n')=g(n)+c(n,n').

$c(n,n')$ 是这一条边的成本。把“已经付的钱”加上“下一步新付的钱”，才是新累计。优先队列会按这个数排序，小的先取；它与普通FIFO队列不同。

课件图逐步算完（p.36）

图（p.36）：S连A/B/C，成本分别1/5/15；A/B/C分别连G，成本10/5/5。原状态图连线没有单向箭头，下方搜索树画向目标的候选路径。看什么：经A先看到了G，但它不是最后应返回的路线。

按图搜索过滤返回已处理起点的更贵路线。下表用“状态:累计成本”，始终按成本升序列frontier；相同状态只保留当前最佳候选。

步	取出	本步计算	处理后完整frontier
0	—	起点成本0	[S:0]
1	S:0	到A为0+1，到B为0+5，到C为0+15	[A:1,B:5,C:15]
2	A:1	到G为1+10=11	[B:5,G:11,C:15]
3	B:5	新到G为5+5=10，比11小，更新	[G:10,C:15]
4	G:10	取出后确认目标，停止	[C:15]

结果是S→B→G，总成本10。关键停顿在第2步：生成G只能说明有一条11的可行路，不能说明不存在更便宜的路。 B才花5，接下来仍有机会得到低于11的目标。所以UCS在从优先队列取出目标时才确认。

若用“首次见过就永久排除”的BFS式visited，第3步G已经见过，10就被错误丢弃。应记录每个状态目前最小的 $g$ ；新值更小时更新成本和父指针。这一步叫松弛。实现可降低队列里原记录的优先级，也可插入新记录、取出时跳过旧的过期记录；两种记账方式的数学意思相同。

为什么非负成本能保护最优性（p.37–38）

直觉是：如果后面的边都不降价，那么一条目前已经比目标贵的路线，不可能靠继续走变便宜。更严格地说，假如取出的目标成本10，而还有总成本8的路线，8的路线必有一个尚未处理的前沿；由于剩余边非负，这个前沿已走成本最多8，理应排在10前面，产生矛盾。

p.38专门打破这个条件：有向边S→B为1、B→G为2，S→C为10、C→G为−20。队列先取B1，再得到G3；G3排在C10前而返回。但C后面有“返款”，总成本 $10-20=-10$ ，所以3不是最优。不能把负边当成普通UCS仍可靠的输入。

p.37另有有向环：S→B成本1、B→S成本−1、B→G成本2。树搜索不断产生成本0的回到S路线，目标3被拖后。图去重能阻止这个具体环，但不能修复上面的负边最优性反例。

“每步至少一点点”为什么还要强调（p.37）

在可能无限的搜索空间里，只说每条边正还不够。需要统一下界 $\epsilon>0$ ：无论哪一条边，都至少花同一个正数 $\epsilon$ 。若可接受成本上限10，每步至少2，最多只能走5步而不超预算；不会有无限多个越来越便宜的动作挤在目标前面。结合有限分支和有限成本解，就有完备性保证。

补充边界：在有限图中，非负边包括0边，配合正确去重/松弛也能运行UCS。不要把用于无限空间证明的充分条件误读为“0边永远非法”。

补充 · 优先队列里留下旧条目时怎样处理（通识讲解；演示数据不属于原题）。

实现不一定有方便的“减小键值”操作，可以在找到更便宜路线时插入新条目，并保留旧条目待弹出。演示先发现到A成本9，随后发现成本4：最佳成本表改为4，队列同时可能有(A,4)和(A,9)。弹出(A,9)时发现它比表中4更贵，应跳过，不再次展开，也不能用它覆盖更好的父节点。

这叫延迟丢弃过期条目。表中成本记录当前已知最好路线，队列条目记录某次发现，二者生命周期不同。找到更低成本时，成本与父节点要一起更新；否则最终会打印成本4，却沿旧父链走出成本9的路径。正确性核对最后应重算返回路径的边代价之和，不只看优先队列最后弹出的数。

补充：零代价环下，更新条件为什么最好用严格更小

自编有限有向图：S→A成本0，A→S成本0，A→G成本1。最佳成本初为S=0，其余无穷。取S得到A=0；取A时，到S的新成本仍为0，不比已有值更小，因此不更新；再得到G=1，取出目标结束。

若无条件把“相等也更新”写成小于等于，并且没有另一个有效的关闭/去重机制，A会重新插入S，S又重新插入A，优先队列始终存在成本0的记录，目标1不断被拖后。有限状态并没有自动防止这个实现层的重复。

严格更小保证这里不会反复接纳相同成本；若任务要求枚举所有等成本解，则需要另外的多父节点记录及防环设计，不能简单让更新条件无限接受重复。一个最优解与所有最优解是不同输出要求。最后恢复路径时，还应保证父链不会因零成本等值覆盖而形成环。

有效深度的含义（p.39–40）

令 $C^{\ast}$ 为最优路线总成本， $\epsilon$ 为每步成本下界， $b$ 为最大分支数。成本不超过最优值的路线至多约 $C^{\ast}/\epsilon$ 步，因此课件用

O\left(b^{C^{\ast}/\epsilon}\right)

估计时间与空间。补充取 $C^{\ast}=10,\epsilon=2,b=3$ ：深度至多5，最满的树到该层有 $1+3+9+27+81+243=364$ 个节点。若最便宜一步从2降成1，有效深度上界变10，候选可能急剧增多。这不是说每个输入都达到上界，而是说明大量便宜分支会拖慢UCS。

若把最后展开生成的额外一层也计入，更保守上界常写 $O(b^{1+\lfloor C^{\ast}/\epsilon\rfloor})$ 。这是隐式搜索树的计数，不要和已给出完整有限图的Dijkstra优先队列运行时间混成同一个公式。

p.35“所有step cost相同则等同BFS”指正的等步成本及相容的同成本先后规则： $g=ck$ 使按g排序等于按深度k排序；若同深度的平局顺序不同，访问名单仍可不同，但最少步成本相同。p.39–40反复强调UCS由成本而非步数引导，因此复杂度中的有效深度来自预算除最小步价，而不是直接拿最浅目标d代入。

本讲核心考点

优先级用整条路径的累计成本，不用最后一条边（p.35–36，C级）。
取出时检查目标，发现更低成本时必须允许更新（p.36，C级）。
负边破坏最优性；统一正下界与有限分支保护一般空间的完备性（p.37–40，C级）。

附录

补充检查：只把课件p.36的B→G从5改为20，其他不变，UCS会返回什么？

参考答案

扩展A后候选为B5、G11、C15。取B时新G成本25，不优于已有11，所以不更新。接着取G11，返回S→A→G。这个练习检验“发现新路径”与“发现更好路径”的区别，不能见到新父节点就无条件覆盖。

来源与证据

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