这是我人工智能系列笔记里，实操性最强的一章。第四章，搜索策略与问题求解。不少初学者翻到教材这一章，看着满屏的树、图、队列、优先队列，会觉得这跟"智能"两个字根本没搭上边；但等你真正把八数码、路径规划、迷宫寻路这类问题亲手跑通，再回头看这一章，会发现搜索其实是大量AI问题的底层共性——棋类游戏的决策树、机器人的路径规划、知识图谱里的关系查找，本质上都是在巨大的状态空间里"找一条路"。这一章的核心任务，就是把"找路"这件事从直觉变成可描述的数学形式，再变成能运行的代码。不同教材的章节顺序略有差异，但搜索这块内容基本都落在第四章附近，各个版本都绕不开它。

1. 第四章在AI知识体系中的位置与核心思路

1.1 为什么搜索会被单独拎出来讲一章

如果你把AI看成一门"如何让程序自己找到答案"的学科，搜索就是最朴素也最关键的一类方法。早期AI研究的相当一部分精力，都花在如何高效地搜索上。后来深度学习火起来，大家开口闭口是神经网络、梯度下降，但仔细想一下：模型训练时的参数寻优，本质上是在一个高维空间里搜索一组好参数；自然语言生成时每个token的选择，也是在候选词集合里搜索最合理的下一个词。搜索并没有过时，它只是换了个名字，藏在了各种现代算法的底层。

教材里把它安排在第四章，逻辑上也很顺。前三章通常会讲清楚什么是智能体、什么是理性决策、怎么把一个问题描述清楚，第四章就要解决"描述完之后，怎么找到解"的问题。搜索是连接"问题定义"和"求解方法"的桥梁。学完这一章，你再看后面章节里的博弈树、约束满足、规划问题，会发现它们都共用同一套状态空间思维，只是换了不同的搜索策略而已。

拿到这一章，我心里给它的定位是：不只学几个算法，而是建立"一切问题都可以建模成状态空间，然后通过搜索求解"的视角。带着这个视角去读后面的章节，会比死记硬背算法好得多。

1.2 问题形式化：写代码前最容易被忽略的一步

搜索的第一步不是写算法，而是把问题形式化。这一节经常被初学者跳过去，觉得"能做题就行"，结果一写代码就翻车。这里以八数码为例，这是第四章的经典问题：一个3x3棋盘上放了1到8八个数字和空格，每次只能把空格和相邻数字交换，目标是摆成目标排列。

形式化需要定义五样东西：

很多同学卡住，不是因为不懂BFS或A*，而是状态表示没设计好。比如用二维列表表示棋盘，每次移动要深拷贝，又慢又容易错；用一维元组(tuple)表示九个位置，空格下标直接算行列，移动只需交换两个元素，又快又稳。这个细节我放在后面实操部分展开，但形式化阶段就要想清楚。

还有个容易被忽略的点：目标测试不一定是"状态完全相等"。有些问题只要达到某种条件就算成功，比如八皇后问题要求任意两个皇后不互相攻击。这提醒我们，形式化方案是为问题服务的，不是为算法服务的。你把状态定义清楚了，后面写转移、写判重、写启发函数都会顺很多。

1.3 搜索树与"可行解"的本质

形式化做完，问题就变成了状态空间里的搜索问题。搜索过程会隐式地建一棵搜索树：根节点是初始状态，从某个节点展开动作得到子节点，子节点继续展开，直到找到目标。这里有个关键区分：节点和状态不是一回事。节点记录的是"从起点到当前状态的路径信息"，状态只描述"当前局面"。同一个状态可能通过不同路径到达，对应搜索树里的不同节点，但局面是一样的。

我一般用旅行规划来类比。假设你要从A城市去D城市，状态就是"当前在哪座城市"，节点则是"完整的行程记录"，比如A到B再到C。同样的C城市，可能是经过B来的，也可能是经过E来的，两种方案的"当前状态"相同，但路径不同，代价也不同。搜索算法要处理的，正是在这些路径里选一条最划算的。

为了避免无限循环，一般要维护一个已探索集合（closed set）。比如八数码里空格先右移再左移，状态会回到原点，如果不判重，BFS和DFS都会陷入毫无意义的重复展开。闭环处理得不好，再好的算法也是空谈，这一点到第6节我会专门说。

2. 无信息搜索：先把基础打牢

2.1 BFS和DFS：两种最极端的策略

无信息搜索指的是搜索时除了问题本身，没有任何额外信息，只能盲目地展开节点。最典型的两个是广度优先搜索(BFS)和深度优先搜索(DFS)。

