从基础理论开始学习人工智能（四）：盲目搜索——深度优先、广度优先与迭代加深

从基础理论开始学习人工智能（四）：盲目搜索——深度优先、广度优先与迭代加深

系列：AI 学习笔记 · 从零开始读教材
教材：《人工智能》（第 3 版）第 2 章「盲目搜索」2.3 节（深度优先搜索 DFS / 广度优先搜索 BFS / 迭代加深的深度优先搜索 DFS-ID）

一、引言：从"怎么走"到"按什么顺序走"

第 03 篇我们完成了 2.0～2.2.3 的学习：把问题表示成状态空间图，再沿着生成-测试范式改进出回溯法与贪心算法。但有一个关键问题还没有系统回答——

在状态空间图上，到底按什么顺序去扩展节点，才能高效地找到解？

教材 2.3 节正式回答这个问题。它给出三种最经典的**盲目搜索（blind / brute-force search）**算法：深度优先搜索（Depth-First Search, DFS）、广度优先搜索（Breadth-First Search, BFS）和迭代加深的深度优先搜索（Depth-First Iterative Deepening, DFS-ID）。

“盲目"的含义是：搜索过程不使用任何关于问题域的知识（不像启发式搜索那样"猜"哪个方向更可能接近目标），只是机械地按某种既定顺序把状态空间图"走"一遍。虽然"盲目”，但它们是理解一切更高级搜索算法的地基，也是本教材第 4 章启发式搜索的对照基线。

二、2.3 总览：三个算法、两种数据结构、一个思想

把 2.3 节浓缩成一张速查表，先建立整体印象：

三种算法都建立在 open 表 / closed 表 的框架上：

• open 表：存放已生成但尚未扩展的节点（“待办清单”）；
• closed 表：存放已经扩展过的节点（“已完成清单”），避免重复访问。

算法的全部差别，只在于"从 open 表中取出下一个节点的顺序"：DFS 从栈顶取（后进先出），BFS 从队首取（先进先出），DFS-ID 则反复用 DFS 但每次限定最大深度。

图 19 深度优先搜索的过程演示：从根节点出发，沿最左侧分支一路深入（1→2→4→8），直到叶子节点无后继；此时回溯到上一层，再深入下一个未访问分支（9、5…）。图中箭头表示扩展顺序，虚线表示"碰壁后的回溯"。

三、2.3.1 深度优先搜索（DFS）

3.1 核心思想：一条路走到黑，撞墙再回头

深度优先搜索的基本策略是：

在搜索树的任意一层，都只取当前节点的一个子节点继续深入；当到达没有后继节点（叶子）或没有未访问后继的节点时，就**回溯（backtrack）**到上一层的下一个未访问节点，继续重复这个过程。

换句话说，DFS 的信念是：“只要沿着一条分支不断深入，总有一刻会碰到目标；这条路走不通，就退回去换一条。” 它优先探索"深度"，而不是"广度"。

3.2 数据结构：栈（LIFO）与 open/closed 表

DFS 对应数据结构是栈（stack）：后进先出（LIFO, Last-In-First-Out）。

搜索开始时，把起始节点压入 open 栈；每次循环：

"栈"决定了 DFS 天然的行为：新发现的节点永远优先被扩展，于是搜索总是扎进当前分支的最深处；只有整条分支都弹空（回溯），才轮到上一层兄弟节点。

3.3 过程演示：一棵 3 层二叉树的 DFS 顺序

图 20 广度优先搜索的过程演示：先把起始节点的全部子节点加入队列，再按"先入队先扩展"的顺序逐层铺开（1→2→3→4→5→…）。扩展顺序严格按节点距根的层数：第 1 层全部访问完，才进入第 2 层。

回到 DFS，它的访问顺序可以用下面这棵小树直观感受（这也是图 19 的底层结构）：

• 根节点记为 1，其子节点 2、3；2 的子节点 4、5；4 的子节点 8、9……
• DFS 的访问序列是：1 → 2 → 4 → 8 → 9 → 5 → 3 → 6 → 7（先沿 1-2-4-8 深入到底，8 无子节点后回溯到 4，再扩展 9；9 到底后回溯到 2，扩展 5……以此类推）。

注意与 BFS 的对照：BFS 会先访问 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9（逐层铺开），而 DFS 则是"垂直到底再回来"，两者的访问顺序截然不同。

3.4 伪代码

图 21 DFS 伪代码：open 为栈（LIFO），closed 记录已扩展节点；每次从 open 弹出栈顶，生成子节点时压栈，并跳过已在 open/closed 中的节点（防止环路与重复）。

教材风格的 DFS 伪代码如下：

