CSCI3230 L09 · Part 2/7 Breadth-first search

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2025T1 本讲：L09，第 2 部分 / 共 7 部分 · 原件 L09-Uninformed-Search-2025T1.pdf（本地课件） p.26–33 定位：FIFO使较浅节点先展开。前后：上一份 Introduction · 下一份 Uniform-cost search

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

按层探索

为什么先看近的一层（p.26–27）

p.26为分节页。BFS（广度优先搜索）适合先回答：“最少做几步能到目标？”想象一圈圈扩大找东西的范围：先查0步，再查1步，再查2步。这里的“近”是动作次数少，还没有比较道路里程或价格。

只需先理解搜索建模的状态、后继和frontier。根的深度为0；沿一条边增加1。**队列（queue）**从尾部加入、从头部取出，叫先进先出FIFO。因为较浅节点先加入，所以它们会先取出。

完整走一遍队列（p.28）

图（p.28）：A为根，下一层B、C；B下为D、E，C下为F、G；目标G。元素：这是一棵向下展开的搜索树，左到右生成后继；叶子D/E/F/G没有画后继。看什么：目标路径是A→C→G，而处理顺序还包含B、D、E、F。

以下统一规定取出时检验目标，队列左端下次取出。课件演示在生成G时结束；BFS在等步成本并正确维护分层时也可以这样做。先明确约定，两种合法实现才不会被误认为算错。

步	取出并检验	为什么接下来这样处理	处理后frontier
0	尚未取出	初态入队	[A]
1	A，不是目标	按顺序加入B、C	[B,C]
2	B，不是目标	D、E排在原来C后面	[C,D,E]
3	C，不是目标	F、G接在队尾	[D,E,F,G]
4	D，不是目标	无后继	[E,F,G]
5	E，不是目标	无后继	[F,G]
6	F，不是目标	无后继	[G]
7	G，是目标	停止，沿父指针恢复	[]

在第2步，把D放到C前面就破坏了BFS：你会先深入B的分支。第3步必须记住G的父节点是C；不能把整个“取出名单”当路线。

补充·重复状态：如果D和F其实是同一地点的两种到达方式，图搜索通常在第一次入队时就记“已发现”，以后不再入队。BFS第一次发现的深度已经最小，等步成本下保留它是安全的。这条规则不能原样照搬到UCS，因为不等成本时晚来的路线可能更便宜。

补充 · 发现时入集合，还是取出时入集合（通识讲解；演示数据不属于原题）。

在单位边代价的图搜索中，BFS第一次发现一个状态时，已通过最少边数的一条路线到达它，因此可以在入队时标记“已发现”，防止其他同层父节点反复将它加入队列。演示 S 同时连向 A、B，A和B都连向C：展开A时C入队，展开B时发现C已在集合中，就不再加入第二份。

若选择出队才标记，也必须说明如何处理队列里的重复项；否则图虽小，frontier可能塞入很多重复路线。不要把这个结论直接照搬到UCS：带不同边代价时，首次发现C的路线未必最便宜。去重时机不是一条脱离搜索策略的通用规定，它依赖首次发现究竟能保证什么。

补充：首次发现深度最小的归纳理由

根深度0。假设队列取出深度 $k$ 的节点时，所有尚未取出的记录深度至少为 $k$ ，并且至多处在 $k$ 与 $k+1$ 两层。展开当前节点只生成 $k+1$ 层，并加到队尾，不会越过已有 $k$ 层节点；所以队列继续满足分层顺序。

如果第一次发现X的深度为 $k+1$ ，却另有一条长度不超过 $k$ 的路线到X，那么那条路线的倒数第二个节点深度最多 $k-1$ ，应在当前 $k$ 层之前展开，早已生成X，与“第一次”矛盾。因此首次发现给出了最少边数；这才支持入队时去重。

自测（自编，非原题）：给每条边的成本都改成2，这个论证哪里需要改？如果只把某一条边改成100呢？

解释

全改成2时，深度仍按边数加1，证明不变；每条长度为k的路线成本都是2k，所以最少边数也最低成本。只改一条边时，首次发现最浅仍成立，但不能再从最浅推出最便宜，损坏的是成本解释而非队列分层性质。

为什么有解就能找到（p.29）

设每个节点最多有 $b$ 个后继，最浅目标在深度 $d$ 。 $b$ 是分支数，不是图中总节点数； $d$ 是目标离起点的最少步数，不是最大树深。若两者有限，目标之前只有有限层，每层又只有有限节点，所以算法总能轮到目标那层。这就是完备性的理由。

反过来，若根有无限多个后继，光生成第一层就可能永远做不完。算法名本身不替你保证输入满足条件。

最少步为何可能更贵（p.30）

图（p.30）：有向边A→B为1、A→C为10，B→D与B→E均1，C→F为1、C→G为10，D→G为1。看什么：图中所有边都正，但两步路线仍比三步路线贵。