BFS用队列实现。队列的特点是先进先出，就像银行取号叫号，先来先办。每一层的节点全部展开完毕，才会进入下一层。所以BFS从根节点出发，一层一层往外探，像水波扩散一样。DFS用栈实现，后进先出，像摞盘子，后放的先拿走。DFS会沿着一条路一路走到黑，走不通了才回头换另一条路。

从结果看，BFS的优势是完备且有最优性的：只要解存在，BFS一定能找到，而且如果每步代价相同，它找到的第一个解就是步数最少的解。缺点是空间消耗大，最后一层的节点都要存在内存里，深度一深就爆炸。DFS正好相反：空间消耗小，只需要保存一条路径上的节点，但可能一头扎进死胡同出不来，遇到无限分支还会找不完。

我刚开始学的时候也纳闷，为什么教科书要讲看起来这么笨的算法？后来才明白，它们是后面所有高级搜索的底座。BF S的"逐层展开"思想贯穿到一致代价搜索，DFS的"压栈回溯"思想贯穿到深度受限搜索和迭代加深。不懂这两个基础，后面的变体全都看不懂。

2.2 一致代价搜索：当每步代价不一样时

BFS有个隐含假设：每走一步代价相同，所以步数最少就是代价最小。但现实问题里，不同动作的代价往往不同。比如地图导航里，走高速和走小路的时间不一样，不能光看经过了多少个路口。这时候BFS就不顶用了，得用一致代价搜索。

一致代价搜索依然用优先队列，但排序键是路径代价g(n)，每次从队里取出代价最小的节点展开。这其实就是Dijkstra算法的思想：不断从已知代价最小的顶点出发松弛邻居。如果所有边权都是1，一致代价搜索就退化成BFS；如果边权不同，它依然能保证找到代价最小的路径，这一点比BFS更通用。

不过一致代价搜索也有代价：它会被代价小的路径拖着走，如果有一条代价很低但路很长的迂回路径，它可能把大量时间耗在探索这条路径上，导致效率下降。这也引出了下一节的核心问题：能不能让搜索"有方向感"，而不是像无头苍蝇一样乱转。

2.3 完备性、最优性与复杂度对比

这四个指标是面试和考试的高频点：完备性、最优性、时间复杂度和空间复杂度。我整理了一张表，学的时候直接对着记。

这里b是分支因子，d是最浅解的深度，m是搜索树最大深度，C*是最优解的代价，ε是最小边权。看这张表的时候，要抓住两个核心矛盾：一是时间和空间的矛盾，二是完备最优和效率的矛盾。BFS和DFS正好站在天平两端，一致代价站在BFS的肩膀上但更通用。

深度优先的改进版是迭代加深DFS，做法是不断加深深度限制，一遍遍地跑深度受限DFS。它既保留了DFS的空间优势，又获得了BFS的完备性和最优性，只是会重复展开上层节点，好在代价通常可以接受。这是面试里经常被追问的知识点，建议自己写一遍。

3. 启发式搜索：让程序学会"挑路走"

3.1 启发函数怎么选：从曼哈顿距离说起

无信息搜索最大的痛点是盲目。以八数码为例，明明目标排列就在某个方向上，程序还是四平八稳地一层层往外扩。启发式搜索的思路是引入一个启发函数h(n)，用它对"当前状态到目标状态还需要多少代价"做估计，让搜索优先展开有希望的方向。

八数码里最常用的启发函数是曼哈顿距离：计算每个数字当前位置与目标位置的行列差绝对值之和。为啥叫曼哈顿？因为曼哈顿的街道是棋盘网格，从一个街口到另一个街口，只能横着走竖着走，走过的"格子距离"就是横纵距离之和。用代码写就是遍历九宫格，对每个非空格数字计算两次行差和列差。

h(n)的大小直接决定搜索效率。h(n)越接近真实的剩余代价，A*展开的节点就越少；h(n)与实际值偏差太大，搜索效率就会退化。八数码里还有一个更弱的启发函数是"错误位置计数"，数一数有多少个数字不在目标位置。这个函数计算快，但估计精度低，展开的节点数会明显多于曼哈顿距离。想验证差异的同学，可以把两种启发函数跑到同一个初始状态，对比展开节点数，效果非常直观。

3.2 贪婪最佳优先搜索的诱人与翻车

有一种很自然的思路：每次只选h(n)最小的节点展开，完全不关心已经走过的路。这就是贪婪最佳优先搜索，它极其"激进"，一路朝着自认为离目标最近的方向冲，跑得飞快。

