简介：一套系统讲解人工智能搜索技术的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, goal=GOAL): 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, goal=GOAL, max_depth=40): 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, goal=GOAL): 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在这里只记录已经弹出过的节点，而不是入队时就去重，因为第一次入队的路径不一定是最小代价路径，直接去重会截断更优解。如果每条边代价都是 1，UCS 和 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, goal=GOAL): 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, goal=GOAL): 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_cost，h 仍然保留曼哈顿或者说改用适合新代价的预估函数，否则下界性质会被打破。
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 左右的局面，你会发现扩展节点数可能相差一倍以上。这个对比是面试和项目汇报里都能拿得出手的数据资料，也是你在设计更强启发式（比如线性冲突）时衡量收益的工具。
最后说一个我自己的长期习惯：所有搜索类代码，先在小规模问题验证正确性，再放大规模；先保证最优性，再谈速度；先做无解检查，再进主循环。搜索技术的水挺深，但骨架永远是“状态空间 + 搜索策略 + 启发式”，只要每一步都留下验证代码，翻车的概率就会小很多。希望帮到你。
本文还有配套的精品资源，点击获取
