简介：这是伯克利大学经典人工智能吃豆人项目的搜索算法完整解决方案，使用Python实现，面向学习搜索策略与人工智能原理的学生和开发者。资源完整覆盖吃豆人游戏中的基础搜索方法，包括广度优先搜索、深度优先搜索、A星搜索、Dijkstra算法，并延伸到极小极大搜索、Alpha-Beta剪枝和Q学习等进阶AI策略，源码均配有注释与测试用例。包内共23个文件，其中20个Python源文件构成核心算法与游戏框架，另有说明文档、命令文件和许可证文件，压缩包仅67KB，轻量精简，主模块与辅助工具齐全，便于快速下载与部署。目前已有564人学习此资源。通过本套代码可对照标准实现，深入理解各搜索算法在真实博弈场景中的编码方式，也适合用于课程作业参考、算法对比实验或二次开发学习。

1. AI-Pacman 搜索项目实战：让吃豆人自己找路，一份能跑通的完整解答

你可能也遇到过这种情况：学完搜索算法，理论都懂，一上手写代码就卡在状态怎么定义、返回值怎么组织、为什么 dfs 会绕路。这套 AI-Pacman 的 Search 解决方案，正好解决这个问题。整个项目用纯 Python 实现，覆盖 DFS、BFS、UCS、A* 四种经典搜索算法，以及两个进阶场景：Corners 问题和 Food 问题。最直观的感受是，同一个 mediumMaze，用 BFS 只要几十毫秒就能跑出最短路径；但换 DFS 在 bigMaze 上就会明显绕远路，而 A* 的扩展节点数只有 BFS 的大约一半。这份方案把搜索问题抽象成统一的 problem 接口，适合刚入门 AI 算法、想动手验证一遍理论的人，也适合做课程作业时被状态哈希、坐标系翻转这些细节卡住的同学直接对照参考。

2. 项目结构拆解：从命令行参数到图形界面的完整数据流

拿到资源第一步不是打开代码就改，而是先把文件分层看明白。这个项目的结构设计很典型：底层游戏逻辑、中层搜索算法、上层 Agent 调度，三层解耦得非常干净。知道每个文件负责什么，后面改起来才不会被牵着鼻子走。

2.1 文件布局：框架文件、算法文件、评测文件各管什么

整个项目按职责可以分成四类：入口与游戏循环、搜索算法实现、问题定义、工具与评测。用一张表快速过一遍：

这里最值得学习的是 search.py 的设计：它完全不依赖图形界面和 Pacman 的具体逻辑，只用 problem 接口打交道。搜索算法只认四个方法——getStartState、isGoalState、getSuccessors、getCostOfActions。这种解耦带来的好处很实际：换一个布局、换一个场景，甚至换一个完全不同的游戏，只要实现同样的接口，四个搜索函数一个字都不用改，这也是 autograder 能批量跑通所有问题的前提。

2.2 启动链路：一条命令行触发一次搜索的完整流程

先看最常用的启动命令：

python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs

命令行参数拆开看：-l指定用 layouts 目录下的哪个地图，-p指定用哪个 Agent 类，-a是传给 Agent 的构造参数。这里的fn=bfs意思是让 SearchAgent 内部调用 search.py 里的 breadthFirstSearch 函数。整个流程是：SearchAgent 初始化时立即执行搜索，把整条路径算好存起来；游戏开始后每一帧调一次 getAction，从路径里按顺序取一个动作返回。

class SearchAgent: def __init__(self, fn='depthFirstSearch', prob='PositionSearchProblem', heuristic='nullHeuristic'): self.searchFunction = getattr(search, fn) self.heuristic = getattr(search, heuristic) self.searchType = globals()[prob] self.actionIndex = 0 self.actions = [] problem = self.searchType(self) if fn != 'aStarSearch': self.actions = self.searchFunction(problem) else: self.actions = self.searchFunction(problem, self.heuristic) def getAction(self, state): if self.actionIndex < len(self.actions): action = self.actions[self.actionIndex] self.actionIndex += 1 return action return 'Stop'

逻辑说明：getattr(search, fn)是在 search 模块里按名字找函数，这就是为什么命令行里传入字符串bfs就能动态绑定到 breadthFirstSearch。A* 特殊处理是因为它比另外三个函数多一个启发式参数。游戏运行时 getAction 每次只返回一个动作，动作序列用完了就返回'Stop'让吃豆人原地待着。