Procedure depth_first_search
open = [Start] # 栈：初始只含起始节点
closed = [] # 已扩展节点表
while open ≠ [] do
x = pop(open) # 取栈顶（最后压入的节点）
if x 是目标状态 then
return x # 找到解
for x 的每个子节点 c do
if c ∉ open 且 c ∉ closed then
push(c, open) # 压入栈顶，优先扩展
push(x, closed) # 记录已扩展
return FAIL # open 为空：无解

3.5 特性与代价

适用场景：状态空间很深但分支不宽、解的位置"大概率靠深"时很划算；也是空间受限环境下（内存小）的首选。教材指出，DFS 在"无效路径不太长"的问题上表现得合理——因为这样即使走错路，回溯成本也不高。

四、2.3.2 广度优先搜索（BFS）

4.1 核心思想：层层推进，先到先得

广度优先搜索与 DFS 恰好相反：

按照节点离根节点的距离（层数）来生成节点——先访问距离为 1 的所有节点，再访问距离为 2 的所有节点，依此类推。第一个到达目标的路径，一定是长度最短的路径。

BFS 的信念是：“先把眼前这一层看全，再往下一层走。” 它优先保证"离起点近的节点先被处理"。

4.2 数据结构：队列（FIFO）与 open/closed 表

BFS 对应数据结构是队列（queue）：先进先出（FIFO, First-In-First-Out）。

搜索过程与 DFS 几乎相同，唯一区别在取出顺序：

"队列"保证了同一层的节点一定先于下一层被扩展：父节点先入队，它的子节点排在所有已有兄弟之后，于是天然形成"逐层推进"的顺序。

4.3 过程演示与最优性

回到图 20 那棵 3 层二叉树：BFS 的访问序列是 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9，一层一层地推进。

由于 BFS 永远在"更浅的层"里先找目标，所以：

在每条边的代价相同（单位代价）的前提下，BFS 找到的第一个目标一定位于最浅深度 d，即最优解。

这是 BFS 最宝贵的性质，也是 DFS 没有的。代价是空间：BFS 需要把当前层的所有节点都保存在内存里。

4.4 伪代码

图 22 BFS 伪代码：open 为队列（FIFO）；每次从队首取出节点，生成子节点时加入队尾，保证按层扩展；同样用 open/closed 表去重。

Procedure breadth_first_search
open = [Start] # 队列：初始只含起始节点
closed = [] # 已扩展节点表
while open ≠ [] do
x = dequeue(open) # 取队首（最早进入的节点）
if x 是目标状态 then
return x # 找到解（且是最浅解）
for x 的每个子节点 c do
if c ∉ open 且 c ∉ closed then
enqueue(c, open) # 加入队尾，等待下一轮
enqueue(x, closed) # 记录已扩展
return FAIL

4.5 特性与代价

适用场景：需要最短路径、或者解大概率很浅的问题；状态空间宽度可控时 BFS 表现很好。但若树又宽又深，BFS 的内存开销会爆炸——这正是 DFS-ID 出场的原因。

五、2.3.3 迭代加深的深度优先搜索（DFS-ID）

5.1 痛点：DFS 省空间但不完备，BFS 完备但费空间

把前面两节对照一下，会出现一个两难：

• DFS：空间省（O(bm)），但可能不完备、不最优；
• BFS：完备且最优（单位代价），但空间爆炸（O(bᵈ)）。

有没有可能"既像 DFS 一样省内存，又像 BFS 一样保证找到最浅解"？

教材给出的答案是：迭代加深的深度优先搜索（Depth-First Iterative Deepening, DFS-ID）——它通过反复执行"带深度限制的 DFS"，并逐轮把深度界限加 1，从而一举兼得两者。

5.2 核心思想：逐轮放宽"深度界限"

DFS-ID 的做法： 先执行深度界限为 0 的 DFS（只看根节点），若未找到解，再执行深度界限为 1 的 DFS（看到第 1 层），再执行深度界限为 2 的 DFS……每轮都从根节点重新开始，深度界限逐轮递增，直到找到解为止。

注意一个关键点：每一轮都要从头重新搜索，之前轮次的结果不能直接复用。表面上看这是巨大的浪费，但事实上——

• 树的分支结构意味着浅层节点只占极小比例：深度为 d 的完全 b 叉树，第 d 层有 bᵈ 个节点，而前 d-1 层总共只有 (bᵈ−1)/(b−1) ≈ bᵈ/(b−1) 个。也就是说，重复搜索浅层的额外开销只有大约 b/(b−1) 倍（常数倍）；
• 因此 DFS-ID 的总时间复杂度仍是 O(bᵈ)，与 BFS 同阶，却只花 O(b·d) 的空间（像 DFS 一样省内存）。

5.3 过程演示

