简介这是一份基于伯克利大学AI Pacman项目的搜索算法解决方案面向正在学习人工智能、搜索策略与Python编程的开发者。资源围绕吃豆人游戏中的智能决策完整覆盖广度优先搜索、深度优先搜索、A星搜索、Dijkstra算法并延伸至最小最大搜索、α-β剪枝与Q学习等高级AI策略通过具体游戏场景展示各类算法的实现方式与适用场景适合用于理解算法原理和动手实践。包体共23个文件以Python脚本为主20个py涵盖游戏逻辑、搜索智能体、图形显示、自动评测等模块另有Markdown说明文档、文本命令说明与许可文件zip压缩包整体仅67KB轻量易用。目前已有564人学习对于希望系统掌握搜索算法并完成伯克利AI课程作业的读者这份资源提供了完整的代码参考与测试环境可帮助对照作业要求逐模块调试、验证算法效果是一份高性价比的学习资料。1. 为什么迷宫明明有全图Pacman 依然要搜索地图就摊在眼前墙、豆子、出口全部可见迷宫对 Pacman 来说并不是一个「未知空间」。那这个项目为什么还把它叫 Search很多人把 DFS、BFS、A* 的代码背下来对着测试跑通却没想过这个反直觉的起点这里的搜索不是「找路」而是「把找路这件事形式化」。状态怎么定义、目标怎么判断、后继怎么生成——这三行接口一旦定义错再正确的算法也会在 2^n 的状态空间里原地转圈。这份解决方案的价值不在于把算法写对而在于把「状态空间长什么样」这件事讲透。理解了它你再看任何搜索项目都不会再把栈和队列当作分水岭。2. 无信息搜索BFS 与 DFS 的状态空间为什么会差一个数量级无信息搜索里没有启发式算法只靠「下一步有哪些选择」在状态图里漫游。Pacman 的地图网格度是 4上下左右看起来简单但 BFS 和 DFS 的实际表现可以差一个数量级。差距不在算法思想而在数据结构对状态图的遍历顺序以及你的状态里装了什么。2.1 三件套接口为什么 DFS、BFS、A* 能共用同一套骨架这份解决方案里的搜索框架最先展示的是一个统一的「搜索问题」接口而不是五个各写各的算法。它把问题收敛成三个抽象方法所有搜索算法只认这一层接口不认识迷宫的具体形状。class SearchProblem: # 搜索问题的最小完备描述只需要回答三个问题 def getStartState(self): # 返回初始状态Pacman 里通常是 (x, y) 或带附加信息的元组 raise NotImplementedError def isGoalState(self, state): # 给定一个状态回答“这是不是终点” raise NotImplementedError def getSuccessors(self, state): # 返回所有合法转移每一项是 (next_state, action, step_cost) raise NotImplementedError三个方法就是「初始状态、目标集合、转移函数」任何搜索问题都能翻译成这三样。迷宫地图本身没有作为参数传给算法它被封装在 getSuccessors 内部——算法眼里只有一张由状态和转移组成的图不关心底层是网格还是棋盘。这是整个搜索框架的设计骨架数据结构栈、队列、优先队列是唯一需要换的东西算法骨架不用动。在这个三件套里最容易出问题的是 state 的信息量。对「找到出口」这样的单目标问题(x, y) 坐标就够了但对「访问四个角落」这种带有记忆的任务坐标相同但已经走过的角落数不同未来需要的信息就完全不同。如果你的 state 只放坐标搜索会在同一个位置反复出现reached 集合把它当成「来过」直接丢掉然后目标永远探测不到。我看过不少翻车的实现bug 都不在算法而在 state 定义得太小状态丢掉了历史搜索就失去了记忆力。反过来state 塞太多也有问题比如直接把整个食物网格放进状态哈希和拷贝成本立刻暴涨这是后面要讲的另一个坑。2.2 栈与队列的遍历顺序为什么 DFS 快但莽BFS 稳但吃内存先看 DFS 的完整实现。这个写法依赖两个数据结构一个 LIFO 的栈一个记录已访问状态的集合。def depthFirstSearch(problem): # 栈模拟递归不用递归是因为 Python 递归深度受限 # 而迷宫一条路径就能走出几百步 frontier Stack() # LIFO后进先出 reached set() start problem.getStartState() frontier.push((start, [], 0)) # (状态, 已行动作列表, 累计代价) while not frontier.isEmpty(): state, actions, cost frontier.pop() if problem.isGoalState(state): return actions # 第一次摸到目标就返回 if state in reached: continue # 惰性去重弹出时再判重 reached.add(state) for next_state, action, step_cost in problem.getSuccessors(state): frontier.push((next_state, actions [action], cost step_cost)) return []这段代码有两个容易被忽略的细节它们决定了它和你随手写的 DFS 是两码事。第一个细节是 reached 的检查时机它在弹出时检查而不是在压入时标记。对纯 DFS 来说push 时标记也能跑但在 A* 和加权搜索里这个时机直接决定你还能不能拿到最优解——同一个状态先以一条较差的路径到达如果提前被「拉黑」真正的最优路径就被挡在门外。统一在 pop 时检查相当于允许同一个状态多次入队但只扩展一次这是图搜索里最稳的写法后面 A* 还会用到。第二个细节是actions [action]。每扩展一层就复制一次列表路径越长拷贝开销越大这是把路径「存在节点里」而不是「回溯拼出来」的代价。Pacman 项目的搜索深度通常只有几百动作列表几 KB可读性优先所以刻意这么写真正的工程场景里你会换成 parent 指针 最后回溯把 O(depth) 的每次拷贝降到 O(1)。BFS 和 DFS 只有一行之差容器从 Stack 换成 Queue。def breadthFirstSearch(problem): frontier Queue() # FIFO先进先出 reached set() start problem.getStartState() frontier.push((start, [], 0)) while not frontier.isEmpty(): state, actions, cost frontier.pop() if problem.isGoalState(state): return actions if state in reached: continue reached.add(state) for next_state, action, step_cost in problem.getSuccessors(state): if next_state not in reached: frontier.push((next_state, actions [action], cost step_cost)) return []遍历顺序改变后性质完全不同BFS 按层推进第一次弹出的目标一定在最浅层。Pacman 地图每一步代价都是 1因此最浅就是距离最短BFS 天然给出全局最短路径。注意我在 BFS 里加了一个if next_state not in reached的入队前过滤这跟 DFS 的处理不同。原因是队列按层扩展一个状态第一次被压入时就处于能到达它的最浅层所以 push 前判重是安全的在 DFS 里这么写反而会挡住深层的可达路径。两种判重时机用在两个算法里结果不同这是图搜索的经典细节。真正让 BFS 在 Pacman 上翻车的不是重复状态而是队列本身的膨胀。网格度为 4每一层的节点数大约按 4^depth 的规模增长而每个节点又带着一整条动作列表副本内存和 GC 压力很快就上来了。一个稍大的地图就能让 BFS 的队列同时挤进上万条路径副本肉眼可见地卡死。算法容器弹出第一个目标时的性质主要风险DFS栈某一条可达路径可能深到超时不保证短BFS队列最浅路径等代价队列内存爆炸UCS优先队列g代价最小路径依赖边权分布扩展范围大A*优先队列gh最优路径h 可采纳时启发式质量决定性能表格里的 UCS 在改动上只是把队列换成按 g 排序的优先队列在动作代价全为 1 的 Pacman 里它和 BFS 等价。但项目里特意把 step_cost 这个参数留在接口里是为了支持「转向更贵」「不同地形代价不同」这类扩展——三件套接口不变只改边权搜索框架就适配了新场景。这也是为什么教学中 UCS 必须单独写它不是新算法是「边权不统一时的 BFS」。3. 启发式搜索A* 的 fgh 是如何把「最优」变成可计算事实的BFS 在浅目标上很灵但目标一旦藏得深队列里积压的层数会先把你压垮。A* 的思路是把「方向感」注入优先队列不只算已经花掉的代价 g还要估计剩余代价 h两者相加决定下一个扩展谁。这一章拆开 A* 的保证看它为什么敢在第一次弹出目标时就宣布这是最优解。3.1 从 UCS 到 A*优先队列的键变一下搜索就变了个物种UCS 弹出的是 g 最小的状态它像一个以起点为圆心的波均匀向外扩散。A* 只做一处修改排序键从 g 变成 f g h。h 是启发式是对「从当前状态到目标还要花多少」的估计。这个估计越准波的形状就越不像圆而是越拉越长像一支箭直接射向目标。def aStarSearch(problem, heuristicnullHeuristic): # A* 是 UCS 的特例heuristic 全为 0 时退化为 UCS frontier PriorityQueue() # 按 f g h 排序 reached set() start problem.getStartState() frontier.push((start, [], 0), heuristic(start, problem)) while not frontier.isEmpty(): state, actions, g frontier.pop() # 弹出的是 f 最小的状态 if problem.isGoalState(state): return actions if state in reached: continue reached.add(state) for next_state, action, cost in problem.getSuccessors(state): new_g g cost h heuristic(next_state, problem) frontier.push((next_state, actions [action], new_g), new_g h) return []注意优先队列的 push 接收两个参数数据和优先级。这里优先级是new_g h而数据里只存 gh 没有进状态。这个设计是刻意的启发式是「关于状态的函数」同一个状态无论从哪条路到达h 都一样所以只需要在计算优先级时取一次。这也意味着启发式必须是纯函数不能有随机性否则 A* 的保证立刻失效。h0 时f 就等于 gA* 退化成 UCS——代码完全不用改只要把 nullHeuristic 传进去。这是一个很好的自检手段先用 h0 跑通再换真实启发式对比扩展节点数。扩展数明显下降说明启发式在起作用没下降说明你的 h 和问题的真实结构无关。3.2 可采纳性与一致性为什么第一次弹到目标就能收工A* 最优性证明的核心只有一句话h 必须永远「乐观」。形式化地说对任意状态 nh(n) 不能超过从 n 到目标的真实最小代价 h*(n)这叫可采纳性。记住这条性质那个「第一次弹出目标就是最优」的结论就是水到渠成的。设 f* 是最优解的代价。对最优路径上的任意节点 n因为 h(n) ≤ h*(n)所以 f(n) g(n) h(n) ≤ g(n) h*(n) f*。也就是说最优路径上的每一个前缘节点它的 f 值都不会超过 f*。假设 A* 先弹出的是一个非最优目标 t其路径代价 C f*那么在弹出 t 之前边界上必然存在某个最优路径上的节点 m而 f(m) ≤ f* C f(t)。优先队列永远先弹 f 小的m 就会先于 t 被弹出矛盾。所以 A* 不可能先弹出一个非最优目标。可采纳性保证「第一次弹出目标即最优」但代码里还有一个 reached 集合这就牵扯出第二个性质一致性也叫单调性。如果 h 满足对任意转移都成立 h(n) ≤ cost(n, n) h(n)那么 f 沿路径单调不减。这种情况下一个状态第一次被弹出时 g 就已经是最优reached 可以直接封存。如果 h 只有可采纳性而没有一致性同一个状态可能被重复打开reached 一旦拒绝就会丢掉更优路径。这个项目里的实现为什么在 pop 时检查 reached我一般会这么理解这是一种「惰性删除」策略它等价于允许同一个状态多次入队只有被弹出时才算数。这比在 push 时严格判重更鲁棒即使你的启发式只可采纳不一致它也不会因为提前拉黑而丢掉最优解。代价是同一状态可能入队多次队列略臃肿但换来的是「算法性质变了也不会悄悄出错」的容错性。提示判断启发式是否可采纳最土但最可靠的办法是拿 h0 的 A* 和你的 A* 在同一个随机迷宫里对比扩展节点数。如果引入启发式后扩展数反而变多或者运行中出现 f 值回退后弹出的节点 f 比先弹出的还小它多半已经悄悄高估了。3.3 启发式质量曼哈顿距离对 Pacman 意味着什么nullHeuristic 直接返回 0它是可采纳的但一点方向感都没有。Pacman 里最常用的真实启发式是曼哈顿距离。def nullHeuristic(state, problemNone): # 可采纳但毫无信息的启发式等价于把 A* 退化成 UCS return 0 def manhattanHeuristic(state, problemNone): # 对单目标场景把墙全部抹掉后的理想步数 x, y state gx, gy problem.goal return abs(x - gx) abs(y - gy)为什么曼哈顿距离对 Pacman 可采纳因为 Pacman 每次只能向上下左右挪一格任何真实路径都必须走至少 |dx| |dy| 步曼哈顿距离是「无视墙的存在」的理想步数它永远不会高估真实代价。欧氏距离在几何上更短在这个网格模型里反而更弱|dx||dy| ≥ sqrt(dx²dy²)所以曼哈顿距离给出的下界更紧A* 扩展的节点更少。这个例子的价值在于它给出了设计启发式的一般套路先把问题里的「硬约束」一个个拆掉看剩下的松弛问题能不能精确求解。曼哈顿距离就是拆掉了「墙」这个约束剩下的自由网格上最短路径有闭式解。后面 Corners 和食物收集的启发式用的都是同一套拆解逻辑只是拆掉的约束更多剩下的松弛问题也更复杂。4. 更聪明的启发式Corners 与食物收集的次优解是怎么设计的单一目标时曼哈顿距离够用。但 Pacman 的进阶任务不是找一个出口而是「吃遍四个角落」甚至「吃掉地图上所有豆子」。这时候状态要扩大启发式也要升级。这一章从子问题分解讲到最小生成树最后说清楚什么时候该体面地放弃最优性。4.1 Corners 问题为什么「到最远未访问角落的距离」是可采纳的Corners 问题的目标是访问地图四个角落访问顺序不限。朴素状态 (x, y) 不够了因为这时的目标是一个「集合」必须知道哪些角落已经去过。标准做法是把状态升级成 (position, visited_corners)visited 用 tuple 保持可哈希。def cornersHeuristic(state, problem): pos, visited state # togo 是还没访问过的角落列表 togo [c for c in problem.corners if c not in visited] if not togo: return 0 # 启发式 到最远未访问角落的曼哈顿距离 # 因为无论如何都要走遍所有未访问角落 # 至少得走到其中「最远」的那一个 return max(manhattan(pos, c) for c in togo)这个启发式是「拆掉墙」之后再进一步「拆掉访问顺序」真实任务要求访问所有未访问角落而访问完所有点的一条路径至少要走完其中离当前位置最远的那一个点。取 max 保证了它是一个合法的下界可采纳性没问题。但它的质量不算好。如果四个角落分布在对角两边取最远距离大致贴近真实代价如果它们聚在一起这个下界就很松A* 会多扩展很多节点。一个更紧的做法是把它升级成 MST以当前位置和所有未访问角落为点集求最小生成树的边长之和。因为一条访问路径本质上也是一棵连通这些点的树而 MST 是所有连通树里权重最小的路径长度必然不小于 MST 权重。对于只有四五个点的集合Prim 或 Kruskal 的常数极小这个启发式几乎免费。4.2 食物收集把路径下界松弛成最小生成树FoodSearchProblem 是 Corners 的极端版要访问的不是 4 个角落而是地图上所有食物点数量可以到三四十个。状态里塞一个食物集合复杂度直接上到 2^n这是普通 A* 无法招架的规模所以启发式设计成了这个任务真正的核心。from functools import lru_cache def foodHeuristic(state, problem): pos, food state foods food.asList() if not foods: return 0 # 点集 当前位置 所有食物点 nodes [pos] foods # 启发式 覆盖所有点的最小生成树权重 return manhattanMST(nodes) def manhattanMST(nodes): # 点集很小用 O(n^2) 的 Prim 实现避免重算所有点对距离 n len(nodes) visited [False] * n dist [float(inf)] * n dist[0] 0 total 0 for _ in range(n): # 从未访问点中选出离当前树最近的点 u min((d, i) for i, d in enumerate(dist) if not visited[i])[1] visited[u] True total dist[u] for v in range(n): if not visited[v]: d manhattan(nodes[u], nodes[v]) if d dist[v]: dist[v] d return total为什么 MST 权重可以作为「吃掉所有食物」的启发式关键在于路径和树的关系一条从当前位置出发、依次经过所有食物点的路径不管中间怎么绕圈把它访问过的边取出来总能整理出一棵连通所有点的树而这棵树的权重不超过路径的实际长度。MST 是所有连通所有点的树里权重最小的所以 MST 权重 ≤ 这棵树的权重 ≤ 真实路径长度。下界成立启发式可采纳。这里还有个性能细节A* 每扩展一个节点就要调一次 heuristic而 MST 每次都是 O(n^2) 的计算。好在启发式是状态的纯函数可以用 lru_cache 把 (pos, 食物掩码) 的结果缓存起来。同一个状态在搜索过程中会被反复从队列里弹出和评估缓存命中率极高能省掉绝大部分重复计算。食物掩码bitmask在这里还有一个额外的好处它让状态变成单个整数哈希和比较比 tuple 快一个数量级这也是大状态空间下 Python 代码能跑下去的常见优化。4.3 加权 A* 与子目标贪心放弃最优性换来能跑FoodSearchProblem 里状态空间是 2^n就算启发式再好精确 A* 也大概率跑不完。教学项目里通常允许这里用次优搜索因为「在合理时间内给出一个能吃完的路径」比「证明它最优」更符合真实需求。def weightedAStarSearch(problem, heuristic, w5): # 加权 A*f g w * h # w 越大越贪心扩展节点越少但路径可能拉长 frontier PriorityQueue() reached set() start problem.getStartState() frontier.push((start, [], 0), heuristic(start, problem) * w) while not frontier.isEmpty(): state, actions, g frontier.pop() if problem.isGoalState(state): return actions if state in reached: continue reached.add(state) for next_state, action, cost in problem.getSuccessors(state): new_g g cost h heuristic(next_state, problem) frontier.push((next_state, actions [action], new_g), new_g w * h) return []w 是权衡旋钮w1 时就是标准 A*w 越大搜索越像贪心——总想把 h 最小即离食物最近的节点先弹出来。实践中 w5 通常能让扩展节点数下降一个数量级路径长度只劣化百分之二三十这笔交易在食物任务里非常划算。真正的工程里还有另一种替代方案把「吃完全部食物」拆成反复执行的「吃最近的一个子目标」每步用标准 A* 规划一段这就是子目标贪心。它牺牲全局最优但每一步都短而准行为反而比一个巨大的加权 A* 更容易理解和调试。参数行为特征适用场景w1标准 A*扩展多保证最优小地图、需要证明最优w2~5加权 A*明显提速路径略劣中等地图可接受次优w 取大或子目标贪心近似贪心最快食物多到状态空间爆炸5. 避坑排查Pacman 搜索里五个看似正确实则翻车的细节搜索算法的坑往往不在算法本身而在实现细节和状态设计。下面五条是我在复现这个项目时最常踩的现场按「现象 → 原因 → 解决」拆开。5.1 启发式成了「高估狂魔」路径绕远却不报错现象A* 返回的路径比肉眼可见的绕路长出 20% 以上但程序不报错、不超时跑得飞快甚至每次都自信地返回「最优路径」。原因启发式高估了剩余代价。比如有人把移动代价设定为转向要加钱但曼哈顿距离仍然按步数算忽略了转向成本又比如对多目标任务取「到最近角落的距离」当启发式它虽然可采纳但下界太松扩展顺序被带偏。高估不会崩溃它只会静默地破坏最优性——这是最危险的一类 bug。解决用 h0 的 A* 作为对照组在随机小地图上对比两者扩展节点数和路径长度。如果启发式的加入没有明显减少扩展数或者路径反而更差基本可以断定高估。再进一步可以在 debug 模式里打印每次弹出的 f 值检查是否单调不减一旦出现回退就能定位到是哪一段启发式超了。5.2 reached 集合标记时机不对路径「凭空消失」现象DFS 返回 [] 或者 A* 在某些地图上找不到任何可达路径但用 BFS 手跑一遍明明存在解。原因在 push 时就把 next_state 加入 reached。同一个状态先被一条很差的路径到达后就被「拉黑」在 A* 里如果启发式不是完全一致的这条被拉黑的状态可能正是能通向目标的关键岔路。把 no 拉黑时机放错搜索就会失去「重开」的资格。解决统一改成 pop 时判重压入时不标记。代码上只有两行之差但语义上完全不同pop 时判重允许同一状态多次入队但只扩展一次既避免无限循环又不会挡住后到的更优路径。这也是我在 2.2 节里强调那个细节的原因。5.3 actions 列表拷贝成瘾内存先于超时崩溃现象BFS 在大地图上跑几十秒不出结果内存涨到几个 G进程被系统杀掉DFS 反而没事。原因actions [action]每扩展一层就复制一次整条动作列表BFS 队列里同时存着上万条路径副本O(depth) 的拷贝在层数大时变成灾难。这不是算法问题是表示法问题。解决小型教学关卡可以直接用 tuple 替代 list减少一点拷贝开销真正要跑大地图改成 parent 指针方案——每个节点只记 (parent_node, action)最后从目标一路回溯出完整路径把 O(depth) 的存储降到 O(1) 每节点。这条经验对后面做 Multi-Agent 同样适用博弈树的节点数量更大路径拷贝更是不能碰。5.4 死胡同里反复横跳自环动作混进了后继现象搜索路径出现令人抓狂的「左右横跳」或者原地不动DFS 在这种地方反复兜圈子最后超时。原因getSuccessors 返回了不合法的后继比如把「原地待着」也当成一个动作或者移动代价设置成了 0让搜索可以在某个区域零成本来回刷状态。状态图里的零成本环会绕过 reached 的保护——状态 A 到达 B 再回到 A如果代价为 0g 不增加优先队列可以把它们来回弹出。解决检查 getSuccessors 里每个后继的 step_cost确认代价严格为正自环动作直接过滤掉。注意反向移动是合法的Pacman 经常需要掉头不要一刀切把反向也去掉。这里的关键是不变量状态图必须有向且无零成本环搜索算法的终止性才不被破坏。5.5 启发式计算本身成了瓶颈A* 卡在自己的「大脑」上现象FoodSearch 每扩展一个节点就卡一下扩展了几百个节点后越来越慢整体跑了十几秒才结束。原因foodHeuristic 里的 MST 每次都重新计算所有点对距离虽然 O(n^2) 看起来不大但 A* 每弹出一个节点就调一次n30 时单次计算就有几百次曼哈顿距离运算总开销被放大到不可忽略。启发式函数虽然是纯的但如果没做缓存同一状态被反复评估的代价就白付了。解决用 lru_cache 或手写字典缓存 (pos, food_mask) 到启发式值的映射预计算食物点对之间的曼哈顿距离矩阵让 MST 查表而不是现场算。这两步合起来能把启发式开销降到几乎可以忽略。排查这个问题的方法是 profile统计 heuristic 被调用的次数和总耗时如果调用次数远超扩展节点数说明有重复评估如果单次耗时长说明该预计算了。6. 从 Search 到 Decision最优性是不是一个可以被放弃的东西搜索在 Pacman 里能完美工作是因为这个环境有三个理想前提完全可观测所有信息都在地图上、确定性每个动作的结果固定、静态除了你没人行动。这三个前提一旦松动A* 的整套保证就跟着松动。项目后面部分会引入鬼魂环境从确定性变成对抗性。同样的三件套状态图还在但 getSuccessors 不再返回确定的后继而是「你的动作 鬼的动作」共同决定下一步。于是搜索树变成了博弈树原本的 DFS 回溯变成了极小极大搜索启发式换成了评估函数——这个过渡不是另起炉灶而是把搜索框架的「转移」从函数升级成了博弈。理解了这个连贯性再看 Multi-Agent 部分就不会觉得突兀。真正值得琢磨的设计取舍是这个项目为什么允许你在食物任务里用次优解因为「可采纳且一致」的启发式本质上是要求你对剩余问题给出一个永远不会出错的下界但真实任务的剩余问题本身就是 NP-hard 级精确下界算不出来。工程里的做法是把「最优性」降级成「在限定时间内给出可行动的方案」加权 A*、子目标贪心、甚至把启发式换成学习出来的网络都是在用「理论上不再保证最优」换取「实际能跑完」。在那次之后我形成了两个习惯。第一动手写任何搜索代码前强制自己先回答三个问题状态里包含哪些记忆、后继是否会产生零成本环、启发式的下界是否真的不会高估。第二把「能跑」和「正确」分开验证先跑 h0 的版本确认框架再加启发式对比扩展数确认收益。这套流程帮我挡掉了绝大多数看着像玄学的问题希望帮到你。本文还有配套的精品资源点击获取