参数说明：prob默认是PositionSearchProblem，它把迷宫抽象成一个单目标搜索问题；heuristic默认是nullHeuristic，恒返回 0，如果跑 A* 不指定启发式，效果就和 UCS 完全一致。所以测试 A* 时记得加heuristic=manhattanHeuristic。

2.3 状态表示：为什么 state 必须是一个不可变的 tuple

搜索问题的状态定义直接决定能不能跑起来。PositionSearchProblem 返回的状态是一个三元组(x, y, direction)，包含了坐标和朝向。四个方向移动后，新状态就是一个新的三元组。这里有一个所有人都可能踩的坑：visited 集合用来判重，必须对状态做哈希，所以状态必须是不可变对象。一旦有人图省事把状态存成[x, y, direction]这种 list，程序直接抛unhashable type: 'list'，搜索根本跑不起来。

另外注意图形层坐标和逻辑层坐标的差异。layout 文本文件里 y 轴是向下增长的，图形渲染时会做翻转，但你写搜索算法时完全不需要关心这些，只认 problem 的 getSuccessors 返回的状态。我自己一开始就犯过这个错：对着渲染画面里的坐标去推墙的位置，结果进去之后全是墙。后来学乖了，所有坐标都以搜索问题内部的接口返回值为准，渲染层对你来说就是个黑匣子。

3. 核心算法实现：四个搜索函数从 DFS 到 A* 的一行差异

这一章是整个资源的核心价值。四个算法放在一起看，会发现它们的骨架几乎一样，区别只在 frontier 用哪种数据结构：栈、队列还是优先队列。理解了这一点，四个函数就不用分开背了。

3.1 统一搜索框架：frontier 加 explored set 加路径累积

通用的图搜索模板长这样：把起始状态放入 frontier；循环里从 frontier 取出一个状态，如果是目标就返回路径；没访问过就标记 explored；再把所有后继状态连同路径一起压入 frontier。四个算法的差异，百分之百集中在「取出哪个状态」这一步。

这里有一个实现细节值得多说一句：判重到底是 push 时做还是 pop 时做。我的习惯是 pop 时判重，也就是先取出状态，再看它是否已经在 explored 里。push 时判重能减小 frontier 的体积，但在带权图上可能漏掉更优路径；pop 时判重牺牲一点点内存，换来的是正确性。像 UCS 场景下，同一个状态可能以不同代价被多次压入队列，pop 时判重才能保证最优的那一次被使用。

3.2 DFS 和 BFS：同样是几行代码，差别只在容器

DFS 用栈，后进先出，深度优先地往下钻。实现如下：

def depthFirstSearch(problem): frontier = util.Stack() frontier.push((problem.getStartState(), [], 0)) visited = set() while not frontier.isEmpty(): state, path, cost = frontier.pop() if problem.isGoalState(state): return path if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): if nextState not in visited: frontier.push((nextState, path + [action], cost + stepCost)) return []

逻辑说明：栈里存的是三元组，path是从起点到当前状态的完整动作列表，cost是累计代价。push 进去时把 path 一起带上，省掉了用 parent 指针回溯的麻烦。找到目标直接返回当前 path，这个 path 因为是 DFS 找出来的，不保证最短。

参数说明：problem.getSuccessors返回的元组是(nextState, action, stepCost)，其中 stepCost 在普通迷宫里恒为 1，但接口保留了加权图的可能性。

BFS 的代码和 DFS 几乎一样，只换一个容器：

def breadthFirstSearch(problem): frontier = util.Queue() frontier.push((problem.getStartState(), [], 0)) visited = set() while not frontier.isEmpty(): state, path, cost = frontier.pop() if problem.isGoalState(state): return path if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): if nextState not in visited: frontier.push((nextState, path + [action], cost + stepCost)) return []

逻辑说明：Queue 是先入先出，逐层扩展，所以第一次到达目标状态时的路径就是最短路径（前提是每步代价相同）。在 maze 这种单位代价场景里，BFS 能保证最短路径，这是它对比 DFS 的最大优势。

参数说明：这两个函数都只接受 problem 一个参数，不涉及启发式。它们的返回值和 SearchAgent 的预期一致，是一个 action 字符串组成的列表。

3.3 UCS：把队列换成按累计代价排序的优先队列

UCS 解决的问题是：当每一步的代价不再恒等于 1，BFS 的逐层扩展就失效了。UCS 把队列换成优先队列，每次弹出累计代价最小的状态：