问题是它经常翻车。h(n)只是估计，不是真实距离。八数码里，某个状态可能看起来离目标很近，实际上那条路是死路，走到一半才发现目标在另一个方向。贪婪最佳优先可能先冲进一条死路才能退回来，甚至因为贪心而找到一条绕远路的解。它的本质是"只看眼前不看全局"，像开车时只盯着导航显示的剩余距离，却忽视了已经绕了多少冤枉路。

我踩过这个坑：用贪婪最佳优先求解某个初始状态，展开节点数确实少，但解出来的步数比最优解多了好几步。追求"快的解"和"最优解"是完全不同的目标，很多竞赛题刁钻的地方就在这里。所以它适合用来做快速近似，不适合要求最优解的场合。

3.3 A*算法：在已走的路和未走的路之间找平衡

A*算法可以说是启发式搜索里最经典的存在。它定义评估函数f(n) = g(n) + h(n)，其中g(n)是起点到当前节点的实际代价，h(n)是对当前节点到目标的估计代价，f(n)就是对"从起点经过当前节点再到目标"的总代价估计。

A的策略很朴素：优先展开f(n)最小的节点。它既不像一致代价搜索只认已走的路，也不像贪婪最佳优先只认没走的路，而是把两者放在一起权衡。这个"混合"听起来简单，实际效果却非常好：只要h(n)满足一定条件，A就能保证找到最优路径，而且展开节点数在所有最优搜索算法中最少。

用生活类比就是：你要去一个陌生城市，既知道你已经在路上花了多长时间，也知道导航估算还要多久，你自然倾向于走那种"已经花的时间加剩余估计时间"最小的路线。A*里的g是真实开销，h是估算，f就是你的决策依据。

3.4 A*最优性的条件：可采纳性与一致性

A*不是随便写个h就能保证最优的，有两个数学条件特别关键。

第一个是可采纳性，要求h(n) <= h*(n)，其中h*(n)是当前状态到目标的真实最小代价。也就是说，启发函数永远不能高估剩余代价。曼哈顿距离是八数码的可采纳启发函数，因为每个数字至少要走这么多步，任何情况下都不会高估。反过来，如果你自作聪明把h乘以2，虽然搜索会快很多，但找到的路径不保证最优。

