人工智能搜索技术

CIE A-Level 计算机科学· 第13单元：计算思维与问题求解· 15 分钟阅读

1. 无信息（盲目）搜索★★☆☆☆⏱ 4 min

📘 定义

无信息搜索

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

例:

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

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
1. 出队A，将A加入扩展顺序，将未访问的邻居B、C入队。扩展顺序：[A]
3
1. 出队B，将B加入扩展顺序，将未访问的邻居D、E入队。扩展顺序：[A, B]
4
1. 出队C，将C加入扩展顺序，将未访问的邻居F入队。扩展顺序：[A, B, C]
5
1. 出队D，将D加入扩展顺序（无未访问邻居）。扩展顺序：[A, B, C, D]
6
1. 出队E，将E加入扩展顺序（无未访问邻居）。扩展顺序：[A, B, C, D, E]
7
1. 出队F，将F加入扩展顺序，将未访问的邻居G入队。扩展顺序：[A, B, C, D, E, F]
8
1. 出队G（目标节点），将G加入扩展顺序。最终顺序：[A, B, C, D, E, F, G]

Exam tip:

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

2. 时间复杂度与空间复杂度★★★☆☆⏱ 3 min

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

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

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

✓ 快速检测

测试你的理解：

对于深度为 $d$ 的目标，BFS的空间复杂度是多少？
- $O (b d)$
- $O (b^{d})$
- $O (b^{m})$
显示答案
1 —
回答正确！BFS需要存储到深度 $d$ 为止的所有节点，因此空间复杂度是指数级的。
哪个算法能保证找到非加权图中的最短路径？
- DFS
- BFS
- Neither
显示答案
1 —
回答正确！BFS在深入下一层前会探索当前层的所有节点，因此第一次到达目标时经过的就是最短路径。

3. 有信息搜索：A*算法★★★★☆⏱ 5 min

📘 定义

有信息搜索

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

📘 定义

可采纳启发式

绝不会高估从当前状态到达目标的实际代价的启发函数。如果启发式是可采纳的，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
1. 选择 $f (n)$ 最小的节点（B），将B加入扩展顺序。
4
1. 扩展B，计算 $f (G) = (3 + 2) + 0 = 5$ ，G是目标节点。
5
1. 验证可采纳性：A到G的真实代价 = 5，启发值 $h (A) = 4$ （没有高估）。B到G的真实代价 = 2，启发值 $h (B) = 1$ （没有高估）。因此该启发式是可采纳的。
6
最终扩展顺序：[S, B, G]。最优路径：S → B → G，总代价 = 5。

Exam tip:

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

4. 搜索技术的考试对比★★★☆☆⏱ 3 min

方法对比

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

BFS

适用于需要最短路径的小型浅层非加权问题

+ 优点: 保证最短路径，实现简单

− 缺点: 空间复杂度为指数级，不适用于大型问题

DFS

适用于内存受限的大型深层问题

+ 优点: 空间复杂度极低，实现简单

− 缺点: 不保证最短路径，存在无限循环风险

A*搜索

适用于能得到良好启发式的实际搜索问题

+ 优点: （使用可采纳启发式时）最优，比无信息搜索快得多

− 缺点: 最坏情况空间复杂度高，性能依赖启发式质量

5. 常见陷阱

错误做法:

认为DFS总能找到非加权图中的最短路径

原因:

DFS按深度优先探索分支，因此第一次到达目标时经过的不一定是最短路径

正确做法:

记住，只有BFS（用于非加权图）和A*（使用可采纳启发式）能保证得到最短路径

错误做法:

混淆BFS和DFS的空间复杂度

原因:

很多学生错误地认为DFS的空间复杂度比BFS更高

正确做法:

记住：BFS空间复杂度为 $O (b^{d})$ ，DFS空间复杂度为 $O (bm)$ ，在大型问题中BFS的空间复杂度远高于DFS

错误做法:

认为无论启发式如何，A*总能得到最优解

原因:

A*只有在启发式可采纳（绝不会高估真实代价）时才能保证最优性

正确做法:

在确认A*会输出最优路径前，一定要先检查启发式是否可采纳

错误做法:

在目标节点首次被发现时就将其记为已扩展，而非在被选中扩展时才记录

原因:

CIE遵循标准A*流程：只有当节点从开放列表中被选中为f(n)最小的节点时，才会被扩展

正确做法:

只有当目标节点被选中进行扩展时，才将其加入扩展顺序，不要在它首次被加入开放列表时就记录

6. 速查表

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

7. 常见问题

考试中我需要记住各种搜索的复杂度值吗？

需要，CIE阅卷官经常会要求比较时间和空间复杂度，因此你需要记住所有常见搜索技术的大O复杂度值。

真题中的出现

AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。

2022 · 1
搜索算法比较
2023 · 1
A*搜索路径计算
2024 · 1
无信息搜索复杂度问题

深入阅读

syllabusCIE 9618 2026 大纲第32页官方搜索技术大纲章节

下一步

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