- 状态空间
- 路径搜索
START WITH A QUESTION
出口在地图上，怎样一步步走到那里？
你站在迷宫入口，知道哪些路口相连，却不知道该先走哪条路。每一次选择都会改变位置。可以不断尝试，但如果总是回到已经走过的路口，就会浪费时间。搜索把这种尝试组织成有顺序、可记录的过程。
本课使用六个地点构成的地图。广度优先先看近处的所有选择，深度优先先沿一条分支继续走。两者都不需要训练模型；差别在于先探索哪个候选状态。
BUILD YOUR VOCABULARY
先把三个概念讲清楚
状态与行动
状态描述当前情况，行动规定可以怎样改变情况。地图中，状态可以是所在路口，行动可以是走到相邻路口。
从入口 S 可以走到 A 或 B，但不能直接跳到终点 G。
待探索集合与已访问集合
前者记录未来还要检查的状态，后者防止反复探索相同状态。一个集合负责安排顺序，另一个负责避免循环。
访问过 A 后，遇到回到 A 的道路时不再重复加入。
路径长度与代价
长度可以是行动次数，代价可以是时间或距离。广度优先在每一步代价相同时找到最少步数的路径；道路代价不同就不能直接等同于最便宜。
两段很长的道路，可能比三段短路更慢。
FOLLOW THE PROCESS
把原理放进完整流程
- 01
加入起点
将只含起点的路径放进待探索集合，记录已经见过的状态。
- 02
取出候选
广度优先从队首取出；深度优先从栈顶取出。
- 03
展开邻居
沿着合法道路加入尚未访问的状态，并保留到达它的路径。
- 04
判断与停止
找到目标就返回路径；候选耗尽则说明在当前地图中不可达。
| 已探索深度 | 可能到达 | 已知事实 |
|---|---|---|
| 0 步 | S | 起点已知 |
| 1 步 | A、B | 先考察所有一步可达位置 |
| 2 步 | C、D | 新状态保存来路，重复状态跳过 |
| 3 步 | G | 等代价时已找到最少步数路径 |
CHANGE ONE THING & OBSERVE
逐步比较广度优先与深度优先
切换策略，点击下一步。观察图上当前节点、已访问节点、候选集合和最终路径；所有边的代价都是 1。
到达当前节点的路径：S。继续展开候选。
候选集合按内部队列或栈的存储顺序显示；深度优先从右端取出。本例在发现节点时去重。
KNOW THE LIMITS
哪些结论不能直接推出？
先找到不等于代价最低
深度优先可能先找到较长路线；广度优先的最少步保证也要求每步代价相同。
启发式不是凭空猜答案
启发式是估计剩余代价的线索。A* 等方法会利用它引导搜索，本课先掌握不使用估计的两种策略。
READ, RUN & EXPLAIN
用 Python 队列执行广度优先搜索
以下示例仅使用 Python 3 标准库，可复制到本地 Python 环境运行。先看每一行的作用，再修改一个输入观察结果；无需网络或密钥。
from collections import deque
graph = {'S': ['A', 'B'], 'A': ['C'], 'B': ['D'], 'C': ['D'], 'D': ['G'], 'G': []}
queue = deque([['S']])
seen = {'S'}
while queue:
path = queue.popleft()
if path[-1] == 'G':
print(path); break
for node in graph[path[-1]]:
if node not in seen:
seen.add(node)
queue.append(path + [node])复制或下载只获取本课示例，不会自动执行。
逐行解释（12 行）
- 第 1 行
from collections import deque导入双端队列，方便从开头取出较早加入的候选。
- 第 2 行
graph = {'S': ['A', 'B'], 'A': ['C'], 'B': ['D'], 'C': ['D'], 'D': ['G'], 'G': []}字典记录各地点的相邻地点。与开场和互动使用同一张六地点地图。
- 第 3 行
queue = deque([['S']])队列里的每一项是一条完整路径，最初只有起点。
- 第 4 行
seen = {'S'}集合保存已经加入过的地点，避免循环与重复。
- 第 5 行
while queue:只要还有候选，就继续搜索。
- 第 6 行
path = queue.popleft()取出最早加入的路径，因此先探索更短的路径。
- 第 7 行
if path[-1] == 'G':-1 表示列表最后一项；检查路径末尾是否为终点。
- 第 8 行
print(path); break找到目标就打印路径，并退出循环。分号分隔两个简短语句。
- 第 9 行
for node in graph[path[-1]]:枚举当前地点可以到达的相邻地点。
- 第 10 行
if node not in seen:只处理还没有加入过的地点。
- 第 11 行
seen.add(node)及时记录，避免其他分支重复加入。
- 第 12 行
queue.append(path + [node])创建延长后的新路径，放到队尾等待探索。
['S', 'B', 'D', 'G']
CHECK YOUR UNDERSTANDING
换一个角度，检查自己是否理解
已回答 0 / 3 题 · 当前答对 0 题
TAKE IT WITH YOU
带走三个判断，再做一次迁移练习
- 搜索从状态、行动和目标构成的问题出发。
- 广度与深度优先的核心差异是候选探索顺序。
- 地图正确性、代价定义和访问记录共同影响结果。
参考与延伸阅读
本课例子、代码和模拟数据为教学设计。以下一手文档用于延伸核对，不代表对本示例的认证。
- Python 官方教程：数据结构列表、集合与队列等示例语法参考。
- scikit-learn：模型评估评估指标与预测、决策的区别。
- IBM：检索增强生成检索与生成组合的进一步说明。
- NIST：AI 风险管理框架可靠性与风险管理的延伸阅读；不是特定项目的合规结论。