第二个是一致性（也称单调性），要求对于任意状态n及其后继n'，满足h(n) <= c(n, a, n') + h(n')。这个条件比可采纳性更强。满足一致性时，f值沿路径单调不减，A*首次展开某个节点时就已经找到了它的最优代价，这样图搜索版本也能保证最优。实际操作中，曼哈顿距离满足一致性，所以可以放心用closed集合判重。

这两个条件看着数学味重，但理解后对调试帮助极大。如果你的A*运行结果不是最优，第一反应就应该是检查h是不是高估了，而不是去改代码逻辑。

4. 局部搜索：不关心路径，只关心终点

4.1 为什么有些问题不需要全局搜索

搜索章节后半部分会讲一类完全不同的方法：局部搜索。这类问题的特点是，解是一个完整的配置，而不是一条路径。比如八皇后问题要找一个不冲突的摆放方案，我们并不关心"怎么一步步摆到那里"，只要最终方案正确即可。

对这类问题，树搜索那套思路反而笨重。你可以想象一个地形图，横轴纵轴是变量的取值，高度是解的质量。找最优解就是在这样的地形里找最高点。局部搜索的思路很简单：从一个候选解出发，不断向相邻状态移动，直到到达一个"不错"的位置为止。它不维护搜索树，不需要回溯，只用少量内存就能应对超大规模问题。

第一次接触局部搜索时，我最大的感触是：并不是所有AI问题都要"从起点找到目标路径"，很多实际问题只是要"找到一个足够好的答案"。把问题分类成"路径问题"和"状态问题"，是选择算法前最重要的一步。

4.2 爬山法：快是快，但容易困在半山腰

爬山法是最简单的局部搜索算法。它从当前状态出发，看所有邻居状态，选择其中质量最好的那个移过去，然后重复，直到没有邻居比当前状态更优。就像一个近视的人蒙着眼在山里找顶，每一步都往坡度最大的方向走。

它的致命弱点是局部最优。我举个例子：你走到一个山脊上，发现周围不论哪个方向都往下走，于是认为自己到顶了，但真正的山顶离你还有几个山头的距离。爬山法看不到全局，一旦进入这种"局部最优陷阱"就出不来了。还有一种更尴尬的情况是平顶或者山脊，多个邻居质量一样，它会随机挑一个，可能原地打转。

教材里通常会有几个改进方向：随机重启爬山法（多换几个起点重新爬）、模拟退火（允许暂时往低处走）、侧移（允许走到质量相同的邻居）。这些改进并不能保证找到全局最优，但能大幅提高找到好解的概率。实操里我建议先用随机重启，代码简单，效果却立竿见影。

4.3 模拟退火与随机重启：摆脱局部最优的思路

模拟退火从金属冷却工艺得到启发：先把金属加热到高温，再慢慢降温，让分子有足够时间排列成低能量结构。对应到算法里，搜索过程中以一定概率接受比当前解更差的邻居，这个概率随"温度"降低而减小。温度高的时候，算法敢于乱跳，跳出局部最优；温度低的时候，行为趋近于爬山法，逐渐收敛。

这里的核心心得是"概率接受坏解"的时机。我把初始温度和降温速率调整过很多次，发现温度降得太快，算法还没跳出局部最优就固化了，跟爬山法没什么区别；降得太慢，算得慢且不稳定。实际做的时候，要针对问题规模调参数，没有放之四海而皆准的值。

随机重启的思路更直白：从多个随机初始状态出发各跑一遍爬山法，最终取所有结果里最好的那个。它不保证找到全局最优，但能显著降低"一次运气不好就全军覆没"的风险。这类方法在资源调度、排课、布局优化等场景里非常实用，也是后面遗传算法等进化类方法的雏形。

5. 实操：用Python从零实现A*解决八数码

5.1 状态表示与相邻状态生成

理论讲再多，不如跑一段代码。下面是我建议的状态设计方案：用长度9的元组表示棋盘，数字0代表空格，位置下标从左到右、从上到下依次是0到8。比如(1,2,3,4,5,6,7,8,0)就是目标状态。

空格在哪个位置，能往哪移动，通过下标换算行列：row = index // 3，col = index % 3。上下左右四个方向就是对行列坐标做加减，再判断是否越界。生成邻居时，先转成列表，交换空格和目标位置的下标，再转回元组。用元组的好处是它可哈希，能直接放进set判重，也能作为字典的键。

GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0) def get_neighbors(state): i = state.index(0) r, c = i // 3, i % 3 for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)): nr, nc = r + dr, c + dc if 0 <= nr < 3 and 0 <= nc < 3: j = nr * 3 + nc lst = list(state) lst[i], lst[j] = lst[j], lst[i] yield tuple(lst)

这段代码量不大，但把状态转移写得很干净。设计时我特意避开二维数组，因为一维元组在判重和比较时更省事。写到这里也想提醒一句：状态表示方式决定了后续所有代码的复杂度，这里多花十分钟思考，后面能省一个小时。

5.2 启发函数与优先队列实现

启发函数用曼哈顿距离。对每个非空格数字，计算它在当前棋盘的行列和目标棋盘的行列，累加绝对值差。代码里的目标行列直接用数字倒推：数字k的目标位置是(k-1)//3和(k-1)%3，因为目标排列是1到8按顺序排，0在末尾。

def manhattan(state): dist = 0 for idx, val in enumerate(state): if val == 0: continue r, c = idx // 3, idx % 3 tr, tc = (val - 1) // 3, (val - 1) % 3 dist += abs(r - tr) + abs(c - tc) return dist

A*主循环用Python的heapq实现优先队列。堆里的每个元素是(f, g, state)，按f值从小到大排序；f相同就比g，再相同就比state本身。为了记录路径，我用了两个字典：came_from记录每个状态从哪个状态转移而来，cost_so_far记录到达该状态的最短代价。当目标状态第一次出队时，沿came_from回溯就能拼出完整路径。

细节上要注意：入队前检查新代价是否优于历史记录，只有更优时才更新并入队。这样既避免无意义的重复入队，也保证A*的正确性。

5.3 完整代码与运行分析

下面是完整实现，把之前的内容串起来。

import heapq def a_star(start): if start == GOAL: return [start], 0, 0 frontier = [] heapq.heappush(frontier, (manhattan(start), 0, start)) came_from = {start: None} cost_so_far = {start: 0} explored = set() expanded = 0 while frontier: f, g, state = heapq.heappop(frontier) if state in explored: continue explored.add(state) expanded += 1 if state == GOAL: path = [] cur = state while cur is not None: path.append(cur) cur = came_from[cur] return path[::-1], cost_so_far[state], expanded for nxt in get_neighbors(state): new_g = g + 1 if nxt not in cost_so_far or new_g < cost_so_far[nxt]: cost_so_far[nxt] = new_g priority = new_g + manhattan(nxt) heapq.heappush(frontier, (priority, new_g, nxt)) came_from[nxt] = state return None, 0, expanded

