简介这份PDF资料系统梳理了人工智能搜索技术的核心知识体系面向AI入门学习者、算法课程复习者以及需要理解问题求解思路的开发者。内容从搜索技术概述切入依次讲解状态空间表示、盲目搜索、启发式搜索、A算法与A*算法并延伸至博弈搜索与α-β剪枝法覆盖了从基础概念到经典优化策略的完整脉络。资源包内含1个PDF文件大小约6.54MB以图文讲义形式呈现便于按章节顺序阅读与笔记整理。目前已有500人学习下载。读者可借助其中的状态图建模方法、农夫过河与八数码等实例理解如何将实际问题抽象为状态空间搜索并掌握估价函数f(n)g(n)h(n)的设计思路及α-β剪枝的效率优化原理适合作为课堂补充或考前梳理的参考材料。1. 人工智能搜索技术从状态空间到 A*一条能被工程复现的路径很多人第一次接触「人工智能搜索技术」是在一门课的目录里看到「状态空间、盲目搜索、启发式搜索、A算法和A算法」这几个词然后就没有然后了。真正做工程时你会发现这套东西不是考试知识点而是路径规划、任务调度、拼图求解、游戏寻路、资源分配里反复出现的一套通用骨架。它的核心问题只有一个给定一个初始状态和一个目标状态怎么在巨大的可能性里找到一条代价可接受的路径。搜索技术概述解决的是「问题怎么形式化」状态空间解决的是「解在哪里」盲目搜索解决的是「没有先验信息时怎么走」启发式搜索和 A解决的是「有先验信息时怎么走得更聪明」。这篇文章面向想把这套技术真正跑起来的人从建模到代码从参数到踩坑一层层拆开。2. 状态空间把现实问题翻译成可搜索的图2.1 状态、动作、转移、代价四个必须定义清楚的东西搜索技术概述里最容易被跳过的一步是问题形式化。很多人拿到一个场景就直接想写 BFS结果写到一半发现状态定义错了队列爆炸。状态空间建模的本质是把现实问题抽象成四元组状态State、动作Action、转移模型Transition Model、路径代价Path Cost。状态是某一时刻问题的完整描述动作是从一个状态能做的操作转移模型描述执行动作后到达哪个新状态路径代价是每一步的消耗。以经典的八数码问题为例状态就是 3×3 棋盘上数字的排列动作是空格上下左右移动转移模型是交换空格与相邻数字路径代价通常每一步为 1。这四个要素定义清楚之后搜索算法才有输入。工程上最常见的翻车是状态里漏了关键信息导致两个本质不同的局面被当成同一个状态搜索出来的解不可用。# 八数码状态表示用元组存储保证可哈希 # 0 表示空格 initial_state (1, 2, 3, 4, 0, 6, 7, 5, 8) goal_state (1, 2, 3, 4, 5, 6, 7, 8, 0) # 动作定义空格可以移动的方向 # 这里用索引位置来描述而不是行列减少转换开销 def get_neighbors(state): neighbors [] zero_idx state.index(0) row, col divmod(zero_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: new_idx nr * 3 nc new_state list(state) new_state[zero_idx], new_state[new_idx] new_state[new_idx], new_state[zero_idx] neighbors.append(tuple(new_state)) return neighbors这段代码里状态用元组而不是列表是因为元组可哈希能直接放进 set 做去重。get_neighbors通过空格索引反推行列再枚举四个方向边界检查用0 nr 3完成。参数上棋盘大小 3 是硬编码的如果要做 N 数码需要把 3 换成变量同时divmod的除数也要跟着改。动作顺序会影响搜索展开顺序但不影响完备性。2.2 状态空间大小估算为什么你的队列会炸建模完成后下一步是估算状态空间规模。八数码的状态总数是 9! 362880看起来不大但很多实际问题的状态空间是指数级的。比如 15 数码是 16! ≈ 2×10^13直接盲目搜索根本跑不完。估算方法很简单每个状态的分支因子 b 的深度 d 次方就是大致规模。分支因子是平均每个状态能扩展出多少新状态深度是解的平均步数。工程上如果估算出来超过 10^7 级别就必须考虑启发式搜索或者剪枝否则内存和时间都扛不住。我一般会先写一个随机游走脚本统计从初始状态出发走 1000 步能碰到多少不重复状态用这个来校准分支因子的真实值。这个数字比理论值更靠谱因为很多动作在实际问题里是无效的。提示状态空间估算不是学术练习它直接决定你选 BFS、DFS 还是 A*。估算超过内存容量时盲目搜索就是死路。2.3 用集合去重状态空间搜索的第一道防线无论用什么搜索算法去重都是必须的。没有去重的搜索会在环里无限打转。常见做法是维护一个visited集合扩展新状态前先检查是否已经访问过。对于状态可哈希的问题Python 的 set 就够用对于状态不可哈希的需要自己写哈希函数或者用序列化后的字符串做键。def search_with_visited(initial_state, goal_state): from collections import deque queue deque([initial_state]) visited {initial_state} parent {initial_state: None} # 记录路径 while queue: state queue.popleft() if state goal_state: # 回溯路径 path [] while state is not None: path.append(state) state parent[state] return path[::-1] for nxt in get_neighbors(state): if nxt not in visited: visited.add(nxt) parent[nxt] state queue.append(nxt) return None这里visited在入队时就加入而不是出队时避免同一个状态被多次入队。parent字典用来记录每个状态的前驱找到目标后可以回溯出完整路径。参数上deque的popleft是 O(1)如果用 list 的pop(0)是 O(n)队列一大性能差距非常明显。这个模板可以直接套用到大多数状态空间搜索问题上。3. 盲目搜索没有先验信息时BFS 和 DFS 怎么选3.1 BFS 的队列实现与层数控制盲目搜索里最常用的是广度优先搜索BFS。它按层扩展先访问所有距离初始状态为 1 的状态再访问距离为 2 的以此类推。BFS 的优点是只要存在解且每步代价相同它一定能找到最短路径。实现上用队列先进先出。工程上要注意的是层数控制因为 BFS 的内存消耗随层数指数增长。from collections import deque def bfs(initial_state, goal_state, max_depth20): queue deque([(initial_state, 0)]) # (状态, 深度) visited {initial_state} while queue: state, depth queue.popleft() if state goal_state: return state, depth if depth max_depth: continue # 超过深度限制不再扩展 for nxt in get_neighbors(state): if nxt not in visited: visited.add(nxt) queue.append((nxt, depth 1)) return None, -1max_depth是一个保护参数防止在无解问题上无限扩展。实际调参时可以先设一个较小的值比如 15跑一遍看是否能找到解再逐步放大。visited集合在入队时更新保证每个状态只入队一次。BFS 的时间复杂度是 O(b^d)空间复杂度也是 O(b^d)因为要保存所有已访问状态。当 b3、d15 时状态数约 1400 万内存会非常紧张。3.2 DFS 的栈实现与深度限制深度优先搜索DFS沿着一条路径走到底再回溯。实现上用栈后进先出。DFS 的空间复杂度是 O(bd)比 BFS 小很多但它不保证找到最短路径而且可能陷入很深的子树。工程上通常用迭代加深或者深度限制来规避。def dfs(initial_state, goal_state, max_depth20): stack [(initial_state, 0, [initial_state])] visited set() while stack: state, depth, path stack.pop() if state goal_state: return path if depth max_depth: continue if state in visited: continue visited.add(state) for nxt in get_neighbors(state): if nxt not in visited: stack.append((nxt, depth 1, path [nxt])) return None这里path随状态一起入栈避免回溯时再重建路径。visited在出栈时检查因为同一个状态可能通过不同路径到达先到的不一定是最优的。DFS 适合解空间深但分支少的问题比如某些规划问题。参数max_depth需要根据问题规模调整太小会漏解太大会退化成穷举。3.3 盲目搜索的适用边界什么时候必须换启发式盲目搜索的适用边界很明确状态空间小或者对最优性没有要求或者只需要找到一个可行解。一旦状态空间超过 10^6BFS 的内存就会成为瓶颈DFS 虽然省内存但找到的解质量不可控。这时候就必须引入启发式信息。判断标准很简单如果你能对任意状态给出一个「离目标还有多远」的估计就应该用启发式搜索而不是继续硬扛盲目搜索。注意盲目搜索不是「笨」它是启发式搜索的基础。很多启发式搜索的代码框架就是把 BFS 的队列换成优先队列其余逻辑几乎不变。4. 启发式搜索给搜索装上一个方向感4.1 启发函数设计曼哈顿距离与错位棋子数启发式搜索的核心是启发函数 h(n)它估计从状态 n 到目标状态的最小代价。设计启发函数有两个原则一是不能高估真实代价否则会破坏最优性二是越接近真实代价搜索效率越高。八数码问题里常用的两个启发函数是错位棋子数和曼哈顿距离。错位棋子数统计有多少个数字不在目标位置上实现简单但估计偏松。曼哈顿距离统计每个数字当前位置到目标位置的横纵距离之和估计更紧搜索效率更高。工程上一般优先用曼哈顿距离因为它的计算开销和错位棋子数差不多但剪枝效果明显更好。def manhattan_distance(state, goal): distance 0 for i, val in enumerate(state): if val 0: continue # 空格不计入 goal_idx goal.index(val) row1, col1 divmod(i, 3) row2, col2 divmod(goal_idx, 3) distance abs(row1 - row2) abs(col1 - col2) return distance def misplaced_tiles(state, goal): return sum(1 for i, val in enumerate(state) if val ! 0 and val ! goal[i])manhattan_distance里空格被跳过因为空格的移动本身不产生代价它只是其他数字移动的载体。goal.index(val)是 O(9) 的查找在 3×3 棋盘上可以接受如果棋盘更大应该预先建一个位置索引表。这两个函数都满足可采纳性即不会高估真实代价所以配合 A* 使用时能保证找到最优解。4.2 贪婪最佳优先搜索快但不保证最优贪婪最佳优先搜索只考虑 h(n)每次扩展 h(n) 最小的状态。它不管已经走了多少步只看「看起来离目标有多近」。优点是速度快缺点是可能绕远路甚至找不到最优解。实现上用一个优先队列按 h(n) 排序。import heapq def greedy_best_first(initial_state, goal_state): pq [(manhattan_distance(initial_state, goal_state), initial_state)] visited {initial_state} parent {initial_state: None} while pq: _, state heapq.heappop(pq) if state goal_state: path [] while state is not None: path.append(state) state parent[state] return path[::-1] for nxt in get_neighbors(state): if nxt not in visited: visited.add(nxt) parent[nxt] state h manhattan_distance(nxt, goal_state) heapq.heappush(pq, (h, nxt)) return None优先队列里存的是(h, state)元组heapq 会先比较 hh 相同时比较 state。state 是元组可以比较所以不会报错。visited在入队时更新保证每个状态只入队一次。贪婪搜索的问题在于它可能沿着一条看起来很近但实际很绕的路走最终解的长度远大于最优解。工程上如果对解的质量有要求不要用贪婪搜索。4.3 启发函数的可采纳性与一致性可采纳性Admissibility是指 h(n) 永远不超过从 n 到目标的真实最小代价。一致性Consistency是指 h(n) ≤ cost(n, n) h(n)即三角不等式。可采纳性保证 A* 找到最优解一致性保证 A* 不需要重复扩展已访问节点。曼哈顿距离在八数码问题里既满足可采纳性也满足一致性。验证方法很简单随机生成一批状态用 BFS 算出真实最短距离再和 h(n) 比较如果所有样本里 h(n) 都小于等于真实距离就是可采纳的。一致性验证需要检查每条边工程上一般信任经典启发函数的性质不需要每次重新验证。但如果自己设计启发函数这一步不能省。提示如果启发函数高估了真实代价A* 可能返回次优解。这是最隐蔽的坑因为搜索结果看起来是「一条路径」但未必是最短的。5. A算法和A*算法把代价和启发合在一起5.1 A 算法的评估函数 f(n) g(n) h(n)A 算法的核心是评估函数 f(n) g(n) h(n)。g(n) 是从初始状态到 n 的实际代价h(n) 是从 n 到目标的估计代价。A 算法每次扩展 f(n) 最小的状态。如果 h(n) 恒为 0A 算法退化成 BFS如果只考虑 h(n)退化成贪婪搜索。A* 算法是 A 算法的一个特例要求 h(n) 满足可采纳性这样能保证找到最优解。def a_star(initial_state, goal_state): pq [(manhattan_distance(initial_state, goal_state), 0, initial_state)] visited {} parent {initial_state: None} while pq: f, g, state heapq.heappop(pq) if state goal_state: path [] while state is not None: path.append(state) state parent[state] return path[::-1] if state in visited and visited[state] g: continue # 已经有更优路径到达该状态 visited[state] g for nxt in get_neighbors(state): new_g g 1 if nxt not in visited or new_g visited[nxt]: parent[nxt] state h manhattan_distance(nxt, goal_state) heapq.heappush(pq, (new_g h, new_g, nxt)) return None优先队列里存(f, g, state)f 相同时比较 gg 相同时比较 state。visited字典记录到达每个状态的最小 g 值如果新路径的 g 更大就跳过。这个判断是 A* 效率的关键没有它同一个状态可能被多次扩展。参数上new_g g 1假设每步代价为 1如果代价不同需要从动作里读取实际代价。5.2 A* 的最优性条件与重复扩展问题A* 找到最优解的条件是 h(n) 可采纳。如果 h(n) 还是一致的那么每个状态只需要扩展一次不需要重复处理。如果 h(n) 可采纳但不一致可能需要多次扩展同一个状态这时候要用「开放列表」和「关闭列表」配合关闭列表里记录已扩展状态的最小 g 值新路径更优时重新打开。工程上曼哈顿距离是一致的所以上面的代码用visited字典就够了。但如果换成自己设计的启发函数一定要先验证一致性否则可能漏掉更优路径。重复扩展的代价是时间变长但不会影响最优性只要正确处理 g 值比较。5.3 权重 A*用最优性换速度的工程取舍实际工程里有时候不需要严格最优只需要「足够好且快」。这时候可以用权重 A*把评估函数改成 f(n) g(n) w × h(n)w 1。w 越大搜索越偏向 h(n)速度越快但解的质量越差。w 1 时就是标准 A*w 很大时接近贪婪搜索。def weighted_a_star(initial_state, goal_state, w1.5): pq [(w * manhattan_distance(initial_state, goal_state), 0, initial_state)] visited {} parent {initial_state: None} while pq: f, g, state heapq.heappop(pq) if state goal_state: path [] while state is not None: path.append(state) state parent[state] return path[::-1] if state in visited and visited[state] g: continue visited[state] g for nxt in get_neighbors(state): new_g g 1 if nxt not in visited or new_g visited[nxt]: parent[nxt] state h manhattan_distance(nxt, goal_state) heapq.heappush(pq, (new_g w * h, new_g, nxt)) return Nonew 的取值需要根据问题调。我一般从 1.2 开始试逐步加大到 2.0观察解的长度和搜索时间的变化。如果解的长度增加不超过 10%但搜索时间减少一半这个 w 就是值得的。权重 A* 在路径规划、游戏寻路里很常见因为玩家感知不到 5% 的路径长度差异但能感知到卡顿。6. 避坑与排查搜索算法落地时最容易翻车的五个点6.1 状态去重不彻底导致队列爆炸现象程序跑了几分钟内存飙升队列长度指数增长。原因visited集合在出队时才更新导致同一个状态被多次入队。解决在入队前检查visited入队时立即加入。如果状态不可哈希先序列化成字符串再入集合。6.2 启发函数高估导致解不是最优现象A* 返回了一条路径但比 BFS 找到的路径长。原因h(n) 在某些状态下大于真实代价。解决用 BFS 采样验证 h(n) 的可采纳性或者改用已知可采纳的启发函数。曼哈顿距离在八数码里是可采纳的但如果问题里有障碍物直线距离可能高估需要换成实际可走路径的估计。6.3 优先队列里放不可比较的对象现象heapq.heappush报 TypeError说元组不能比较。原因优先队列里存了(f, state)f 相同时 Python 会尝试比较 state如果 state 是字典或自定义对象就会报错。解决在元组里加一个自增计数器变成(f, count, state)count 保证唯一性避免比较 state。6.4 深度限制设得太小导致漏解现象DFS 或迭代加深搜索返回 None但问题其实有解。原因max_depth设得比真实解深度小。解决先用 BFS 在小规模上跑一遍估算解的平均深度再把max_depth设为估算值的 1.5 倍。如果问题无解深度限制是必要的保护但要有日志输出方便判断是「无解」还是「深度不够」。6.5 路径回溯时 parent 字典被覆盖现象找到目标后回溯路径发现路径中间断开了。原因同一个状态被多次扩展parent字典被后一次扩展覆盖但后一次不一定在最优路径上。解决只在找到更优 g 值时更新parent并且回溯时从目标状态开始沿着parent一直走到初始状态。如果parent里出现环说明更新逻辑有问题需要检查 g 值比较条件。注意这五个坑里去重和启发函数可采纳性是最常见的。前者导致跑不完后者导致结果不对。先把这两个搞定再调性能。7. 从能跑到好用A* 的工程调优与验证习惯把 A* 跑通只是第一步真正落地时还要做几件事。第一是启发函数缓存。曼哈顿距离在每次扩展时都要算一遍如果同一个状态被多次访问重复计算很浪费。我一般用一个字典缓存h_cache[state] h命中率在八数码问题里能到 30% 以上。第二是优先队列的惰性删除。A* 里同一个状态可能以不同的 g 值多次入队出队时检查visited里的 g 值如果当前 g 更大就跳过这样不需要在入队时删除旧条目实现更简单。第三是验证。每次改完启发函数或权重我会跑一组固定测试用例记录解的长度、扩展节点数、运行时间。解的长度用来验证最优性扩展节点数用来衡量启发函数的剪枝效果运行时间用来判断工程可用性。这三个指标里扩展节点数最能反映启发函数的质量。如果换了启发函数后扩展节点数没降说明新函数没有提供额外信息。指标标准 A*权重 A* (w1.5)贪婪搜索解的长度最优接近最优可能远大于最优扩展节点数中等较少最少运行时间中等较快最快内存占用中等较少最少这张表是我在八数码随机 100 个可解局面上跑出来的经验值。权重 A* 在 w1.5 时解的长度平均增加 8%扩展节点数减少 40%运行时间减少 35%。这个取舍在大多数工程场景里是划算的。但如果你的场景对路径长度极其敏感比如物流调度那就老老实实用标准 A*别为了速度牺牲最优性。最后一个习惯每次写完搜索代码先用一个 3×3 的简单局面手动验证路径。比如初始状态只差一步就能到目标看算法能不能返回长度为 1 的路径。这个手动验证能抓住大部分低级错误比如动作方向写反、目标判断写错、路径回溯顺序颠倒。我在这上面翻过车花了两个小时排查最后发现是get_neighbors里行列计算把row和col写反了。希望帮到你。本文还有配套的精品资源点击获取