简介PDF 文档系统梳理了人工智能搜索技术的完整知识体系涵盖搜索技术概述、状态空间表示、盲目搜索、启发式搜索、A 算法与 A* 算法以及博弈搜索中的 α-β 剪枝法适合 AI 入门学习者、算法爱好者及备考人工智能课程的本科生作为复习参考。内容从 Nilsson 归纳的 AI 四个基本问题引入将问题求解抽象为状态空间中的搜索过程并结合八数码、农夫过河等经典案例讲解状态向量建模、操作与状态转移随后对比盲目搜索与启发式搜索的适用场景深入分析 A* 算法的估价函数 f(n)g(n)h(n)并介绍博弈搜索中的 α-β 剪枝如何压缩搜索空间。整份资源打包为单个 PDF 文件大小约 6.54MB便于随时查阅。目前已有 498 人学习下载章节划分清晰、概念推导完整对状态空间建模、A* 算法实现依据及剪枝条件等难点讲解细致可直接用于课程作业参考或自学提升。1. 搜索技术概述从“枚举”到“会选路”的转变提到人工智能搜索技术很多人第一反应是百度或Google那种搜索引擎。但在AI领域里“搜索”是两个完全不同的概念它不是在海量网页里找关键词而是在一个状态空间里找一条从初始状态到目标状态的路径。无论是迷宫寻路、八数码问题、机器人路径规划还是游戏中AI的决策底层用的都是这套搜索算法。你只要理解了“状态”、“动作”、“转移”这三个词就抓住了这个标题的骨架。这门技术最反直觉的地方在于搜索的难点从来不是“能不能找到”而是“能不能高效找到”。盲目搜索BFS/DFS在小规模问题上能用状态一多就直接爆炸启发式搜索A*看起来只是多算了一个估价函数却能指数级减少扩展节点。这篇笔记会把状态空间建模、盲目搜索的适用边界、启发式设计的门道以及A*算法的最优性条件和实际调参经验逐一讲透。适合正要交人工智能大作业、准备面试或者要用搜索算法做路径规划的从业者读完可以直接照着复现并改造自己的问题。2. 状态空间建模把现实问题翻译成图才算真正开始2.1 状态、动作与转移一切搜索问题的共同骨架任何搜索问题本质上都可以抽象成三个要素。第一个是状态State描述某一时刻系统的完整情况第二个是动作Action指从当前状态能够执行的操作第三个是转移模型Transition Model说明执行动作后会到达哪个新状态。这三者合起来就构成了状态空间图。以八数码问题为例当前棋盘上9个格子的数字排列就是状态上下左右移动空白格就是动作移动后的新排列就是转移结果。状态空间图的节点是状态边是动作。搜索的全部任务就是在这张隐式定义的图中从起点走到目标。这里有一句我常对学生讲的“黑话”图是隐式的不要真的把整张图建出来。游戏地图可能有几亿个状态显式建图内存直接爆掉搜索时动态生成后继状态才是通用做法。class State: def __init__(self, board, empty_pos, path_cost0): self.board board # 例如 (2,8,3,1,6,4,7,0,5) 这样的元组 self.empty_pos empty_pos # 空白格下标0~8 self.path_cost path_cost # 从初始状态到当前状态的实际代价g(n) def is_goal(self, goal_board): return self.board goal_board这段代码中board用元组而非列表是为了让状态可以被set()判重后面写图搜索时能直接if next_state in closed_set。path_cost记录从起点走来的真实代价盲目搜索里每个动作代价相同可以不加但到了A*就必须维护它。状态建模的核心原则就一句话状态必须包含做决策所需的全部信息一个都不能少多了反而浪费空间。2.2 从八数码到迷宫两个经典建模的对照八数码的状态是排列迷宫的状态是坐标。迷宫由于状态是二维坐标转移就是移动一格建模更简单但暴露的问题也更明显——状态是否可重复访问。如果允许原路返回搜索就会陷入无限循环如果不允许又可能丢失最优路径因为到达同一坐标的方式不同代价可能不同。我一般会建议先判断问题是否满足“到达同一状态的路径代价相同”。迷宫每一步代价为1先到达某坐标的路径必然代价更小所以可以放心砍掉后续到达的同坐标状态——这就是图搜索中的closed表思想。八数码也同理给定起点到达同一排列的操作序列长度若相同则保留第一次到达若没有这个性质就必须用代价更低的路径替换旧路径这才是A*中使用g(n)比较的真正原因。def maze_successors(state, maze): 向四个方向扩展返回 (next_state, step_cost) 列表 x, y state results [] for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: nx, ny x dx, y dy if 0 nx len(maze) and 0 ny len(maze[0]) and maze[nx][ny] ! 1: results.append(((nx, ny), 1)) return results这里迷宫用1表示墙、0表示通路越界检查放在扩展函数里而不是主循环里可以减少主循环的代码分支。step_cost1是给后续从DFS/BFS升级到加权A*留的口子——如果地图上沼泽地形代价是3这个函数只要改返回值就行。3. 盲目搜索BFS、DFS与一致代价搜索的适用边界3.1 宽度优先搜索保证最短路径但内存是硬伤盲目搜索指的是不使用任何问题领域知识只会机械地按固定策略扩展节点。**宽度优先搜索BFS**按层扩展先扩展离起点最近的节点它的核心优势是当每一步代价相同时第一次到达目标状态的路径就是最短路径。但BFS的代价也极其直观——内存消耗按层指数增长。假设迷宫是100×100格每层扩展节点大约翻倍存到第20层可能就有百万级节点在队列里。用Python的deque做队列一个状态存储几字节到几十字节几百万节点内存立刻吃紧。我给学生的建议是BFS只适合状态数在百万以内、且能找到目标在较浅层的场景。八数码用BFS可能要在内存里铺开十几层勉强能跑四阶及以上就建议放弃。from collections import deque def bfs(start, goal, successors): queue deque([start]) parent {start: None} while queue: node queue.popleft() if node goal: return reconstruct_path(parent, goal) for next_state in successors(node): if next_state not in parent: parent[next_state] node queue.append(next_state) return Noneparent字典既当visited表又记录回溯路径一举两得。popleft()是O(1)操作不要用列表的pop(0)那会让整个BFS变成O(n²)级别。BFS的最优性要求“每一步代价相同”代价不同时必须改用一致代价搜索否则最短路径完全不保证。3.2 深度优先搜索内存友好但可能一头扎进死胡同深度优先搜索DFS沿着一条路走到底再回溯内存占用只有一条路径的长度这是它相对BFS最大的优势。但它有两个致命问题不完备性在无限状态空间里可能永远找不到解和非最优性找到的第一条路径不一定最短。实际做项目时我很少直接裸用DFS找最短路径但DFS在两类场景很香一类是空间受限的判定问题只需回答“有没有解”另一类是配合深度限制的迭代加深搜索IDDFS。IDDFS的思路是用DFS跑深度限制为1、2、3……直到找到解每次只重新从头搜索虽然看起来重复劳动但因为在深度限制下分支数增长极快总开销只比BFS多常数倍内存却只占O(深度)。def iddfs(start, goal, successors, max_depth30): for depth_limit in range(max_depth 1): result dls(start, goal, successors, depth_limit) if result is not None: return result return None def dls(node, goal, successors, limit, depth0, pathNone): if node goal: return path or [node] if depth limit: return None path path or [] for next_state in successors(node): new_path path [next_state] result dls(next_state, goal, successors, limit, depth 1, new_path) if result: return result return None注意这个版本没有用visited表靠深度限制避免无限递归。实际使用时为了防环可以在dls里传入set(path)但代价是内存回归O(深度)加集合开销。采用哪种要按场景权衡树形状态空间不会重复访问同一状态比如某些拼图游戏的排列天然无环不加visited能更快图状状态空间必须加否则容易在环里反复扩展直到深度上限。3.3 代价不一致时用一致代价搜索UCS是盲目搜索的终点如果不同动作的代价不同且你没有启发式信息一致代价搜索Uniform-Cost Search是盲目搜索家族里的最优解。它用**优先队列最小堆**按path_cost从小到大扩展节点。算法上BFS只是UCS在等代价情况下的特例。UCS的实现与A几乎一样唯一差别是优先级队列排序只看g(n)不看h(n)。所以当你理解了UCS后面学A只是加一个启发式函数的事。这里有一个常见的实现坑UCS/A*在“出队时判断目标”而不是“入队时判断”。如果在生成节点时发现它是目标就立即返回第一次入队的目标节点不一定是全局最优——可能会有代价更小的路径仍然在队列里没被扩展。import heapq def ucs(start, goal, successors): open_heap [(0, start)] came_from {start: None} cost_so_far {start: 0} while open_heap: current_cost, current heapq.heappop(open_heap) if current goal: return reconstruct_path(came_from, current) for next_state, step_cost in successors(current): new_cost cost_so_far[current] step_cost if next_state not in cost_so_far or new_cost cost_so_far[next_state]: cost_so_far[next_state] new_cost heapq.heappush(open_heap, (new_cost, next_state)) came_from[next_state] current return Noneheapq是小根堆(代价, 状态)元组入堆后自动按代价排序。注意cost_so_far字典承担了closed表的职责——当新路径代价更小时覆盖旧路径。很多教程里用visited集合直接丢弃所有重复节点这在代价不一致的地图中是错的会让UCS变成不保证最优的“伪UCS”。3.4 盲目搜索的避坑清单三个最常见的翻车现象现象1BFS/DFS跑大图内存爆炸。原因队列/栈里存了太多节点。解决换IDDFS或改为双向BFS。双向BFS从起点和目标同时扩展每层只扩展到一半深度内存消耗通常可以降到单向BFS的平方根级别。在迷宫题里双向BFS是作业和比赛中最稳的做法。现象2DFS找到了一条很长很丑的路径甚至不是最短路径。原因DFS天然偏向深度第一个目标就是当前深度耗尽时遇到的第一个解。解决如果必须用DFS加上迭代加深。现象3一致代价搜索和带权BFS分不清。很多初学者把BFS直接套在加权图上结果得到的是“边数最少”而不是“代价最小”的路径。解决代价不一致时必须用UCS或A*BFS的队列顺序和代价毫无关系。4. 启发式搜索用“往目标方向的直觉”砍掉无用节点4.1 启发式函数它决定了搜索效率的上限启发式搜索的核心在于启发式函数h(n)它表示从状态n到目标状态的估计代价。h(n)的值越接近真实剩余代价搜索效率越高但永远不要高估真实代价——这是A最优性的铁律叫做“可采纳性”admissible。如果h(n)高估了A就会变成贪心算法丢掉最优解。选h(n)时要先看问题是不是“网格/欧几里得空间”。路径规划常用两个经典函数。曼哈顿距离|dx||dy|用于只能上下左右移动的地图且没有对角线移动的情况欧几里得距离sqrt(dx²dy²)是“直线飞”的估计比曼哈顿距离小更保守也更安全。八数码问题里h(n)可以取“所有错位数字到目标位置的曼哈顿距离之和”这是简单又好用的标准配置。def manhattan_heuristic(board, goal_positions): total 0 for idx, value in enumerate(board): if value 0: continue # 空格不参与计算否则会高估 gx, gy goal_positions[value] cx, cy divmod(idx, 3) total abs(cx - gx) abs(cy - gy) return total注意空格不参与计算。如果计算空格位移h(n)会偏大可能破坏可采纳性。goal_positions是预计算的{数字: (行, 列)}字典不要在每次调用h时去遍历目标状态找位置否则一次搜索几万个节点性能立刻翻车。4.2 贪心最佳优先搜索跑得快但容易“抄近路翻车”在引出A*之前需要先理解“只用启发式”会发生什么。贪心最佳优先搜索每次扩展h(n)最小的节点它只盯着目标方向走不管累计代价。优点是速度快缺点极明显完全不保证路径最优甚至可能绕进死胡同出不来。用迷宫举例如果前方有一堵墙但墙后离目标很近贪心会一直尝试穿墙方向的节点不断扩展墙附近的低h节点把大量时间耗在一个没有出口的区域。这种“只看结果不看过程”的搜索方式在复杂地图上表现很不稳定。所以它只适合对最优性没要求、只求速度快到能出结果的场景或者作为A*的“热身理解”。def greedy_best_first(start, goal, successors, heuristic): open_heap [(heuristic(start, goal), start)] came_from {start: None} while open_heap: _, current heapq.heappop(open_heap) if current goal: return reconstruct_path(came_from, current) for next_state in successors(current): if next_state not in came_from: came_from[next_state] current heapq.heappush(open_heap, (heuristic(next_state, goal), next_state)) return None这里的优先队列只存h(n)没有g(n)。注意它直接丢弃重复节点而没有比较代价——因为贪心根本不关心到达该节点的代价所以这个丢弃是对的。如果你拿这段代码改A*记得这里要换成g h并保留代价比较逻辑。4.3 启发式函数的归一化让h的尺度对齐g的尺度很多从游戏开发转过来的朋友会有个困惑为什么我的A跑出来路径很怪看似绕远问题往往出在h和g的量纲不一致。例如g是“移动1步代价为1”h却是曼哈顿距离乘以10相当于把启发式权重放大了10倍。只要h仍然不大于真实代价A理论上仍最优但扩展顺序会被严重扭曲路径看起来近似贪心而且搜索效率反而可能下降。如果在实际工程中需要追求“速度优先”常见的做法是给h加一个权重系数εepsilon变成f(n) g(n) (1ε)h(n)这叫加权A*Weighted A*。ε越大搜索越快路径越次优。工程中ε取值范围常见在1.04.0之间事实上很多机器人路径规划库默认ε1.5路径代价损失约2%~5%但搜索时间可以快几倍甚至一个数量级。5. A算法与A*算法从“贪心”到“最优”的临门一脚5.1 A算法先看懂f g h再看穿它的局限A算法A1/A2算法是启发式搜索的通用框架f(n) g(n) h(n)其中g是起点到当前点的实际代价h是当前点到目标的估计代价。f(n)表示“经过n点从起点到目标的估计总代价”。优先扩展f最小的节点这就是A算法的全部思想。那么问题来了A算法和A算法的区别到底是什么教科书上会说A是A算法的特例它要求h满足可采纳性和一致性一致性能保证每个节点只被扩展一次。但工程上你几乎见不到“非A的A算法”实现因为它缺少可采纳性约束时路径质量不可控。所以下面的讨论统一锚定A的标准实现同时也把A算法的开关式实现方式交代清楚。def a_star(start, goal, successors, heuristic): open_heap [(0 heuristic(start, goal), 0, start)] came_from {start: None} cost_so_far {start: 0} while open_heap: _, current_cost, current heapq.heappop(open_heap) if current goal: return reconstruct_path(came_from, current) for next_state, step_cost in successors(current): new_cost current_cost step_cost if next_state not in cost_so_far or new_cost cost_so_far[next_state]: cost_so_far[next_state] new_cost priority new_cost heuristic(next_state, goal) heapq.heappush(open_heap, (priority, new_cost, next_state)) came_from[next_state] current return Nonepriority new_cost heuristic(...)这一行就是A*的灵魂。堆里同时存priority和new_cost是因为如果两个节点priority相同堆会接着比较第二个元素保证扩展顺序稳定。这里的current_cost来自堆中存储的值而不是cost_so_far[current]——两者在正常情况下一致但直接读堆里的值可以避免字典查表开销。5.2 A*最优性的三个条件可采纳性、一致性、非负代价A要保证返回最优路径必须同时满足三个条件。第一h(n)可采纳admissibleh(n) h(n)h是真实剩余代价。第二h(n)一致consistenth(n) cost(n, n) h(n)即相邻节点的估计不能跳动过大。一致性蕴含可采纳性所以满足一致性时A的closed表可以安全丢弃重复节点每个状态只扩展一次。第三所有动作代价非负一旦有负权边A*就退化成不保证最优的普通启发式搜索。工程上经常踩的坑是h可采纳但状态空间的转移带有“绕路惩罚”导致h不满足一致性。典型例子是直线曼哈顿距离为2的两个节点中间隔了一座山绕山需要5步。曼哈顿距离恰好小于5可采纳性还行但一致性被打破。此时A*仍然能找到最优路径但closed表不能简单丢弃更高代价的重复节点必须允许“代价更小的新路径覆盖旧路径”这也是上面的代码用cost_so_far而不是visited的原因。5.3 参数怎么调三个直接影响搜索效率的旋钮旋钮一open表的数据结构。用heapq是最省心的方案插入和弹出都是O(log n)。但堆不能快速判断“某个状态是否已经在open表里”所以必须搭配cost_so_far字典。不要用线性列表存open表几万节点后每次找最小节点都是O(n)搜索直接卡死。旋钮二启发式函数的计算复杂度。在百万节点迷宫上h算得再准如果每次都要遍历整张表性能也白搭。工程上常见做法是预计算目标点到所有格子的距离场用一次BFS/多源BFS之后每个节点查表O(1)拿h。这在大地图上收益极高几乎所有游戏寻路插件都是这么做的。旋钮三开放列表的重复入堆。上面的实现中同一状态可能多次入堆因为代价更小的路径后到达堆里会有冗余节点。这不是bug是权重一致时必要的行为但冗余过多会拖慢速度。优化方案是用计数器记录每个状态被压入堆的次数当从堆里弹出时如果堆中记录的路径不是该状态的最优路径cost_so_far[current] current_cost直接跳过。这叫延迟删除lazy deletion。5.4 A*的避坑清单四个最常见的高频翻车记录现象1路径一定是最优的但跑得极慢节点扩展远超预期。原因h函数太弱比如全部返回0。解决换更强且可采纳的h。八数码中可以用“错位数字的数量 每个数字到目标位置的曼哈顿距离之和”比单纯曼哈顿距离更强但不破坏可采纳性。路径规划中可以用“对角线距离”max(|dx|, |dy|)替代曼哈顿距离。现象2A*跑出来的路径“穿墙”或“穿障碍物”。原因启发式函数或后继生成函数中没有正确考虑障碍物对路径代价的影响。解决检查succeccors是否把墙内节点生成了另外检查h是否用了欧几里得距离穿越障碍。地图上h可以用“预计算距离场”这张场本身就已经包含障碍信息可以避免大部分问题。现象3A*死循环或内存持续增长。原因状态空间有环而cost_so_far更新逻辑写错了允许同状态无限次入堆。解决在扩展循环开始前加一道防线# 放在从open_heap弹出节点后, 扩展后继之前 if current in closed_set and current_cost cost_so_far.get(current, 0): continue closed_set.add(current)但注意只有h满足一致性时才能用closed_set否则“第一次扩展某状态”不保证代价最小过早closed会丢掉更优路径。这也是算法题和工程题最大差异之一——算法书假设一致性成立真实地图常常不满足。现象4明明地图不大但A*花了几秒钟才出结果。原因open表频繁入堆堆元素数量膨胀每次堆操作O(log n)n被重复节点数撑大。解决加延迟删除或换更紧凑的状态表示。Python元组存储开销不小可以把二维坐标编码成整数x * width yh和g算完后再解包速度能提升30%~50%。5.5 从A*到实践一个带权重和障碍的完整路径规划脚本把前面的模块拼成一个可直接运行的迷宫路径规划器。这个版本支持加权代价、障碍检测、A*加权搜索并且加入了延迟删除优化。你可以原样拿去跑AI大作业也可以改成本文前面提到的地图格式。import heapq import math def weighted_a_star(start, goal, width, height, obstacles, epsilon1.5): start/goal: (x,y); obstacles: set of (x,y) def successors(node): x, y node for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: nx, ny x dx, y dy if 0 nx width and 0 ny height and (nx, ny) not in obstacles: # 对角线通行代价1.2, 直线1.0 cost 1.2 if dx ! 0 and dy ! 0 else 1.0 yield (nx, ny), cost def heuristic(node, goal): # 对角线距离: 允许斜着走时用; 如果地图不允许斜走, 换成曼哈顿距离 dx, dy abs(node[0] - goal[0]), abs(node[1] - goal[1]) return max(dx, dy) (math.sqrt(2) - 1) * min(dx, dy) open_heap [(0 epsilon * heuristic(start, goal), 0, start)] came_from {start: None} cost_so_far {start: 0} pushed_count {start: 1} # 每个状态入堆的次数, 用于延迟删除 while open_heap: f_priority, g_value, current heapq.heappop(open_heap) if cost_so_far[current] g_value: continue # 这是冗余节点直接丢弃 if current goal: path [] while current is not None: path.append(current) current came_from[current] return path[::-1] for next_state, step_cost in successors(current): new_cost cost_so_far[current] step_cost if next_state not in cost_so_far or new_cost cost_so_far[next_state]: cost_so_far[next_state] new_cost priority new_cost epsilon * heuristic(next_state, goal) heapq.heappush(open_heap, (priority, new_cost, next_state)) came_from[next_state] current pushed_count[next_state] pushed_count.get(next_state, 0) 1 return None # 无路径这段代码在实现上有三个值得注意的细节。一是epsilon直接乘在h上这是加权A*的标准写法它破坏了最优性但大幅提升速度工程上很实用如果你需要严格最优把epsilon1.0即可此时h可采纳就能保证最优解。二是对角通行代价设为1.2直线为1.0这是模拟真实地形中拐角路径消耗的常见做法也可以根据自己的地图改。三是pushed_count目前记录入堆次数延迟删除的判定在堆弹出时通过cost_so_far[current] g_value完成省掉了主循环里的closed_set判断且对一致性被破坏的情况更稳健。6. 进阶技巧从验证结果到性能瓶颈的定位写完A*只完成了80%的工作剩下是验证和调优。验证的核心不是“找没找到路径”而是“找到的路径是否真正最优”。我建议在实验里加一条对照逻辑把epsilon改成1.0跑一遍记录路径总代价再把epsilon设为1.5、2.0、3.0分别跑对比“路径代价增长百分比”和“搜索时间缩短倍数”。如果epsilon3.0时代价增长超过10%说明你的启发式函数太弱或者地图的凹形障碍太多加权带来的代价损失被放大了。性能定位上最有效的手段是插桩统计扩展节点数和open表峰值长度。扩展节点数少但运行慢瓶颈在h的计算成本扩展节点数多但单次扩展快瓶颈在h的估计精度不够。这两个方向的优化手法完全不同前者要预计算距离场或缓存h结果后者要换更强的可采纳启发式。我遇到过的最极端情况是一个2D网格地图换了一个更强的启发式后扩展节点数从80万降到了6万速度提升了十几倍——启发式质量远比代码微优化重要。还有一个容易被忽略的坑Python递归深度。如果reconstruct_path用递归写路径长度超过1000就会RecursionError。上面的代码已经用了迭代版本但如果你的作业代码是递归回溯记得改用循环或用sys.setrecursionlimit兜底。另外如果你的实验要对比BFS/DFS/A*三种算法的性能要统一用同一个状态扩展函数并统计“扩展节点数”和“运行时间”两个指标否则对比的变量就失控了。最后记录自己的一个习惯每写完一个搜索算法我会先拿一个手算可达的最小用例验证正确性再换随机地图验证鲁棒性最后再回去调权重和启发式。这个顺序能过滤掉八成以上的“换数据就翻车”问题。希望帮到你。本文还有配套的精品资源点击获取