def uniformCostSearch(problem): frontier = util.PriorityQueue() frontier.push((problem.getStartState(), [], 0), 0) visited = set() while not frontier.isEmpty(): state, path, cost = frontier.pop() if problem.isGoalState(state): return path if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): if nextState not in visited: newCost = cost + stepCost frontier.push((nextState, path + [action], newCost), newCost) return []

逻辑说明：PriorityQueue 的 push 接收两个参数，第二个是优先级，这里直接传累计代价。每次弹出的都是当前 frontier 里代价最小的状态，等价于把搜索过程按代价从低到高展开。第一次弹出目标状态时，返回值就是最优路径。

参数说明：visited 的存在让算法不会重复扩展已经处理过的状态。注意旧条目留在队列里没关系，因为它们弹出 时会因为state in visited被跳过，不会影响正确性。

3.4 A*：在 UCS 上叠加启发式引导方向

A* 的代码只比 UCS 多一行：push 时的优先级从纯代价改成代加启发式。

def aStarSearch(problem, heuristic=nullHeuristic): frontier = util.PriorityQueue() start = problem.getStartState() frontier.push((start, [], 0), heuristic(start, problem)) visited = set() while not frontier.isEmpty(): state, path, cost = frontier.pop() if problem.isGoalState(state): return path if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): if nextState not in visited: newCost = cost + stepCost priority = newCost + heuristic(nextState, problem) frontier.push((nextState, path + [action], newCost), priority) return []

逻辑说明：priority = newCost + heuristic(nextState, problem)，前一半是已付出的代价，后一半是对剩余代价的估计，两者相加是对总代价的预估。启发式越接近真实剩余代价，搜索越「聪明」，扩展的无关节点越少。

参数说明：heuristic是一个接收 (state, problem) 并返回数字的函数。nullHeuristic恒返回 0，所以不传启发式时 A* 退化成 UCS。注意启发式必须可采纳——估计值不能超过真实剩余代价——否则 A* 找到的路径不保证最优。

提示：调试启发式时，先把heuristic换成nullHeuristic跑一遍，再把自定义的换上，对比扩展节点数。扩展节点数变少了，说明启发式在起作用；变多了，说明估计值不可采纳，A* 被带偏了。

3.5 同一个迷宫上的实测对比

在 bigMaze 布局上跑这四个算法，路径长度和扩展节点数差异很明显。以我本地跑出来的数据为参考（不同版本布局数据略有出入）：

这个对比非常有说服力：BFS 和 A* 都能找到最短路径，但 A* 的扩展节点少了近三成。在实际项目中，节点数直接对应内存和时间，这也是为什么真实路径规划场景几乎不用纯 BFS，而是用 A* 及其变体。

4. 高级问题进阶：Corners 和 Food 场景里的状态设计与启发式

前四关是热身，Corners 问题开始才是真正考验状态设计能力的地方。这里的目标从「到达一个点」变成「遍历一组点」，状态空间一下子复杂起来。

4.1 CornersProblem：目标从单点变成四个角

Corners 问题的难点不在算法，而在状态定义。吃完四个角意味着 Pacman 有一组「已完成目标」的信息要携带。如果状态还只用坐标表示，搜索会丢失关键信息：从同一个位置出发，可能已经吃掉两个角，也可能一个都没吃，这两种情况不能混为一个状态。

解决方案是把状态扩成((x, y), visitedCorners)，visitedCorners 记录已经到达过的角落。关键是 visitedCorners 也要塞进状态里，而不是做成全局变量——搜索树里每个分支的访问历史不同，全局变量会让不同分支互相污染。

def isGoalState(self, state): x, y = state[0] visitedCorners = state[1] return len(visitedCorners) == 4 def getSuccessors(self, state): successors = [] x, y = state[0] visitedCorners = state[1] for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: dx, dy = Actions.directionToVector(action) nextx, nexty = int(x + dx), int(y + dy) if not self.walls[nextx][nexty]: nextVisited = set(visitedCorners) if (nextx, nexty) in self.corners: nextVisited.add((nextx, nexty)) successors.append(((nextx, nexty), tuple(sorted(nextVisited)), action, 1)) return successors

逻辑说明：isGoalState 检查 visitedCorners 的个数是否达到 4；getSuccessors 里每次移动后判断新位置是否在四个角之一，在的话就把该角加入集合。注意tuple(sorted(nextVisited))，把集合转成排序后的元组，是为了让状态可哈希，这也呼应了第 2 章说的不可变状态要求。

参数说明：self.corners是 layout 里四个角的坐标列表；Directions.NORTH等是常量字符串，Actions.directionToVector 负责把方向映射成坐标增量。getSuccessors 返回的元组是(nextState, action, stepCost)，stepCost 这里写死为 1。