用几个初始状态跑一下，比如start = (1,2,3,4,0,5,6,7,8)，输出目标步数和展开节点数。你会看到曼哈顿距离驱动的A*展开节点数远少于BFS，而且解出来的路径是最优的。想加深理解的话，把manhattan换成错误位置计数，对比同样输入下的展开节点数，差距会是数量级的。

运行时的观察点我列两个：一是展开节点数，这个数字直接反映算法效率；二是搜索树深度，对应着解的步数。把这两个数字和BFS对比，你才能真正感受到启发函数的价值。

6. 常见问题与避坑指南

6.1 状态爆炸：为什么你的搜索跑不动

八数码的状态空间总共是9!个排列，约36万种，BFS在多数初始状态下还行；但换成15数码，状态空间变成16!，直接量级爆炸。无信息搜索在这种规模下完全跑不动，网络上有不少求解器能处理几十步的八数码，核心原因就是用了A*加曼哈顿距离这类强启发。

遇到搜索跑不动，第一件事不是优化代码，而是检查搜索空间和启发函数。我见过有人用BFS跑15数码，跑了十分钟没出结果，换成A加曼哈顿距离后秒出答案。搜索算法领域有个经验法则：如果能设计出一个好的启发函数，效果比任何代码层面的微优化都显著。这也是为什么第四章花了大量篇幅讲贪心和A，而不是教你怎么把BFS写得更快。

6.2 启发函数高估的隐患

A代码看起来对了，但跑出来的路径不是最优，这是很隐蔽的坑。问题几乎都出在启发函数上。只要h(n)曾经高估过真实代价，A就可能提前放弃一条实际最优的路径，因为它的f值被算大了。

我调试过一个问题，用了一个看似合理的启发函数，结果解的步数比最优解多两步。排查了很久才发现是这个函数在某些状态下高估了。修好之后，步数立刻回到最优。建议所有人在动手写A前，先写一个暴力BFS做基准，用小规模问题对比A的步数和展开节点数。如果A*的路径不是最优，第一嫌疑就是启发函数不满足可采纳性。

6.3 判重与优先级队列的细节坑

代码里有个常见问题：用list做判重。八数码状态一共才36万种，list的in检查是O(n)，虽然小规模能跑，但15数码一上来就卡死。正确做法是用set存元组状态，查找是O(1)。另外，如果你在heapq里直接存(f, state)，Python会在f相同时去比较state元组本身，这个没问题，但如果你在元组里混入了list类型的路径字段，就会引发严重的性能问题，因为list比较是逐元素递归的。

我的建议是：路径不要塞进优先队列，用came_from字典回溯；优先队列元素限定为可比较的、定长的数据。这样既快又不容易踩坑。另一个容易被忽略的问题是closed集合的更新时机，A*主循环里要在出队时判重而不是入队时判重，否则可能错过更优的到达路径。这一点我在代码里特意用了出队判重的写法。

6.4 学习地图与后续章节衔接

搜索这一章是整个AI基础的地基，学完它应该能在脑子里画出地图：无信息搜索解决"我不会失败但要慢慢找"的问题；启发式搜索解决"我知道目标在哪所以找得快"的问题；局部搜索解决"我不关心路径只要好答案"的问题。后面学博弈搜索时，Minimax和Alpha-Beta剪枝就是在搜索树基础上加了对局双方的博弈视角；学约束满足问题时，回溯搜索和推理是处理离散组合的利器。

建议学完这一章做三件事巩固：第一，把八数码的BFS、一致代价、贪婪最佳优先、A各写一遍，对比展开节点数；第二，把A的启发函数换掉，观察最优性和效率变化；第三，找一个地图最短路径问题，把八数码代码改成通用状态空间搜索框架。做完这三件事，这一章你就真正吃透了。

我个人在实际操作中最深的体会是，别急着把代码写漂亮，先把状态定义和启发函数想清楚。状态定义错了，后面所有代码都是白写；启发函数选对了，整个算法的性能天差地别。还有一个屡试不爽的小技巧：调试A*的时候，先跑一个最简单的初始状态，比如只差一步的目标，确认基础逻辑没问题，再上复杂状态。这样一旦出错，你能立刻缩小排查范围。搜索这一章最迷人的地方在于，你能亲眼看到同一个问题，不同策略的效率差距可以大到几百倍，这种直观感受比任何理论描述都更有说服力。