# 人工智能搜索技术

> CIE A-Level 计算机科学 · 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u13-ai-search-techniques/

本子主题讲解解决状态空间问题的核心人工智能搜索技术，是CIE 9618试卷1的考察内容。我们会讲解无信息盲目搜索、有信息启发式搜索，以及它们的复杂度、最优性保证和考试应用场景。

**先修:** [基础算法复杂度分析](https://www.owlsprep.com/zh/study/as-a-level-algorithm-complexity/); [图遍历基础](https://www.owlsprep.com/zh/study/graph-traversal-algorithms/)

## 学习目标

- 区分状态空间问题的无信息搜索和有信息搜索方法
- 将广度优先、深度优先和A*搜索应用于简单问题图
- 比较常见搜索技术的时间和空间复杂度
- 解释可采纳启发式在最优A*搜索中的作用

## 无信息（盲目）搜索

**无信息搜索** — 不使用任何问题特定启发信息引导搜索，仅依赖状态空间结构的搜索算法，也称为盲目搜索。

*例:* 在不知道自己距离出口多远的迷宫中寻找出口

CIE考试中最常考察的两种无信息搜索方法是**广度优先搜索（BFS）**和**深度优先搜索（DFS）**。它们采用不同的遍历策略，各有优缺点：

- - **广度优先搜索（BFS）**：在进入下一层深度节点前，先探索当前深度层的所有节点。使用先进先出（FIFO）队列存储节点，保证能找到非加权图中的最短路径。
- - **深度优先搜索（DFS）**：在回溯前尽可能沿每个分支深入探索，使用后进先出（LIFO）栈（或递归）存储节点，不保证能找到最短路径。

**例题:** 给定一个非加权图，起始节点为A，目标节点为G，边为：A → B，A → C；B → D，B → E；C → F；F → G。列出BFS的节点扩展顺序。

1. 1. 用起始节点A初始化队列，标记A为已访问。
2. 2. 出队A，将A加入扩展顺序，将未访问的邻居B、C入队。扩展顺序：[A]
3. 3. 出队B，将B加入扩展顺序，将未访问的邻居D、E入队。扩展顺序：[A, B]
4. 4. 出队C，将C加入扩展顺序，将未访问的邻居F入队。扩展顺序：[A, B, C]
5. 5. 出队D，将D加入扩展顺序（无未访问邻居）。扩展顺序：[A, B, C, D]
6. 6. 出队E，将E加入扩展顺序（无未访问邻居）。扩展顺序：[A, B, C, D, E]
7. 7. 出队F，将F加入扩展顺序，将未访问的邻居G入队。扩展顺序：[A, B, C, D, E, F]
8. 8. 出队G（目标节点），将G加入扩展顺序。最终顺序：[A, B, C, D, E, F, G]

> **考试提示:** 永远记住，BFS仅能保证非加权图中的最短路径。如果步进代价不同，BFS无法找到最优路径。

## 时间复杂度与空间复杂度

CIE经常要求比较复杂度，使用以下参数衡量：$b$ = 分支因子（每个节点的平均邻居数量），$d$ = 最浅目标节点的深度，$m$ = 状态空间的最大深度。

| 算法 | 时间复杂度 | 空间复杂度 | 最短路径保证 |
| --- | --- | --- | --- |
| BFS | $O(b^d)$ | $O(b^d)$ | 是 |
| DFS | $O(b^m)$ | $O(bm)$ | 否 |

BFS的空间复杂度是指数级的，因为它需要存储当前深度层的所有节点，因此无法应用于大型状态空间。DFS仅存储当前活跃路径上的节点，因此内存需求低得多，但可能会陷入无限深的分支中。

**概念自测**

测试你的理解：

1. 对于深度为$d$的目标，BFS的空间复杂度是多少？

   - $O(bd)$
   - $O(b^d)$
   - $O(b^m)$

   *答案:* $O(b^d)$

   *解析:* 回答正确！BFS需要存储到深度$d$为止的所有节点，因此空间复杂度是指数级的。

2. 哪个算法能保证找到非加权图中的最短路径？

   - DFS
   - BFS
   - Neither

   *答案:* BFS

   *解析:* 回答正确！BFS在深入下一层前会探索当前层的所有节点，因此第一次到达目标时经过的就是最短路径。

## 有信息搜索：A*算法

**有信息搜索** — 使用问题特定启发信息估计当前状态距离目标的远近，优先处理更有希望的路径，从而比无信息搜索更快找到解的搜索算法。

**可采纳启发式** — 绝不会高估从当前状态到达目标的实际代价的启发函数。如果启发式是可采纳的，A*搜索就能保证得到最优解。

A*搜索是CIE考试中最常考察的有信息搜索方法，它使用以下代价函数：

$$f(n) = g(n) + h(n)$$

- - $g(n)$ = 从起始节点到节点$n$的实际代价
- - $h(n)$ = 从节点$n$到目标的代价的启发估计

**例题:** 起始节点S，目标节点G。边代价：S→A = 2，S→B = 3，A→G = 5，B→G = 2。启发值：$h(S)=6$，$h(A)=4$，$h(B)=1$，$h(G)=0$。求A*的扩展顺序和最优路径，验证启发式是否可采纳。

1. 1. 计算S的邻居的$f(n)$：
2. 对于A：$f(A) = 2 + 4 = 6$。对于B：$f(B) = 3 + 1 = 4$。
3. 2. 选择$f(n)$最小的节点（B），将B加入扩展顺序。
4. 3. 扩展B，计算$f(G) = (3+2) + 0 = 5$，G是目标节点。
5. 4. 验证可采纳性：A到G的真实代价 = 5，启发值$h(A) = 4$（没有高估）。B到G的真实代价 = 2，启发值$h(B)=1$（没有高估）。因此该启发式是可采纳的。
6. 最终扩展顺序：[S, B, G]。最优路径：S → B → G，总代价 = 5。

> **考试提示:** 即使答案显而易见，也要在A*搜索的每一步展示$f(n)$的计算过程，这样才能拿到满分。

## 搜索技术的考试对比

**方法对比**

CIE经常要求考生为给定问题选择合适的搜索技术，以下是核心优缺点总结：

- **BFS** — 适用于需要最短路径的小型浅层非加权问题
  - 优点: 保证最短路径，实现简单
  - 缺点: 空间复杂度为指数级，不适用于大型问题

- **DFS** — 适用于内存受限的大型深层问题
  - 优点: 空间复杂度极低，实现简单
  - 缺点: 不保证最短路径，存在无限循环风险

- **A*搜索** — 适用于能得到良好启发式的实际搜索问题
  - 优点: （使用可采纳启发式时）最优，比无信息搜索快得多
  - 缺点: 最坏情况空间复杂度高，性能依赖启发式质量

**考试命令词**

- **Compare** — 说明异同点，包括复杂度、最优性保证和应用场景 *(比较BFS和DFS搜索技术)*

- **Calculate** — 展示节点扩展和代价计算的所有中间步骤 *(计算A*搜索的扩展顺序)*

## 常见错误

- **错误做法:** 认为DFS总能找到非加权图中的最短路径
  - 原因: DFS按深度优先探索分支，因此第一次到达目标时经过的不一定是最短路径
  - 正确做法: 记住，只有BFS（用于非加权图）和A*（使用可采纳启发式）能保证得到最短路径
- **错误做法:** 混淆BFS和DFS的空间复杂度
  - 原因: 很多学生错误地认为DFS的空间复杂度比BFS更高
  - 正确做法: 记住：BFS空间复杂度为$O(b^d)$，DFS空间复杂度为$O(bm)$，在大型问题中BFS的空间复杂度远高于DFS
- **错误做法:** 认为无论启发式如何，A*总能得到最优解
  - 原因: A*只有在启发式可采纳（绝不会高估真实代价）时才能保证最优性
  - 正确做法: 在确认A*会输出最优路径前，一定要先检查启发式是否可采纳
- **错误做法:** 在目标节点首次被发现时就将其记为已扩展，而非在被选中扩展时才记录
  - 原因: CIE遵循标准A*流程：只有当节点从开放列表中被选中为f(n)最小的节点时，才会被扩展
  - 正确做法: 只有当目标节点被选中进行扩展时，才将其加入扩展顺序，不要在它首次被加入开放列表时就记录

## 速查表

| 技术 | 类型 | 空间复杂度 | 最优路径保证 | 应用场景 |
| --- | --- | --- | --- | --- |
| BFS | 无信息 | $O(b^d)$ | 是（非加权图） | 小型浅层问题 |
| DFS | 无信息 | $O(bm)$ | 否 | 大型深层问题，内存受限 |
| A* | 有信息 | $O(b^d)$ (worst) | 是（可采纳启发式时） | 有良好启发式的实际搜索 |

## 下一步

人工智能搜索技术是许多高级人工智能应用的基础，从路线导航到游戏寻路再到自动规划都有应用。对于CIE 9618考试而言，该主题经常与复杂度分析和图遍历问题结合出题，因此掌握这些核心概念能帮助你解答试卷1中各种各样的问题求解题目。你在这里学到的搜索策略也可以直接扩展到约束满足问题，这是大纲中考察的另一个常见人工智能主题。

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u13-ai-search-techniques/