简介这份PDF资料面向人工智能初学者与算法进阶学习者系统梳理搜索技术这一AI问题求解的核心分支。内容从搜索技术概述切入说明问题求解可抽象为状态空间中的搜索过程并依次讲解状态空间表示、盲目搜索、启发式搜索、A算法与A*算法延伸至博弈搜索与α-β剪枝法。资源以农夫过河、八数码难题等经典实例展开配合状态向量、算符、估价函数f(n)g(n)h(n)等概念帮助读者理解宽度优先、深度优先及启发式策略的差异与适用场景。压缩包内为1个PDF文件约6.54MB结构完整、图文并茂适合作为课程笔记或复习提纲。目前已有500人学习下载可用于掌握搜索算法的建模思路、评估函数设计与剪枝优化方法为后续路径规划、博弈决策等方向打下基础。1. 人工智能搜索技术从状态空间到 A*一条能跑通的落地路径很多人第一次接触「人工智能搜索技术」是在课程表上看到「搜索技术概述、状态空间、盲目搜索、启发式搜索、A算法和A算法」这一串名词感觉像是一门纯理论课。但真正做过路径规划、拼图求解、任务调度的人会告诉你这套东西是 AI 里少数「学完当天就能写出可运行代码」的知识模块。它的核心问题只有一个——在一个巨大的可能性空间里怎么用最少的计算找到一条从初始状态到目标状态的路径。状态空间负责把问题形式化盲目搜索负责给出保底解法启发式搜索和 A负责把效率拉起来。这篇文章面向想把这套技术真正用起来的开发者从概念到代码到调参一步步走完。2. 状态空间把现实问题翻译成搜索器能吃的格式2.1 状态、动作、转移三个必须定义清楚的东西搜索算法的输入不是「一个问题」而是一个五元组状态集合、初始状态、目标条件、动作集合、转移代价。很多新手写搜索代码翻车不是算法写错了而是状态定义没想清楚。以经典的八数码8-puzzle为例。状态就是 3×3 棋盘上数字的排列初始状态是给定的乱序目标条件是所有数字归位动作是空格向上下左右移动代价每一步为 1。这四个要素一旦确定搜索空间就确定了。我一般会先用一个简单的数据结构把状态表示出来再写状态转移函数。状态表示的选择直接影响后续的性能——用元组比用列表好因为元组可哈希能直接放进集合做去重。# 八数码状态表示与转移 # 状态用长度为9的元组表示0代表空格 from typing import List, Tuple GOAL (1, 2, 3, 4, 5, 6, 7, 8, 0) def get_neighbors(state: Tuple[int, ...]) - List[Tuple[int, ...]]: 返回当前状态所有合法后继状态 neighbors [] idx state.index(0) # 空格位置 row, col divmod(idx, 3) # 转成行列坐标 # 四个方向上、下、左、右 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: nidx nr * 3 nc new_state list(state) new_state[idx], new_state[nidx] new_state[nidx], new_state[idx] neighbors.append(tuple(new_state)) return neighbors这段代码里divmod把一维索引转成二维坐标四个方向偏移后检查边界合法就交换空格和目标位置。逻辑很直白但有两个参数值得注意一是状态用元组而非列表保证可哈希二是邻居生成顺序会影响搜索的扩展顺序在同等代价下会改变找到的第一条路径但不影响最优性对 BFS 和 A* 而言。2.2 状态空间爆炸为什么 8 数码能解15 数码就吃力8 数码的状态总数是 9! 362880去掉不可达的一半实际约 18 万。这个规模用 BFS 还能扛。但换成 15 数码状态数是 16! ≈ 2×10¹³直接爆炸。这就是状态空间搜索的核心矛盾问题规模稍微涨一点搜索空间就指数级膨胀。理解这一点才能理解为什么需要启发式搜索。盲目搜索不管目标在哪均匀地向外扩展启发式搜索用评估函数引导方向把计算集中在「有希望」的分支上。两者的差距不是常数级的是数量级的。在实际工程里定义状态空间时要有意识地控制维度。能合并的状态就合并能剪枝的分支就剪枝。我见过一个任务调度项目初始状态定义里把「已完成任务列表」和「待执行任务队列」都编码进去状态数直接多了两个数量级后来把已完成列表去掉因为不影响后续决策搜索速度立刻上来了。2.3 用代码验证状态空间的可达性在写搜索之前先确认目标状态是否可达能省掉大量无效计算。八数码有一个经典的逆序数判据把状态展成一维去掉空格计算逆序数逆序数奇偶性相同则可达。def is_solvable(state: Tuple[int, ...]) - bool: 通过逆序数奇偶性判断八数码是否可解 flat [x for x in state if x ! 0] inversions 0 for i in range(len(flat)): for j in range(i 1, len(flat)): if flat[i] flat[j]: inversions 1 return inversions % 2 0 # 测试 print(is_solvable((1, 2, 3, 4, 5, 6, 7, 8, 0))) # True目标状态 print(is_solvable((1, 2, 3, 4, 5, 6, 8, 7, 0))) # False不可达这个判据只适用于八数码这类特定问题但它体现了一个通用思路在进入搜索之前先用领域知识做可行性判断。参数上没什么可调的但要注意flat列表里必须去掉 0否则逆序数计算会出错。这个坑我在早期实现里踩过调试了半天才发现是空格参与了比较。3. 盲目搜索BFS、DFS 和一致代价搜索的选型与实现3.1 BFS 为什么能保证最短路径代价是什么广度优先搜索BFS按层扩展先访问所有距离为 1 的节点再访问距离为 2 的以此类推。只要每步代价相同BFS 第一次到达目标时走过的路径就是最短的。这个性质来自它的扩展顺序所有更短的路径都已经先被探索过了。但 BFS 的代价是空间。它需要把当前层的所有节点都放在队列里空间复杂度是 O(b^d)b 是分支因子d 是深度。八数码的分支因子大约 2-4深度可能到 20 多队列里同时存几万个状态是常事。from collections import deque def bfs(start: Tuple[int, ...]): 广度优先搜索返回路径和扩展节点数 if start GOAL: return [], 0 frontier deque([(start, [])]) # (状态, 路径) explored {start} # 已访问集合 nodes_expanded 0 while frontier: state, path frontier.popleft() nodes_expanded 1 for neighbor in get_neighbors(state): if neighbor GOAL: return path [neighbor], nodes_expanded if neighbor not in explored: explored.add(neighbor) frontier.append((neighbor, path [neighbor])) return None, nodes_expanded这里用deque而不是 list 做队列因为popleft是 O(1)list 的pop(0)是 O(n)。explored集合用来去重防止同一个状态被反复扩展。注意路径是随状态一起存的这样找到目标时直接返回完整路径不用回溯。代价是内存占用更高每个节点都带一个路径列表。如果只关心路径长度不关心具体路径可以省掉路径存储用父节点指针回溯。3.2 DFS 的内存优势与不保证最优的代价深度优先搜索DFS沿着一条路走到底走不通再回溯。它的空间复杂度是 O(bd)比 BFS 小得多但找到的路径不一定最短甚至可能在无限深的分支里迷路。在状态空间有限且解密集的问题里DFS 配合深度限制IDDFS可以兼顾内存和最优性。迭代加深搜索IDDFS就是反复用递增的深度限制跑 DFS第一次找到解时保证是最优的。它的时间复杂度和 BFS 同阶但空间只有 O(bd)。def iddfs(start: Tuple[int, ...], max_depth: int 30): 迭代加深搜索 for depth in range(max_depth): result, expanded dls(start, depth, {start}) if result is not None: return result, expanded return None, -1 def dls(state, depth, path_set): 深度受限搜索 if state GOAL: return [state], 0 if depth 0: return None, 0 expanded 0 for neighbor in get_neighbors(state): if neighbor not in path_set: path_set.add(neighbor) result, sub_expanded dls(neighbor, depth - 1, path_set) expanded sub_expanded 1 if result is not None: return [state] result, expanded path_set.remove(neighbor) return None, expandedpath_set用来防止环这是 DFS 类算法必须做的。max_depth要根据问题规模设太小找不到解太大浪费时间。八数码一般 30 以内足够。3.3 一致代价搜索当每步代价不一样时怎么办BFS 假设每步代价相同。如果不同动作代价不同就要用一致代价搜索UCS它每次扩展当前累计代价最小的节点用优先队列实现。import heapq def ucs(start: Tuple[int, ...]): 一致代价搜索适用于每步代价不同的场景 frontier [(0, start, [])] # (累计代价, 状态, 路径) explored {} # 状态 - 最小代价 nodes_expanded 0 while frontier: cost, state, path heapq.heappop(frontier) if state GOAL: return path [state], nodes_expanded if state in explored and explored[state] cost: continue explored[state] cost nodes_expanded 1 for neighbor in get_neighbors(state): new_cost cost 1 # 这里假设每步代价为1可替换为实际代价 if neighbor not in explored or new_cost explored.get(neighbor, float(inf)): heapq.heappush(frontier, (new_cost, neighbor, path [neighbor])) return None, nodes_expanded关键在explored字典存的是「到达该状态的最小代价」而不是简单的已访问标记。如果后来发现了更便宜的路径允许重新入队。这个细节很多实现会漏掉导致结果不是最优。4. 启发式搜索让搜索有方向感4.1 启发函数怎么设计可采纳性与一致性启发式搜索的核心是评估函数 f(n) g(n) h(n)g(n) 是从起点到 n 的实际代价h(n) 是从 n 到目标的估计代价。h(n) 的设计决定了搜索的效率和解的最优性。两个关键性质可采纳性admissible要求 h(n) 永远不高估真实代价这保证 A* 找到最优解一致性consistent要求 h(n) ≤ cost(n, n) h(n)这保证每个节点只被扩展一次。八数码常用的两个启发函数一是错位棋子数不在目标位置的数字个数二是曼哈顿距离每个数字到目标位置的曼哈顿距离之和。两者都可采纳曼哈顿距离更紧搜索效率更高。def h_misplaced(state: Tuple[int, ...]) - int: 错位棋子数启发函数 return sum(1 for i in range(9) if state[i] ! GOAL[i] and state[i] ! 0) def h_manhattan(state: Tuple[int, ...]) - int: 曼哈顿距离启发函数 distance 0 for i, val in enumerate(state): if val 0: continue goal_idx GOAL.index(val) row, col divmod(i, 3) goal_row, goal_col divmod(goal_idx, 3) distance abs(row - goal_row) abs(col - goal_col) return distance曼哈顿距离的计算里GOAL.index(val)每次都要查一遍如果状态扩展量大可以预先建一个「数字 - 目标位置」的映射表把 O(9) 的查找降到 O(1)。这个优化在 15 数码这种大规模搜索里很关键。4.2 加权启发函数用最优性换速度如果不需要严格最优解可以把 h(n) 乘以一个大于 1 的权重 w变成 f(n) g(n) w·h(n)。w 越大搜索越贪心速度越快但解的质量可能下降。这就是加权 A*Weighted A*。在实际工程里很多场景允许「次优但快」的解。比如游戏寻路玩家感知不到多走一格但帧率不能掉。这时候把 w 设成 1.5 到 3 之间往往能拿到几倍的速度提升。def weighted_a_star(start, weight2.0): 加权 A*weight 1 时偏向快速找到解 frontier [(weight * h_manhattan(start), 0, start, [])] explored {} nodes_expanded 0 while frontier: f, g, state, path heapq.heappop(frontier) if state GOAL: return path [state], nodes_expanded if state in explored and explored[state] g: continue explored[state] g nodes_expanded 1 for neighbor in get_neighbors(state): new_g g 1 new_f new_g weight * h_manhattan(neighbor) if neighbor not in explored or new_g explored.get(neighbor, float(inf)): heapq.heappush(frontier, (new_f, new_g, neighbor, path [neighbor])) return None, nodes_expanded注意优先队列里存的是(f, g, state, path)Python 的 heapq 在 f 相同时会比较 g再比较 state。如果 state 是不可比较的类型会报错。元组在这里是可比较的所以没问题。但如果状态表示换成字典或自定义对象就要加一个计数器来打破平局。5. A 算法和 A* 算法从理论到能跑的代码5.1 A 算法与 A* 的区别一张表说清楚很多人把 A 算法和 A* 混着叫其实有区别。A 算法是一个框架只要用 f(n) g(n) h(n) 做评估就属于 A 算法族。A* 是 A 算法的一个特例要求 h(n) 可采纳不高估。如果 h(n) 不可采纳就叫 A 算法但不叫 A*此时不保证最优。特性A 算法A* 算法评估函数f g hf g hh(n) 要求无限制必须可采纳最优性不保证保证树搜索可采纳图搜索一致典型用途快速近似解需要最优解的场景效率取决于 h 质量h 越紧效率越高实际写代码时只要 h 是可采纳的就是 A*。我一般先用曼哈顿距离实现 A*跑通之后再根据需求决定要不要换成加权版本。5.2 完整 A* 实现优先队列、去重与路径回溯import heapq def a_star(start: Tuple[int, ...]): 标准 A* 算法使用曼哈顿距离作为启发函数 # 优先队列元素(f值, g值, 状态, 路径) frontier [(h_manhattan(start), 0, start, [start])] # explored 记录到达每个状态的最小 g 值 explored {} nodes_expanded 0 while frontier: f, g, state, path heapq.heappop(frontier) # 到达目标返回路径和扩展节点数 if state GOAL: return path, nodes_expanded # 如果已经用更小或相等的代价到达过该状态跳过 if state in explored and explored[state] g: continue explored[state] g nodes_expanded 1 # 扩展邻居 for neighbor in get_neighbors(state): new_g g 1 new_f new_g h_manhattan(neighbor) # 只有当新路径更优时才入队 if neighbor not in explored or new_g explored[neighbor]: heapq.heappush(frontier, (new_f, new_g, neighbor, path [neighbor])) return None, nodes_expanded这段代码有几个关键点。第一explored存的是最小 g 值而不是布尔标记这样后来发现更优路径时还能更新。第二入队前检查new_g explored[neighbor]避免把劣质路径塞进队列。第三路径随节点一起传递找到目标时直接返回不用回溯父节点。代价是内存占用高如果状态空间很大可以改成存父节点指针找到目标后再回溯。5.3 性能对比BFS、UCS、A* 在八数码上的实测用一个随机但可解的八数码状态做测试对比三种算法的扩展节点数。import random def random_solvable_state(): 生成一个随机可解的八数码状态 while True: state list(range(9)) random.shuffle(state) state tuple(state) if is_solvable(state) and state ! GOAL: return state test_state random_solvable_state() print(测试状态:, test_state) path_bfs, exp_bfs bfs(test_state) print(fBFS: 路径长度{len(path_bfs)-1}, 扩展节点{exp_bfs}) path_ucs, exp_ucs ucs(test_state) print(fUCS: 路径长度{len(path_ucs)-1}, 扩展节点{exp_ucs}) path_astar, exp_astar a_star(test_state) print(fA*: 路径长度{len(path_astar)-1}, 扩展节点{exp_astar})典型结果BFS 和 UCS 扩展几万到十几万节点A* 通常只扩展几百到几千。差距在 10 到 100 倍之间。这个差距随着问题规模增大会进一步拉大。在 15 数码上BFS 基本跑不动A* 配合曼哈顿距离还能在可接受时间内出解。6. 避坑与排查搜索算法落地时最容易翻车的 5 个点6.1 现象A* 找到的路径不是最短的原因通常是启发函数不可采纳高估了真实代价。比如在八数码里用「曼哈顿距离 × 2」做启发虽然搜索快了但可能错过最优解。解决方法是检查 h(n) 是否满足可采纳性或者改用加权 A* 并接受次优解。6.2 现象搜索跑着跑着内存爆了原因是 explored 集合和 frontier 队列同时存了大量状态。BFS 在深层次问题上尤其明显。解决办法一是换用 IDDFS 降低空间复杂度二是用更紧的启发函数减少扩展节点三是如果只关心解的存在性可以用布隆过滤器替代精确去重代价是可能重复扩展少量节点。6.3 现象同一个状态被反复扩展节点数远超预期原因是去重逻辑写错了。常见错误是只在入队时去重没有在出队时再检查一次。由于优先队列里可能存在同一状态的多个副本不同 g 值出队时必须检查当前 g 是否优于已记录的 g否则跳过。上面的 A* 代码里if state in explored and explored[state] g: continue就是做这件事。6.4 现象优先队列报 TypeError说状态不可比较原因是 heapq 在 f 值相同时会比较第二个元素如果第二个元素是字典或自定义对象就会报错。解决办法是在元组里加一个自增计数器作为 tie-breaker或者确保状态本身可比较。我一般用(f, g, counter, state, path)这种结构counter 用itertools.count()生成。6.5 现象启发函数计算太慢拖累整体速度原因是 h(n) 在每次扩展时都要算一遍如果 h 本身复杂度高会成为瓶颈。解决办法是缓存 h 值用字典存「状态 - h 值」避免重复计算。另一个办法是预计算部分信息比如八数码里预先建好「数字 - 目标坐标」的映射把每次 h 计算里的查找从 O(9) 降到 O(1)。7. 进阶技巧用模式数据库把 15 数码的 A* 提速一个量级标准曼哈顿距离在 15 数码上还是太弱扩展节点数经常到几百万。一个实用的进阶技巧是模式数据库Pattern Database。思路是把部分棋子拿出来单独建一个数据库预计算这些棋子从任意位置到目标位置的最短距离作为启发值。多个不相交的模式数据库取最大值就得到一个更紧的可采纳启发函数。以 15 数码为例可以选 5 个棋子加空格组成一个模式预计算所有排列的最短距离。这个数据库只算一次之后每次查询是 O(1)。多个模式数据库组合后启发值比曼哈顿距离紧得多A* 的扩展节点数能降一个数量级。# 模式数据库构建思路伪代码级实际需要 BFS 预计算 # 1. 选定模式棋子集合比如 {1, 2, 3, 4, 0} # 2. 从目标状态出发做 BFS只移动模式内的棋子 # 3. 记录每个可达模式状态到目标的最短距离存入字典 # 4. 搜索时从完整状态中提取模式状态查表得到 h 值 # 5. 多个模式数据库取 max 作为最终 h 值 def build_pattern_db(pattern_tiles): 构建模式数据库返回 {模式状态: 最短距离} # 目标状态中提取模式 goal_pattern tuple(x if x in pattern_tiles else -1 for x in GOAL) db {goal_pattern: 0} frontier deque([goal_pattern]) while frontier: state frontier.popleft() for neighbor in get_pattern_neighbors(state, pattern_tiles): if neighbor not in db: db[neighbor] db[state] 1 frontier.append(neighbor) return db实际实现里get_pattern_neighbors只考虑模式内棋子的移动空格也在模式内。多个模式数据库的构建可以并行查询时取最大值。这个技巧在 15 数码和 24 数码上是标配能把 A* 从「跑不动」变成「秒出」。我自己的习惯是先用曼哈顿距离跑通 A*确认逻辑正确再根据问题规模决定要不要上模式数据库。不要一上来就搞复杂先把基础版本调对再逐步优化。搜索算法这东西玄学的地方不多大部分翻车都是状态定义、去重逻辑、启发函数可采纳性这三个地方出了问题。把这三个点盯住剩下的就是调参和优化了。希望帮到你。本文还有配套的精品资源点击获取