4.2 cornersHeuristic：曼哈顿距离组合出来的可采纳启发式

Corners 场景要找最短路径遍历四个角，一个自然的想法是用曼哈顿距离组合出现状下的剩余代价。最简版本是当前位置到最近未访问角的距离，这样估计明显偏乐观，但满足可采纳性。

实际效果更好的做法是：不仅考虑当前点到最近角的距离，还要考虑这些角彼此之间的连通代价。我的做法是取两个值的较大者：当前点到最近未访问角的曼哈顿距离，以及剩余未访问角彼此之间的最短连接距离的某种近似。取 max 是为了保住可采纳性，因为启发式只要求不超过真实代价，偏小的估算总是安全的。

def cornersHeuristic(state, problem): corners = problem.corners x, y = state[0] visited = state[1] unvisited = [c for c in corners if c not in visited] if not unvisited: return 0 return min(manhattanDistance((x, y), c) for c in unvisited)

逻辑说明：这个版本只考虑第一步——到最近未访问角的距离。真实方案里通常会再加一层「剩余角之间的最小连接」，比如把剩余角按曼哈顿距离贪心串成一条链，把链总长的一部分并入估计值。加这一层后扩展节点数会显著下降，但必须验证合并后的值仍然不超过真实代价。

参数说明：manhattanDistance接收两个坐标元组，返回abs(x1-x2)+abs(y1-y2)，在 Pacman 项目里它默认忽略墙的存在，所以一定是真实步数的下界，这保证了可采纳性。

4.3 FoodProblem：状态包含食物集合，搜索空间指数增长

Food 问题比 Corners 更狠。Corners 只需要记四个角的状态，Food 场景的地图里有几十个豆子，每个豆子都可能被吃掉或没被吃掉，状态组合数指数爆炸。FoodSearchProblem 的状态是(position, foodGrid)，foodGrid 里记录了当前哪些位置还有豆子。

给 Food 写启发式是最容易翻车的地方。一个合格的可采纳启发式思路是：从当前位置出发，至少要走一段路才能抵达某个剩余豆子；吃完所有豆子还需要在豆子之间移动。可以用剩余豆子的最小生成树（MST）总长作为下界估计，因为无论怎么走，要经过所有剩余豆子，路径长度不会小于连接这些点的最小生成树长度。

def foodHeuristic(state, problem): position, foodGrid = state foods = foodGrid.asList() if not foods: return 0 def md(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1]) h = 0 for f in foods: h = max(h, md(position, f)) return h

逻辑说明：这个实现只用当前位置到最远豆子的距离做估计，是最保守的版本，可采纳但偏弱。我一般会在h = 0附近再加一层：对剩余豆子集合构造带权完全图，边权是曼哈顿距离，求最小生成树总长，把「当前点到最近豆子距离 + MST 总长」和当前版本取 max。这样估计更紧，但依然保持可采纳。

参数说明：foodGrid.asList()返回当前剩余豆子的坐标列表。md是局部的曼哈顿距离函数。注意 foodHeuristic 的 state 结构与 Corners 不同，它的第一个元素是位置，第二个是食物网格，写自定义启发式时一定要先确认 state 的结构，否则就是在盲猜。

4.4 suboptimalSearch：什么时候可以放弃最优解

Food 场景规模一大，A* 也很难在有限时间内找到严格最优路径。课程里有个子问题专门允许你返回一条非最短但足够好的路径，这种「差不多得了」的思路在实际工程里很常见：路径规划第一优先级是别撞墙、能到达，其次才是绕路少。我的做法是每次从当前位置贪心选择最近的豆子走过去，吃完再重新计算。这种方式扩展节点数极少，路径长度比最优长一些，但胜在快。

5. 运行指南与避坑记录：从 Python 2 到 tkinter 的五个深坑

代码看懂了，下一步是把项目跑起来。这个项目年代比较早，运行环境有不少暗坑，我把最常见的几个问题按「现象 → 原因 → 解决」整理出来，照着排查基本能一次通过。

5.1 跑起来的三种方式

# 图形界面，肉眼观察搜索路径 python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs # 指定 A* 和曼哈顿启发式 python pacman.py -l bigMaze -p SearchAgent -a fn=astar, heuristic=manhattanHeuristic # 静默模式，不开图形窗口，适合调试 python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs --frameTime 0 -q # 跑自动评测中的第一道题 python autograder.py -q q1

