简介一套系统讲解人工智能搜索技术的PDF电子文档面向AI学习者、算法研究者及备考人员从问题求解的搜索本质出发依次介绍搜索技术概述、状态空间表示、盲目搜索、启发式搜索、A算法与A算法、博弈搜索与α-β剪枝法等核心内容。文档以农夫过河等经典问题为例演示状态向量建模与合法路径搜索并对比广度优先/深度优先与启发式搜索的差异深入解析A算法估价函数f(n)g(n)h(n)的计算逻辑同时介绍极小极大法与α-β剪枝如何通过上下限估计减少评估节点、提升博弈搜索效率。包体为单个PDF文件大小约6.54MB便于阅读与打印该资源上线后已有499人学习下载受到AI入门者与备考者的关注。通读后可帮助读者建立AI问题求解的完整知识框架掌握不同搜索策略的适用场景与效率权衡既可作为课堂教学的辅助材料也可作为项目实践中快速检索搜索方法与评估原理的参考。1. 人工智能搜索技术状态空间搜索到底在搜什么如果你接触过《人工智能》这门课大概率会在前几章碰到“搜索技术”这个词。第一次听会以为是怎么写百度或者 Elasticsearch 那种检索系统实际完全不是一回事。这里说的搜索是“状态空间搜索”把问题建模成一张图从初始状态出发通过一步步动作找到通向目标状态的路径。八数码、八皇后、迷宫寻路、机器人路径规划、走迷宫的小车全是同一套骨架。暴力枚举算法能解决规模极小的问题但状态空间一爆炸枚举就是空谈。这篇文章按“搜索技术概述 → 状态空间 → 盲目搜索 → 启发式搜索 → A 算法和 A* 算法”这条主干把每个环节的原理、能抄的代码、必须避开的坑一次讲透适合正在啃教材的学生也适合准备算法工程师面试、想快速重建这块知识框架的从业者。2. 状态空间把问题变成一张有向图2.1 状态、动作、转移搜索问题的标准四元组所有搜索问题都能拆成四个要素状态集合、动作集合、转移函数、目标测试。拿八数码举例状态就是 3×3 棋盘上数字的一种排列比如2831647_5动作是空格上下左右四个方向的移动转移函数告诉你在某个状态执行某个动作后会变成哪个新状态目标测试则判断当前状态是否等于12345678_。构造搜索问题的过程本质上就是把“现实问题”翻译成这一套形式化描述。这段翻译为什么重要因为它决定了你能不能写出通用的搜索代码。一个搜索算法只需要“四个接口”获取初始状态、判断当前状态是否到达目标、生成所有后继状态、以及在带代价的问题里计算某一步动作的代价。只要实现了这四个接口BFS、DFS、UCS、A* 全部可以复用同一套框架。很多初学者一上来就为具体问题写特化逻辑结果换一道题就要推翻重来其实亏在没做抽象。2.2 为什么状态空间大小直接决定你能不能跑搜索技术的难点不在“搜”而在状态空间太大。八数码的状态数是 9! 362880看起来不多但如果用暴力枚举算法把它们全部展开还要为每个状态记录路径内存就已经开始吃紧。十五数码是 16! ≈ 2.09×10^13暴力展开想都不要想。现实里的调度问题、路径规划问题状态空间通常是连续的或组合爆炸的这迫使我们必须引入启发式信息来减少探索。判断一个搜索问题值不值得做第一步永远是先估状态空间量级。这步没做好后面跑不通也不奇怪因为问题本身就决定了盲目搜索的天花板。我一般会先算两个数平均每步的分支因子 b以及从初始到目标的最短步数 d。b^d 就是最坏情况下的搜索量级。当这个值在百万级以内盲目搜索还能应付一旦上了亿级就该转去设计启发式函数了。2.3 从问题到代码建状态图和判重的第一步用 Python 写八数码的状态空间最常见做法是把棋盘压成字符串空格记为 0。字符串做哈希 key 很方便也省内存。下面这段是继任状态生成的核心逻辑from collections import deque GOAL 123456780 # 目标状态0 表示空格 def get_successors(state): 生成所有合法后继状态 i state.index(0) row, col divmod(i, 3) moves [] for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)): nr, nc row dr, col dc if 0 nr 3 and 0 nc 3: j nr * 3 nc sl list(state) sl[i], sl[j] sl[j], sl[i] moves.append(sl) return [.join(sl) for sl in moves]这里的参数就三个state是当前局面字符串row/col是空格位置dr/dc是尝试移动的四个方向。移动前必须做边界检查否则下标越界移动后把字符串转成 list 再交换位置是因为字符串在 Python 里不可变。返回值是后继状态列表BFS、DFS、A* 都能用。判重则靠一个visited集合记录已扩展过的状态避免同一个局面重复入队。另一个前置检查是逆序数奇偶性。八数码问题把棋盘从左到右从上到下展开成序列忽略空格位统计逆序对数量目标状态123456780的逆序数是 0是偶排列因此初始状态必须是偶排列才有解。很多人在 A* 里跑了半天没结果不是算法写错是起点本身无解。这个检查十分钟就可以补上def is_solvable(state): seq [int(c) for c in state.replace(0, )] inv 0 for i in range(len(seq)): for j in range(i 1, len(seq)): if seq[i] seq[j]: inv 1 return inv % 2 0值得强调的是逆序数检查依赖目标状态的具体排列。如果你把目标设成_12345678或者其他形状判断条件可能从“偶数”变成“奇数”。我习惯先写一个辅助函数把任意局面和目标局面分别求逆序数的奇偶再比较两者是否一致这样比硬记“偶可解”更不容易翻车。3. 盲目搜索不挑路的穷举法3.1 BFS 为什么是“理想化最短步数”的标准答案盲目搜索里最先被讲到的通常是广度优先BFS因为它逻辑最直观一层一层往外扩第一次碰到目标状态的路径就是最短路径。在八数码这类每步代价相同的问题上BFS 能保证最优解。实现上用普通队列deque即可def bfs(start, goalGOAL): if not is_solvable(start): return None queue deque([(start, [start])]) visited {start} while queue: state, path queue.popleft() if state goal: return path for nxt in get_successors(state): if nxt not in visited: visited.add(nxt) queue.append((nxt, path [nxt])) return None这里的核心参数是queue和visited。前者按层序保存待扩展状态后者做判重如果你把判重去掉BFS 会退化到暴力枚举算法小棋盘还可能跑完大一点的棋盘直接卡死。路径记录用的是path [nxt]在每次扩展时复制列表换来的是代码简单代价是内存开销明显上升。对八数码这种 36 万状态量级还能接受但如果状态空间上亿就得改成记录父节点链最后回溯生成路径。3.2 DFS 的深度受限与迭代加深省内存的代价深度优先DFS看起来很省内存一路扎下去只保存当前分支但有两个致命问题可能掉进死循环也可能找到的路径远非最短。八数码里如果来回走一步没有判重就永远走不出去即使判了重DFS 也可能先钻到一条超长分支里把大量时间耗在无用路径上。解决办法之一是深度受限 迭代加深Iterative Deepening DFS, IDDFS从深度 1 开始逐个增加限制每轮都重新跑一遍 DFS。这个做法把内存需求压到 O(深度) 的同时保留 BFS 的最短路径保证。代价是重复扩展节点不过对树搜索来说重复开销通常可以接受。代码大概长这样def dls(state, goal, depth, path, visited): if state goal: return path if depth 0: return None visited.add(state) for nxt in get_successors(state): if nxt not in visited: res dls(nxt, goal, depth - 1, path [nxt], visited) if res: return res return None def iddfs(start, goalGOAL, max_depth40): for depth in range(max_depth 1): res dls(start, goal, depth, [start], set()) if res: return res return None迭代加深里值得调的参数是max_depth和每轮 visited 的清理。每轮 DFS 都要新开一个 visited 集合否则上一轮的访问记录会错误地剪掉本轮该走的分支。我见过有人在历次迭代间复用同一个 visited结果深度限制增加后反而搜不到解这属于典型的参数生命周期管理失误。max_depth设多大取决于你对问题最短解长度的估计宁可稍微设大一点也不能小到把解拒之门外。剪枝算法这个说法在迷宫、游戏搜索里很常见迭代加深天然就是一种“时间换空间”的剪枝思路用深度限制剪掉不可能出解的分支以此控制递归深度。很多讲算法的人会把剪枝当作高级技巧但在盲目搜索里深度受限本身就是第一道剪枝。3.3 代价一致搜索UCS当每一步代价不一样八数码每走一步代价相同所以 BFS 就能求最短步数。但现实问题里动作代价往往不同比如机器人在地图上移动平路代价 1泥地代价 3。这种情况就得用代价一致搜索Uniform Cost Search, UCS它按累计代价 g(n) 从小到大扩展节点本质是 Dijkstra 算法在隐式图上的单源最短路径版本import heapq def ucs(start, goalGOAL): pq [(0, start, [start])] visited set() while pq: cost, state, path heapq.heappop(pq) if state goal: return path if state in visited: continue visited.add(state) for nxt in get_successors(state): step_cost 1 heapq.heappush(pq, (cost step_cost, nxt, path [nxt])) return NoneUCS 的实现要点是优先队列Python 里用heapq就是堆排序的经典应用插入和弹出都是 O(log n) 级别。visited在这里只记录已经弹出过的节点而不是入队时就去重因为第一次入队的路径不一定是最小代价路径直接去重会截断更优解。如果每条边代价都是 1UCS 和 BFS 的行为几乎一致代价不一样时BFS 的最短步数保证就失效了必须靠 UCS 来保证最小代价。4. 启发式搜索从“瞎走”到“带方向”4.1 启发式函数 h(n)可采纳性不是玄学盲目搜索最大的问题是“不看目标在哪里”。八数码里空格往哪个方向挪都能走但有的方向明显在远离目标。启发式搜索要做的就是用一个函数 h(n) 估计从状态 n 到目标还差多少步。注意h(n) 是“估计值”不是真实距离。这个估计值越接近真实距离搜索效率越高如果 h(n) 永远不大于真实代价就说它是可采纳的admissible这是一个决定算法能否叫 A* 的性质。最常见的两个启发式函数错位数字数和曼哈顿距离。错位数统计有多少数字不在目标位置显然每一块至少需要一步所以它可采纳。曼哈顿距离是每个数字当前位置到目标位置的行差加列差之和比如数字 2 要从第 1 行挪到第 0 行横向再挪 1 列那它对 h 的贡献就是 2。曼哈顿距离也不高估因为一个数字每次移动最多让它距目标近一格。用代码算曼哈顿距离def manhattan(state, goalGOAL): dist 0 for i, ch in enumerate(state): if ch 0: continue cur_r, cur_c divmod(i, 3) goal_idx goal.index(ch) goal_r, goal_c divmod(goal_idx, 3) dist abs(cur_r - goal_r) abs(cur_c - goal_c) return dist这里的开销在于每次都要goal.index(ch)查目标位置。如果进入搜索主循环这个函数会被调用很多次强烈建议预先把目标位置存成字典{数字: 目标索引}把一次 O(9) 的查找变成 O(1)。数据结构和算法那套分析在这类细节上特别管用很多面试也会问你怎么在几百万次 h 计算中减少常数开销。4.2 贪心最佳优先搜索只盯目标不看历史贪心最佳优先搜索是最简单的启发式搜索用优先队列按 h(n) 从大到小优先级扩展完全不看已经走的路程 g(n)。它跑得快但可能把总代价越带越大——典型行为是“看起来快到了目标然后被堵在死胡同里”。如果 h 设计得不好贪心搜索甚至可能比 BFS 更慢因为它在局部最优的方向上浪费太多扩展。贪心搜索适合的场景是你只想要一个解不要求最优而且启发式函数非常准。比如某些实时策略游戏的单位寻路能走通就行不追求全局最短。但在八数码这种问题里我一般不建议单独用贪心它更适合作为 A* 的设计起点既然 h 能引路那在引路的同时也把已经走的路段计入代价是不是就不会瞎冲了这就引出了下一节的核心。4.3 A 算法与 A* 算法f g h 的一个“星”差在哪A 算法把搜索代价定义为 f(n) g(n) h(n)其中 g(n) 是从起点到当前状态的实际代价h(n) 是启发式估计值。它比贪心多考虑了“已经付出多少”比 UCS 多考虑了“预计还要付出多少”。A* 算法是 A 算法的特例特指 h(n) 满足可采纳性的版本。这里的“星”代表最优性只要 h 可采纳A* 就一定能在有限时间内找到最优路径并且在同样的 h 下扩展的节点数比其他算法更少。很多人把 A 和 A* 当成两个不同的算法去记忆其实可以这样理解A 算法是一个“用 f 排序的通用图搜索框架”你往里面放入任何 h 都能跑A* 是对这个框架附加了一条严格的数学条件。如果你用的 h 高估了真实代价算法仍然能跑但它失去最优性保证此时你写的其实是“A 算法”而不是 A*。面试里考 A* 时最常追问的也是“你的 h 满足可采纳性吗为什么”一个标准 A* 实现import heapq def astar(start, goalGOAL): goal_pos {ch: idx for idx, ch in enumerate(goal)} def h(state): dist 0 for i, ch in enumerate(state): if ch 0: continue gi goal_pos[ch] dist abs(divmod(i, 3)[0] - divmod(gi, 3)[0]) \ abs(divmod(i, 3)[1] - divmod(gi, 3)[1]) return dist open_set [(h(start), 0, start, [start])] best_g {start: 0} while open_set: f, g, state, path heapq.heappop(open_set) if state goal: return path if best_g.get(state, float(inf)) g: continue for nxt in get_successors(state): ng g 1 nf ng h(nxt) if ng best_g.get(nxt, float(inf)): best_g[nxt] ng heapq.heappush(open_set, (nf, ng, nxt, path [nxt])) return None这段代码里有个容易忽略的细节open_set 里存的是(f, g, state, path)优先级按 f 排如果两个节点 f 相同再按 g 排。best_g是每个状态当前已知的最短 g 值当从堆里弹出的 g 比 best_g 记录的大说明这个状态已经有更优路径直接跳过相当于一个闭集剪枝。path [nxt]在这里依然有复制开销如果路径很长建议改成父指针回溯能省大量内存开销。这个版本的可采纳性成立前提是每步步长统一为 1代码里ng g 1写死了且曼哈顿距离不高估。如果哪天你想改成代价不同的地图要在三处同步改动get_successors 要返回 (状态, 单步代价)ng 改为g step_costh 仍然保留曼哈顿或者说改用适合新代价的预估函数否则下界性质会被打破。5. 搜索实现常见坑判重、无解、内存与最优性5.1 现象BFS 跑了几分钟没出结果原因大概率是没判重或者判重时机不对。我在初学 BFS 时就踩过一次觉得八数码才 36 万状态不判重也能跑完结果分支因子约 2~4路径一长状态重复扩展数量指数上升队列里塞了几百万个冗余节点直接把内存打满。解决方法是把visited放在入队那一刻就标记而不是出队时再标记。入队时标记能保证同一个状态不会多次入队出队时标记会让队里堆大量重复状态。如果你用 UCS 或 A*情况略有不同它们需要允许某个状态以不同 g 值多次入队但依然要维护 best_g 做剪枝。5.2 现象A* 跑的比 BFS 还慢原因基本只有一个h 太弱或者 h 的计算开销太大。错位数字数作为 h 的确可采纳但它对八数码的区分度太差大量状态的 f 值相同A* 退化接近 BFS。换成曼哈顿距离后扩展节点数通常会降一个量级。另一个隐蔽原因是 h 每次重复计算目标位置索引没有预存字典导致单次计算从 O(1) 变成 O(9)在大规模问题上会造成可观的常数损失。我一般会做一次对比实验同一个初始局面分别用错位数和曼哈顿距离跑记录扩展节点数和耗时。扩展数少但耗时反而高就要检查是不是 h 本身算得太重。这时候可以在 h 上做文章比如曼哈顿距离配合一个小的查表缓存lru_cache在重复状态被重新评估时能直接命中缓存效果立竿见影。5.3 现象搜出来的路径明显绕路这几乎必然是启发式函数高估了真实代价。典型例子是把某个数字的行列距离乘了一个大于 1 的系数或者用了“线性冲突”等更强但需要额外验证的启发式却没有检查它是否始终满足 h(n) ≤ 真实代价。一旦 h 高估那个本应最优的节点会被排到堆后面算法先扩展了看似 f 小实则实际代价更大的分支最终返回一条次优路径。解决方法是先验证 h 的可采纳性。最可靠的办法是小棋盘上直接用 BFS 求出真实最短步数然后对大量随机状态检查 h ≤ 真实值是否恒成立。不要相信经验上的“它应该不会高估”数学性质的验证必须落在数据上。5.4 现象程序报错或者永远搜不到但代码看起来没错先查无解。八数码不是所有排列都能还原成目标排列逆序数奇偶不一致就无解。这个问题藏得很深因为搜索代码本身完全正常只是它在一个没有解的图里遍历最终耗尽所有状态然后退出返回 None。你可以在入口处加一道is_solvable检查直接拒绝无解输入既省内存也避免误会。换个视角看这也解释了为什么跑路前一定要先算算状态空间有没有“出口”。盲目搜索和启发式搜索都是在“图”里找路但如果图里压根没有目标节点再好的 A* 也无能为力。5.5 现象A* 反复扩展同一个节点性能急剧下降这通常是因为 best_g 的更新逻辑出了问题。比如你只在弹出节点时才更新 best_g而 push 时不检查新路径的 g 是否更小导致同一个状态以多个 g 值反复入队。或者反过来在 push 时发现 g 更大就直接丢弃但没考虑到后期可能出现更优路径。规范做法是每次生成后继时都比较ng best_g.get(nxt, inf)只有更优才压入堆。这是 A* 实现里最容易写出“伪 A*”的位置。对比一下 UCS 和 A* 的判重策略UCS 的 visited 只管“弹出过”A* 的 best_g 管的是“当前已知最优 g”。A* 允许同一状态多次入队但每次入队都必须携带更小的 g否则丢弃。你如果彻底禁止同一状态重复入队就可能丢掉更优路径违反一致性条件的有效利用方式。6. 验证 A* 最优性的三个实操方法以及一个值得长期保留的习惯想确认自己写的 A* 真的最优最直接的办法是把小规模问题的实测解与真实最短距离对比。拿八数码来说BFS 可以暴力求出任意可解局面的最短步数虽然只适用于几万状态的小图但作为基准足够了。于是可以写一段验证脚本随机生成 100 个可解初始局面对每个局面用 BFS 求最短步数 d_true再用 A* 求路径长度 d_astar断言两者相等。这一步能同时暴露 h 高估和 best_g 更新错误两类问题。第二个方法对所有启发式都通用随机采样大量状态计算 h 值和真实距离统计有多少比例的情况 h ≤ 真实值一旦出现反例就说明启发式在当前问题域上不可采纳必须停用或者修正。我把这个习惯叫“启发式函数的体检”做完才敢在正式项目里放心使用。第三个方法比较实用做一个“错位数 vs 曼哈顿距离”的扩展节点数对比表。随便跑同一个深度为 20 左右的局面你会发现扩展节点数可能相差一倍以上。这个对比是面试和项目汇报里都能拿得出手的数据资料也是你在设计更强启发式比如线性冲突时衡量收益的工具。最后说一个我自己的长期习惯所有搜索类代码先在小规模问题验证正确性再放大规模先保证最优性再谈速度先做无解检查再进主循环。搜索技术的水挺深但骨架永远是“状态空间 搜索策略 启发式”只要每一步都留下验证代码翻车的概率就会小很多。希望帮到你。本文还有配套的精品资源点击获取