图 23 DFS-ID 过程演示：第 1 轮只允许深度 0（仅根）；第 2 轮允许深度 1（访问到第 1 层）；第 3 轮允许深度 2（访问到第 2 层）……每轮都从根重新开始，直到某轮在界限内发现目标。右侧标出"每轮重做浅层"的代价其实只是常数倍。

用一棵目标在第 3 层的小树感受过程：

• 轮次 0（界限 d=0）：只检查根节点，不是目标；
• 轮次 1（d=1）：从根重新出发，检查到第 1 层，不是目标；
• 轮次 2（d=2）：从根重新出发，检查到第 2 层，不是目标；
• 轮次 3（d=3）：从根重新出发，检查到第 3 层，找到目标，停止。

因为每轮都按"先深后浅、但不超过界限"的顺序展开，而界限又逐轮放宽，所以第一次找到目标的轮次，深度界限恰好等于最浅解深度 d——这正是 BFS 的最优性。而任意时刻内存里只保留"当前深度界限内的一条路径"，空间又回到 DFS 的量级。

5.4 伪代码

Procedure depth_first_iterative_deepening
for d = 0, 1, 2, … do # 深度界限逐轮递增
result = depth_limited_search(Start, d)
if result ≠ cutoff then
return result # 找到目标（或确认无解）

Procedure depth_limited_search(x, limit)
if x 是目标状态 then
return x
if depth(x) = limit then # 已达本轮界限
return cutoff # 返回"该层截断"标记
for x 的每个子节点 c do
result = depth_limited_search(c, limit)
if result ≠ cutoff then
return result
return cutoff # 此分支在界限内无解

（实现细节：外层循环也可以从 d=1 开始；cutoff 是一个特殊标记，表示"本轮界限内没找到，但可能更深的地方有解"，触发下一轮。）

5.5 特性与代价

教材特别强调最后一点：

深度优先的迭代加深（DFS-ID）在树搜索中，是"时间 + 空间"意义上渐进最优的盲目搜索算法——想要最优解，又想省内存，DFS-ID 就是盲目搜索的终极答案。

另一个值得一提的性质：DFS-ID 是一种"任意时刻算法（anytime algorithm）"——它可以在任意时刻被中断，并返回当前已完成轮次所能给出的当前最优解。这在实时系统里非常实用。

六、三种算法对比：一张表看懂

图 24 三种盲目搜索算法对比总表：从数据结构、扩展顺序、完备性、最优性、时间与空间复杂度、典型场景六个维度并排比较，底部给出记忆口诀。

记忆口诀：解深用 DFS，解浅用 BFS，深度未知要最优省内存，就上 DFS-ID。（符号约定：b = 分支因子；d = 最浅解深度；m = 状态空间最大深度。）

七、适用场景总结

三者都是盲目搜索：不使用问题域知识。若想在同样的框架下"猜"得更聪明——比如优先扩展"看起来最接近目标"的节点——就需要进入教材后续的启发式搜索（第 4 章），那里将给出贪心最佳优先、A* 等算法。

八、总结：整篇思维导图

把 2.3 节全部知识点收拢成一张导图，复习时一眼掌握：

图 25 第 04 篇总结导图。中心主题「2.3 盲目搜索」，六个主分支：DFS 深度优先、BFS 广度优先、DFS-ID 迭代加深、算法评价（完备性/最优性/时间/空间）、公共基础（状态空间图、open/closed 表、生成-测试范式）、选型建议。

九、学习心得与下一步

9.1 学习心得

参考资料与说明

• 教材内容与引文出处：《人工智能》（第 3 版）第 2 章「盲目搜索」2.3 节：2.3.1 深度优先搜索、2.3.2 广度优先搜索、2.3.3 迭代加深的深度优先搜索（DFS-ID）。复杂度记号 b/d/m 的含义、渐进最优性结论均按教材与经典 AI 教材（Russell & Norvig AIMA）对照整理。
• 伪代码为教材风格的重述：DFS 使用栈 LIFO 与 open/closed 表；BFS 使用队列 FIFO 与 open/closed 表；DFS-ID 使用带深度界限的深度受限搜索，逐轮递增界限。
• 复杂度说明：DFS 最坏时间 O(bᵐ)、空间 O(b·m)；BFS 时间与空间均为 O(bᵈ)；DFS-ID 时间 O(bᵈ)（常数因子 b/(b−1)）、空间 O(b·d)；"树搜索中时间与空间渐进最优"为教材明确结论。
• 配图说明：本文所有示意图均为自绘矢量图（SVG 渲染为高清 PNG），全部中文标注，无任何 AI 生成水印/logo/角标；字号层级统一（标题 15–16px / 正文 12–13px / 注释 10–11px），已逐张视觉质检：无乱码、无重叠、无连线压字。