BFS先找到A→C→G，步数2，成本 $10+10=20$ 。另一条A→B→D→G有3步，成本 $1+1+1=3$ 。BFS并没违反自己的规则，它优化的是层数。

若每条边成本都等于同一个正数 $c$ ，深度 $k$ 的路线成本就是 $kc$ ，少一步一定更便宜，这时BFS才保证最低成本。p.30的“costs decreasing”不要误读成存在负边；反例真正说明不同路线的成本未必随层数排序。

p.30原文更一般地要求路径成本是深度的非递减函数。准确理解为存在同一个非递减函数 $F$ ，各路径成本由其深度 $k$ 决定，即 $g=F(k)$ ，因而同深度不会藏着未比较的更低成本。仅有“每条路径向前走时成本不减”还不够：本页的全正边反例已经满足后者，却不满足不同路径之间按深度统一排序。

指数增长是怎样来的（p.31–32）

根1个，第一层至多 $b$ 个，第二层每个父节点再生 $b$ 个，所以至多 $b^2$ 个。到深度 $d$ 的总数是

1+b+b^2+\cdots+b^d=\frac{b^{d+1}-1}{b-1}\quad(b>1).

补充取 $b=2,d=3$ ：层数分别为1、2、4、8，总数15。再多一层就增加16个，总数31。这解释了为什么队列会突然很大。课件用到目标层的规模记为 $O(b^d)$ ； $O$ 表示增长阶，不是精确节点数。

空间也可能有一整层候选，所以同阶。若实现直到取出目标才停，并在此前展开了同层非目标，可能已经生成下一层，常见更保守上界为 $O(b^{d+1})$ 。写复杂度时应说明计的是生成还是展开、检验在何时，而不是只背一个指数。

课堂小题先看层数（p.33）

p.33 If node G is a goal node, what is the solution if use breadth-first search?

原选项为A.ABDG、B.ABDHG、C.ABEG、D.ACG。图在D下、H下、E下和C下均画有G。先数每条路径的边，不要被画得最左的目标吸引。

参考答案

ACG只有2条边，其他选项分别3、4、3条边，因此选D。返回路径ACG，不返回节点展开次序。

把队列与动作列表分开保存的练习见附录 A1。

本讲核心考点

FIFO维护“浅层在前”，首次发现时去重需要等步成本的背景（p.27–29，C级）。
最少步与最低成本只有在适当成本条件下等价（p.30，C级）。
时间和内存的难点都是层宽指数增长（p.31–32，C级）。

附录

A1 不把搜索顺序交给执行者

补充检查：p.28的图展开过B，为什么返回动作不能包含A→B？如果把队尾加入改成队头加入，会发生什么？

参考答案

B属于另一条被尝试过的路径；它不是G的祖先。G的父链为G←C←A，所以执行者只需A→C、C→G。把新后继放队头会让新生成的深层节点抢先处理，失去FIFO分层保证，行为趋近深度优先。可把上表第2步重算为[D,E,C]，立即看出差异。

这里是讲义小图的学习演练，不是历史HW04可提交实现，也未运行任何自动评分器。

历史HW04的接口要求对应哪部分机制（非讲义内容）

题面节选（HW04-2025T1-题目.pdf · Q2 · p.4）：

p.4 Implement the breadth-first search (BFS) algorithm in the breadthFirstSearch function in search.py. Again, write a search algorithm that avoids expanding any already visited states.

这是2025旧作业Q2，占36%；本节只帮助理解接口，不是当前作业提交代码。题目要求的不是打印出队名单，而是返回合法动作列表。后继必须由题目框架给出，不能直接用坐标差制造穿墙动作；p.3还要求使用util.py提供的数据结构以兼容框架。

沿p.28树做接口记录：初态携带空动作；生成C时保存A→C；从C生成G时保存此前动作再接C→G。B虽然被探索，其动作属于另一份候选记录，不得混进G的列表。去重用来避免同一状态反复扩展，FIFO用来保证浅层先处理，这两件事各有职责。

原题测试入口包括mediumMaze、bigMaze的SearchAgent与bfs参数，并说明通用写法也可用于eightpuzzle。应分别检查动作合法、终点满足目标、层数是否最少和重复扩展是否被挡住；不能仅见到动画到达终点就断言所有性质通过。既有笔记依据题面与教学小图解释；此次补写未运行这些游戏命令或autograder。

回到正文

来源与证据

原件：L09-Uninformed-Search-2025T1.pdf（本地课件），具体页码标在各节。原课件保留本地。
例子标为“补充”时是为帮助理解而选取，不是教师题目或2026T1要求。
考试证据（沿用既有笔记的历史核对记录）：核对 HW04-2025T1-题目.pdf Q1–Q2（p.3–4）；只作为2025旧作业证据（A级），未运行作业程序。补充练习与自检均为通识（C级）。