CSCI3230 L09 · Part 7/7 Summary

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2025T1 本讲：L09，第 7 部分 / 共 7 部分 · 原件 L09-Uninformed-Search-2025T1.pdf（本地课件） p.62–64 定位：先说取点规则，再说有条件的性质。前后：上一份 Iterative deepening depth-first search

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

五种策略对照

先问问题要什么，再选取点规则（p.62–63）

p.62为分节页，p.63回顾搜索建模与五种无信息搜索。到这里最容易出现的困惑是：“五个名字都记住了，给图还是不知道做什么。”先不要默写性质表，先写一句下次从frontier拿谁。

BFS拿最先加入的节点，维持浅层先处理。
UCS拿当前累计成本最小的路径。
DFS拿栈顶，优先深入当前分支。
DLS拿法同DFS，但到上限便停止下探。
IDDFS从0开始反复DLS，成功才停。

前三个主要改变待办表的顺序；DLS改变可以探索的深度，IDDFS再改变限制怎样递增。把这些机制分开，性质才有理由。

同一张小图比较，而不是背五张图（补充）

下面数字专为比较选取，非讲义原图。所有边有向：S→A成本1，A→C成本1，C→G成本1；S→B成本5，B→G成本5。后继A先于B，各非目标未列出的后继为空。

策略与约定	frontier关键变化	首次解	它实际优化什么
BFS，出队验目标	[S]→[A,B]→[B,C]→[C,G经B]；随后C生成G经C但已发现G	S→B→G，10	2步最浅
UCS，最小g	[S0]→[A1,B5]→[C2,B5]→[G3,B5]	S→A→C→G，3	最小成本
DFS，A先	[S]→[A,B]→[C,B]→[G,B]	S→A→C→G，3	只因先试A，偶然最优
DLS，限制1	S后[A,B]，二者到边界均截断	未找到	只查1步内
DLS，限制2	先A再C截断，后B生成G	S→B→G，10	限制内第一个成功
IDDFS	限制0失败；1截断；2找到	S→B→G，10	最少步，不是一般最低价

BFS行必须留意：在采用图搜索首次发现去重时，经B的G先被发现，之后经C的更便宜G不会替换；正因边权不等，这不是适合最低成本任务的规则。UCS会按费用顺序保留3而不是10。

性质表里的每个字都有条件（p.63总结，推理见各Part）

$b$ 是最大分支数； $d$ 是最浅目标深度； $m$ 是最大搜索树深度； $\ell$ 是当前限深； $C^{\ast}$ 是最优成本； $\epsilon>0$ 是统一的一步成本下界。

策略	典型完备性条件	最低成本保证	课件树规模时间 / 路径式空间
BFS	有限分支、存在有限深度解	等步正成本时	$O(b^d)$ / $O(b^d)$
UCS	有限分支、每步至少统一正数、有限成本解	该成本条件下有	约 $O(b^{C^{\ast}/\epsilon})$ / 同阶
DFS	有限可达图并妥善防重复	一般无	有限深树 $O(b^m)$ / $O(bm)$
DLS	限制覆盖目标深度且有限分支，本轮才能保证找到	一般无	$O(b^{\ell})$ / $O(b\ell)$
IDDFS	有限分支、存在有限深度解	等步正成本时	固定 $b>1$ ： $O(b^d)$ / $O(bd)$

空间列不能忽略全局visited或日志的额外存储；复杂度按课件的树规模口径，出队才验目标的BFS可能多生成一层。有限显式图的实现复杂度和隐式树最坏计数是不同模型。

写一张手算表就能发现大部分错误（补充）

给图后先抄清：边是有向还是无向？成本是否相同？哪些状态是目标？同优先级按什么顺序？目标在生成还是取出时检验？重复状态用什么规则？

然后每一步写三件事：取出谁、增加或更新谁、完整frontier还剩谁。最后沿父指针恢复路径，并把边成本重新相加。若取出顺序与返回路径完全一样，要检查是否误把探索历史当解；若UCS一生成目标就停，要检查是否漏掉更便宜候选。

补充 · 用三个小反例检验自己选算法的理由（通识讲解；演示数据不属于原题）。

第一种图各边代价相同，想要最少步，BFS的分层顺序正好对应目标。第二种图一步可花100、两步只花2，最少步不再等于最少成本，应转向成本排序。第三种空间有无限深分支但另一浅分支有目标，普通DFS可能一直下潜，不能仅因存在解就保证找到。

这三例分别改变成本、评价目标和搜索空间深度，而不是随意给算法贴好坏标签。完整回答应包含：要优化什么，frontier如何取出，如何记录重复状态，何时检查目标，依赖哪些有限性或成本条件。漏掉其中一项，即使背对算法名，也可能执行出不同路线。

补充：为搜索算法设计四个有区分力的小检查

只测一条直线通往目标，五种策略往往都能通过，不能显示各自差异。自编四种小输入：第一种让起点本身是目标，应返回空动作列表，不能当作失败；第二种有一个环和一个出口，检查是否会重复绕圈；第三种把两步路设成本20、三步路设成本3，区分最少步和最低成本；第四种把目标恰好放在DLS限制层，检查先验目标还是先截断。

每次结果都分三项核：动作是否逐步合法、终点是否满足目标、任务要求的代价是否最优。返回一个不存在的捷径即使成本更小也不是解；返回合法目标路径也不自动证明最优。若声称无解，还要看是否真正穷尽了允许空间，还是因为深度或资源上限中止。

这些检查无需大型迷宫，反而容易逐步手算。它们用于理解算法性质，不是声称已运行课程的作业评分器，也不代替课件每个策略的条件证明。

接到下一讲：还缺“未来”（p.64）

p.64列AIMA第3章及CS188阅读。当前五种方法都没有估计“剩下还多远”；UCS只知道已经支付的 $g$ 。下一讲启发函数引入剩余代价估计 $h$ ，并比较只看未来的贪心搜索和同时考虑过去/未来的A*。

原阅读页p.64书目完整为Stuart J. Russell与Peter Norvig的《Artificial Intelligence: A Modern Approach》第3章，以及CS188 Introduction to Artificial Intelligence（Summer 2021）的讲义。此处只保留该版课件指定的来源身份；不将2021课程安排当成本课今年安排。

本讲核心考点

从frontier规则解释行为，不用算法名称替代过程（p.63，C级）。
最少步、最低成本、有解必找到是三件事（p.63，C级）。
先说明图/树、去重、成本、目标检验条件，再写性质（p.63及补充，C级）。

附录

补充检查：把上面S→B和B→G的成本都改为1，哪些算法的返回路径改变，哪些只改变成本？

参考答案

BFS、限制2的DLS、IDDFS仍走S→B→G，但现在成本为2且成为最优。DFS仍因A先而走三步路线，成本3，所以这次不最优。UCS先面对A1/B1的平局，若A先则生成C2；之后取B1得到G2，最终返回两步成本2。它的目标答案会改变，但最优性原则没变。

来源与证据

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