★ FEATURED ARTICLE 这是我人工智能系列笔记里实操性最强的一章。第四章搜索策略与问题求解。不少初学者翻到教材这一章看着满屏的树、图、队列、优先队列会觉得这跟智能两个字根本没搭上边但等你真正把八数码、路径规划、迷宫寻路这类问题亲手跑通再回头看这一章会发现搜索其实是大量AI问题的底层共性——棋类游戏的决策树、机器人的路径规划、知识图谱里的关系查找本质上都是在巨大的状态空间里找一条路。这一章的核心任务就是把找路这件事从直觉变成可描述的数学形式再变成能运行的代码。不同教材的章节顺序略有差异但搜索这块内容基本都落在第四章附近各个版本都绕不开它。1. 第四章在AI知识体系中的位置与核心思路1.1 为什么搜索会被单独拎出来讲一章如果你把AI看成一门如何让程序自己找到答案的学科搜索就是最朴素也最关键的一类方法。早期AI研究的相当一部分精力都花在如何高效地搜索上。后来深度学习火起来大家开口闭口是神经网络、梯度下降但仔细想一下模型训练时的参数寻优本质上是在一个高维空间里搜索一组好参数自然语言生成时每个token的选择也是在候选词集合里搜索最合理的下一个词。搜索并没有过时它只是换了个名字藏在了各种现代算法的底层。教材里把它安排在第四章逻辑上也很顺。前三章通常会讲清楚什么是智能体、什么是理性决策、怎么把一个问题描述清楚第四章就要解决描述完之后怎么找到解的问题。搜索是连接问题定义和求解方法的桥梁。学完这一章你再看后面章节里的博弈树、约束满足、规划问题会发现它们都共用同一套状态空间思维只是换了不同的搜索策略而已。拿到这一章我心里给它的定位是不只学几个算法而是建立一切问题都可以建模成状态空间然后通过搜索求解的视角。带着这个视角去读后面的章节会比死记硬背算法好得多。1.2 问题形式化写代码前最容易被忽略的一步搜索的第一步不是写算法而是把问题形式化。这一节经常被初学者跳过去觉得能做题就行结果一写代码就翻车。这里以八数码为例这是第四章的经典问题一个3x3棋盘上放了1到8八个数字和空格每次只能把空格和相邻数字交换目标是摆成目标排列。形式化需要定义五样东西要素八数码中的具体含义状态一个3x3棋盘的全部排列情况初始状态题目给定的乱序棋盘动作空格向上下左右移动转移模型给定状态和动作返回移动后的新状态目标测试判断当前状态是否等于目标排列路径代价每移动一步代价为1路径总代价是步数很多同学卡住不是因为不懂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 完备性、最优性与复杂度对比这四个指标是面试和考试的高频点完备性、最优性、时间复杂度和空间复杂度。我整理了一张表学的时候直接对着记。算法完备性最优性时间复杂度空间复杂度BFS完备仅每步代价相同时最优O(b^d)O(b^d)DFS在有限状态空间下完备否O(b^m)O(bm)一致代价搜索完备是O(b^(1⌊C*/ε⌋))同左这里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 // 3col 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 distA*主循环用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*的时候先跑一个最简单的初始状态比如只差一步的目标确认基础逻辑没问题再上复杂状态。这样一旦出错你能立刻缩小排查范围。搜索这一章最迷人的地方在于你能亲眼看到同一个问题不同策略的效率差距可以大到几百倍这种直观感受比任何理论描述都更有说服力。
阅读完成 · 觉得有帮助？