逻辑说明：--frameTime 0把每帧间隔设为 0，让它以最快速度跑完；-q关闭图形界面，只输出最终统计信息。自动评测是验证改动的唯一标准，本地手动跑通不代表评分能过，因为 autograder 会检查路径代价和启发式可采纳性。

注意：autograder 默认按 Python 2 语法解析代码。如果你用 Python 3 跑，看到print相关语法错误，优先考虑版本兼容问题，而不是怀疑代码写错了。

5.2 高频踩坑记录

坑一：Python 3 下直接报SyntaxError: invalid syntax。原因是项目底子是 Python 2 写的，print还是语句不是函数。解决：要么安装 Python 2 环境，要么全局把print "xxx"替换成print("xxx")。我一般把 autograder 也一并转成 Python 3 语法，方便统一调试。

坑二：图形窗口打开后秒退，或者直接不显示。原因多半是系统里没有 tkinter 库，或者当前环境不支持图形界面。解决：在本地桌面环境安装 python3-tk 再重试；如果用的是远程服务器，直接走--frameTime 0 -q的静默模式，完全不需要图形界面。

坑三：搜索卡住，几分钟不结束。这个现象基本可以断定是状态哈希出了问题。比如把状态里的坐标用 list 保存，list 不可哈希，visited set 永远判重失败，同一批状态被无限次重新扩展。解决：所有进 visited 的状态一律转成 tuple 或 frozenset，我在第 4 章的 Corners 代码里特意用了tuple(sorted(nextVisited))，就是防这个。

坑四：DFS 跑出来的路径明显在绕远路，甚至能看到回头路。原因是很多简化的 DFS 实现里，在 push 时就标记 visited，导致某些分支被过早剪掉，路径质量更差。解决：统一在 pop 时判重，让 DFS 先把一条路探索到底，再回头探索其他分支。这样能保证 DFS 至少返回一条可达路径，虽然不一定最短。

坑五：自定义启发式之后，A* 返回的路径不是最优的。原因是启发式不可采纳，估计值高于真实剩余代价。解决：验证「当前点到目标的最短距离」和「启发式返回值」的大小关系，确保前者永远不小于后者。最简单的手法是对多个不同估计取 max，得到的新函数通常更容易保持可采纳。

5.3 验证不想玄学：用 autograder 和自定义日志

跑 autograder 并不是只看总分。我习惯在执行时加一个统计扩展节点数的计数器，每 pop 一个状态就加一，终局打印出来。同一个布局下比较 BFS 和 A* 的扩展节点数，如果 A* 节点数反而更多，那启发式大概率有问题。autograder 跑完会明确指出哪道题最优性失败，那里就是启发式返回错误估计的位置，可以先单独打印每次的 estimate 和真实距离，比对几组数据就能定位到具体逻辑。

6. 二次开发思路：把搜索算法套到自己的场景里

这个项目的接口设计有个很实用的特点：搜索算法不关心你是迷宫还是别的什么图，只要你实现四个方法，四个搜索函数直接复用。这一章聊点改造技巧。

6.1 换地图：layout 文件就是你的实验场

layouts 目录下的迷宫是纯文本，%表示墙，空格表示可走路径，P是吃豆人起点。直接复制一个文件改几行，就能造出一个新迷宫来验证你的启发式。我把 map 尺寸改大、把豆子位置摆出奇怪的形状，专门用来测试启发式会不会在某些布局下崩掉。这个操作零成本，却比在固定地图上调参更能暴露问题。

class MyProblem: def __init__(self, start, goal, walls): self.start = start self.goal = goal self.walls = walls def getStartState(self): return self.start def isGoalState(self, state): return state == self.goal def getSuccessors(self, state): successors = [] # 遍历四个方向，返回 (nextState, action, stepCost) return successors def getCostOfActions(self, actions): return len(actions)

逻辑说明：这个自定义 Problem 骨架直接扔进 search.aStarSearch 就能用，只要你把 getSuccessors 按实际场景填完整。参数说明：walls只是一个示例字段，实际场景里可能换成图、网格或者导航数据，只要保证四个接口语义正确即可。

这套东西最值得带走的经验是：改完代码别只在一个地图上跑，多换几个布局，顺手把 autograder 全量跑一遍。我第一次改 foodHeuristic 时，只在给定布局下调得飞快，结果 autograder 随机布局一跑就挂，原因就是我针对固定布局过拟合了。从那以后我每次改完都强制走一遍全量评测，换三个不同 layout 各跑一次。希望帮到你。

本文还有配套的精品资源，点击获取