简介伯克利大学AI吃豆人项目是探索搜索算法与游戏AI的经典实战这份配套解决方案面向具备Python基础的中级学习者也适合进修人工智能课程或准备算法面试的开发者。压缩包共23个文件以20个Python源码文件为主体覆盖游戏环境、图形显示、搜索代理、评分测试等核心模块并有说明文档便于快速上手整体仅67KB已有564人学习下载。源码实现了宽度优先搜索、深度优先搜索、A星搜索、迪杰斯特拉算法等基础搜索算法其中宽度优先搜索可定位最近食物或幽灵A星通过曼哈顿距离等启发函数高效寻路迪杰斯特拉用于全局最短路径规划。进阶部分引入最小最大搜索与阿尔法贝塔剪枝应对多幽灵对抗并用Q学习演示强化学习落地配套的自动评分与测试模块可一键执行便于随改随测直观验证算法效果。从幽灵追踪到路径规划模块化组织清晰代码直给既能辅助复盘原版作业也能迁移到其他状态空间搜索项目中是一份实用的AI实战参考。1. AI-Pacman项目从游戏里学透Python搜索算法我第一次在 AI-Pacman 搜索项目里跑通代码时最大的感受是原来用 Python 写的搜索算法不只是一堆教科书伪代码而是真的能让吃豆人在迷宫里自己找路、吃豆、绕开鬼。这套作业源自某高校人工智能导论课程的经典题目完整覆盖 DFS、BFS、UCS、A* 四种搜索算法以及启发式函数设计和自定义搜索问题的实现。适合两类人正在学搜索算法、想找一个能跑起来还能可视化验证的 Python 练手项目的人以及想快速回顾 AI 搜索经典实现、准备面试或做二次开发的工程师。整份资源代码量不大但分层非常讲究。2. 项目架构与代码地图从游戏状态到搜索框架这套项目的代码量不算大但信息密度很高。我拆它的时候没有从 search.py 的算法开始读而是先看了一遍 game.py 和 util.py 的接口再回到 searchAgents.py 的 Problem 定义最后才去看算法本体。这个顺序能少走很多弯路。2.1 目录结构与文件职责解压项目之后核心文件的职责划分非常清晰一眼能看出哪些文件是给你改的哪些是运行环境自带的文件职责是否要改search.pyDFS、BFS、UCS、A* 四种搜索算法的实现入口要改searchAgents.pySearchAgent、CornersProblem、启发式函数的实现要改pacman.py游戏主循环、命令行参数解析、游戏场景搭建不用改game.pyGameState、Agent、动作、状态转移的底层定义不用改util.pyStack、Queue、PriorityQueue 等数据结构实现不用改但要读懂graphicsDisplay.py图形化渲染把搜索路径实时画出来不用改layout/迷宫布局文件如 tinyMaze.lay、mediumMaze.lay可自定义search.py 和 searchAgents.py 是核心功课所在。前者写通用搜索算法后者写特定场景的 Problem 定义和启发式函数。剩下文件都是支撑框架改动它们的需求很低但读懂它们的接口对二次开发帮助很大。layout/ 目录下的 .lay 文件同样值得关注。每个文件用纯文本描述一张地图%表示墙、.表示豆子、P表示吃豆人起始位置。想造一个自己的测试场景直接复制一个 .lay 文件修改命令行 -l 换成新文件名就能加载。这是二次开发时很实用的抓手不用动任何 Python 代码就能生成新的搜索问题。2.2 游戏状态与SearchProblem抽象game.py 里的 GameState 把吃豆人的坐标、剩余豆子、鬼的位置、分数全部打包在一个对象里。但搜索算法不直接碰这个对象而是通过 SearchProblem 这个抽象接口来访问。这套设计的精妙之处在于搜索引擎永远只回答“从状态 A 怎么走到状态 B”完全不用管游戏里的鬼怎么运动、分数怎么算。class SearchProblem: def getStartState(self): # 返回搜索的初始状态吃豆人一开始站在哪个格子 util.raiseNotDefined() def isGoalState(self, state): # 判断传入的 state 是否是目标状态是则搜索结束 util.raiseNotDefined() def getSuccessors(self, state): # 返回 [(nextState, action, stepCost)] 三元组的列表 util.raiseNotDefined() def getCostOfActions(self, actions): # 给一串动作序列计算总代价用于评估路径开销 util.raiseNotDefined()这个接口一共四个方法。getStartState 告诉搜索从哪里开始isGoalState 判断终点getSuccessors 展开相邻状态每次返回后继状态、触发动作、单步代价三样东西getCostOfActions 是给外部评分用的搜索过程中不太会被频繁调用但测试框架依赖它判断返回的路径是否符合预期。只要实现这套接口搜索算法就是通用的。迷宫寻路是一个 Problem收集四个角落的豆子也可以做成另一个 Problem算法代码完全复用不需要动一行。这是整个项目最值得学习的设计思路。2.3 数据结构选型Stack与Queue如何决定搜索行为util.py 里实现了几种基础数据结构它们的差异直接决定了搜索算法的行为走向。class Stack: def __init__(self): self.list [] def push(self, item): self.list.append(item) def pop(self): return self.list.pop() def isEmpty(self): return len(self.list) 0 class Queue: def __init__(self): self.list [] def push(self, item): self.list.insert(0, item) def pop(self): return self.list.pop() def isEmpty(self): return len(self.list) 0Stack 用 list 的 append 和 pop后进先出Queue 用 insert(0, ...) 配合 pop()先进先出。DFS 用 Stack最新加入的节点最先被展开搜索会一头扎进一条分支直到走不动才回头BFS 用 Queue按层推进第一次遇到目标节点时找到的就是最短路径。PriorityQueue 和 PriorityQueueWithFunction 是给 UCS 和 A* 用的。前者 push 时手动传 (item, priority) 二元组后者传入一个计算优先级的函数push 时自动算出优先级。内部实现都是维护一个按优先级排序的列表每次插入做线性扫描。在这类地图规模的问题上绰绰有余如果二次开发要处理百万级节点的搜索再考虑换成堆结构。3. 核心模块拆解从DFS到UCS的搜索算法实现3.1 DFS栈驱动的深度优先搜索def depthFirstSearch(problem): from util import Stack frontier Stack() startState problem.getStartState() frontier.push((startState, [], 0)) visited set() while not frontier.isEmpty(): state, actions, cost frontier.pop() if problem.isGoalState(state): return actions if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): frontier.push((nextState, actions [action], cost stepCost)) return []栈里存的是三元组当前状态、从起点到当前状态的动作序列、累计代价。每次弹出栈顶节点先判目标再查重然后展开后继状态压入栈中。visited 在出栈时标记这是这套代码里最容易被忽视但也是关键的一处设计。如果在入栈时就标记 visitedDFS 会遇到一种经典问题某个状态先被一条较长路径访问到并标记之后更短的路径因为这个标记被跳过最终返回的路径就不是最短的。改成出栈时标记虽然可能让同一个状态被压入栈多次稍微增加内存开销但保证了路径正确性。很多人在这个项目里翻车就是没注意到标记时机。3.2 BFS换一个数据结构就是另一种算法def breadthFirstSearch(problem): from util import Queue frontier Queue() frontier.push((problem.getStartState(), [], 0)) visited set() while not frontier.isEmpty(): state, actions, cost frontier.pop() if problem.isGoalState(state): return actions if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): frontier.push((nextState, actions [action], cost stepCost)) return []BFS 和 DFS 的代码几乎一模一样只把 Stack 换成了 Queue。但行为差异是本质性的Queue 先进先出搜索一层一层往外推保证在单位代价的地图上第一次到达目标节点时路径一定最短。在这个吃豆人项目里普通迷宫寻路的每一步移动代价都是 1所以 BFS 是解决 mediumMaze、bigMaze 这类静态迷宫寻路的稳妥算法。有一个容易被忽视的细节actions 列表这里用的是actions [action]每次展开新节点都会生成一个新列表旧列表留在内存里等垃圾回收。路径短时无所谓但 A* 跑超大迷宫时大量节点展开会让内存开销明显上升。想优化的话可以改成动作链表加回溯不过课程作业场景里没必要。3.3 UCS把累计代价写进优先级def uniformCostSearch(problem): from util import PriorityQueueWithFunction def priorityFn(item): state, actions, cost item return cost frontier PriorityQueueWithFunction(priorityFn) frontier.push((problem.getStartState(), [], 0)) visited set() while not frontier.isEmpty(): state, actions, cost frontier.pop() if problem.isGoalState(state): return actions if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): frontier.push((nextState, actions [action], cost stepCost)) return []UCS 把优先队列的优先级设成累计代价 cost每次弹出的都是当前已知代价最小的节点。在地图上如果所有边的代价都一样UCS 退化成 BFS如果边的代价不同比如某些格子移动代价更高UCS 能找到真正的代价最小路径而 BFS 只保证步数最少。到这里会发现四种算法共享同一个模板初始化前沿、循环弹出、判目标、访问标记、展开后继。差别只有前沿数据结构和优先级计算方式。这就是通用图搜索框架的骨架理解了这个模板后面看 A* 就只是多一个启发式函数的事。4. A*搜索与启发式函数吃豆人怎么“看得见”终点4.1 A*在UCS基础上加一个启发式评估def aStarSearch(problem, heuristicnullHeuristic): from util import PriorityQueueWithFunction def priorityFn(item): state, actions, cost item return cost heuristic(state, problem) frontier PriorityQueueWithFunction(priorityFn) frontier.push((problem.getStartState(), [], 0)) visited set() while not frontier.isEmpty(): state, actions, cost frontier.pop() if problem.isGoalState(state): return actions if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): frontier.push((nextState, actions [action], cost stepCost)) return []A* 和 UCS 的结构完全同构唯一区别就是优先级计算从 cost 变成了cost heuristic(state, problem)。这里的 heuristic 接收当前 state 和 problem返回从当前状态到目标代价的估计值 h(n)加上已经花费的 g(n) 就是 f(n)。A* 的搜索质量完全取决于 h(n) 是否可采纳。nullHeuristic 是项目里预置的“恒返回 0”的启发式函数把它传给 aStarSearchA* 就会退化成 UCS。这个函数在调试启发式时是很好的基线基准。跑任务时经常用的 manhattanHeuristic是吃豆人当前坐标到目标坐标的曼哈顿距离也就是网格横向纵向距离之和不考虑斜线。4.2 自定义ProblemCornersProblem的完整实现第四个编程任务要求吃豆人访问地图上四个角落上的豆子。这个任务不能直接用“当前位置等于目标位置”来定义目标因为四个角落都要访问顺序还不固定。核心做法是把状态扩展成“坐标 角落访问记录”的复合结构。class CornersProblem(search.SearchProblem): def __init__(self, startingGameState): self.walls startingGameState.getWalls() self.startingPosition startingGameState.getPacmanPosition() top self.walls.height - 2 right self.walls.width - 2 self.corners ((1, 1), (1, top), (right, 1), (right, top)) self.cornersVisited [False, False, False, False] def getStartState(self): return (self.startingPosition, tuple(self.cornersVisited)) def isGoalState(self, state): position, visited state return all(visited) def getSuccessors(self, state): position, visited state successors [] for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: x, y position dx, dy Actions.directionToVector(action) nextx, nexty int(x dx), int(y dy) if not self.walls[nextx][nexty]: nextVisited list(visited) if (nextx, nexty) in self.corners: index self.corners.index((nextx, nexty)) nextVisited[index] True nextState (nextx, nexty), tuple(nextVisited) successors.append((nextState, action, 1)) return successorsgetStartState 返回的第二个元素强制转成 tuple这一步极其关键。因为 state 之后会被放进 visited 集合里判重而 list 是不可哈希的如果不转 tuple运行时会直接报 unhashable type 错误这个坑在后文还会展开讲。isGoalState 用 all(visited) 判断四个角落是否全部访问过。getSuccessors 里遍历四个方向用 Actions.directionToVector 把动作转成坐标增量检查下一步是否撞墙然后生成后继状态。如果走进了一个角落就更新 visited 里对应的下标为 True。每步代价固定为 1所以这个 Problem 是一个无权图搜索问题A* 配合好的启发式能大幅减少展开节点数。searchAgents.py 顶部已经统一导入了 Directions 和 Actions所以类方法里可以直接使用。4.3 启发式函数怎么保证A*不翻车def cornersHeuristic(state, problem): position, visited state corners problem.corners unvisited [c for i, c in enumerate(corners) if not visited[i]] if not unvisited: return 0 minDist min( abs(position[0] - c[0]) abs(position[1] - c[1]) for c in unvisited ) return minDist这个实现取“当前位置到最近未访问角落的曼哈顿距离”作为启发式。它永远不大于真实剩余的代价所以是可采纳的A* 使用它能保证返回最优路径。缺点是它过于保守只估计了前往其中一个角的最短代价完全没考虑后续还要覆盖其他角所以搜索展开节点数偏多。想让启发式更紧又不牺牲可采纳性一种常见做法是先求当前位置到所有未访问角落各自的最短曼哈顿距离取其中的最大值再根据未访问角落之间的相对位置估算一条覆盖链的代价取一个不超过真实最短路径的上界。调启发式时最忌讳“感觉差不多就行”每改一次都要对比最终路径长度和展开节点数。路径长度变长了说明启发式低估被打破A* 不再保证最优。下一章会讲具体怎么排查这类问题。5. 运行测试与常见问题排查从命令行到可视化调优5.1 环境准备与运行指南项目不需要安装任何第三方依赖所有数据结构都在 util.py 里手写实现只要能跑 Python 3 就能直接运行。装好 Python 后进入项目目录执行以下命令跑 DFS 搜 tinyMazepython pacman.py -l tinyMaze -p SearchAgent -a fndfs命令行参数里 -l 指定布局文件-p 指定代理类型-a 传给代理的参数。SearchAgent 在内部会按名字从 search 模块里找到对应的函数因此新增搜索算法后只要函数名对得上命令行直接就支持调用。更多场景的跑法# BFS 跑标准迷宫 python pacman.py -l mediumMaze -p SearchAgent -a fnbfs # UCS 跑统一代价搜索 python pacman.py -l mediumMaze -p SearchAgent -a fnucs # A* 配曼哈顿启发式 python pacman.py -l mediumMaze -p SearchAgent -a fnastar, heuristicmanhattanHeuristic # 跑四个角落收集任务 python pacman.py -l mediumCorners -p CornersProblem -a fnastar, heuristiccornersHeuristic如果不想开图形界面只想快速验证算法正确性用 autograder.py 评分脚本python autograder.py -q q2-q 参数控制跑哪道题q1 对应 DFSq2 对应 BFSq3 对应 UCSq4 对应 A*q5 对应 CornersProblem 和启发式函数。它会自动加载测试用例比对路径代价和展开节点数给出通过与否的结论。5.2 常见问题与踩坑记录这一节把我在跑这套代码时遇到的几个高频问题整理出来每条都按现象、原因、解决展开。现象1DFS 找到的路径比 BFS 长甚至明显绕路。 原因visited 集合在节点入栈时就标记了一个状态被先到达它的长路径“占位”后面更短的路径因为状态已访问而被跳过。 解决把 visited 标记逻辑放到 pop 出栈之后执行即先查重、后标记、再展开后继。虽然可能让一个状态被重复压栈多次但在 DFS 里这是保证能搜出合理路径的常用写法。现象2跑 CornersProblem 时直接抛 TypeError: unhashable type: list。 原因state 里带了 list 类型的 visited而 state 要被放进 set() 中判重list 不可哈希。 解决状态里所有可变容器都换成 tuplegetStartState 和 getSuccessors 里统一把 visited 转成 tuple 后再放进 state。这是这个项目里出现频率最高的报错。现象3A* 跑起来展开节点数量巨大比 BFS 还多。 原因启发式函数返回了不可接受的估计或者代码里写成了固定返回 0 的 nullHeuristic导致 A* 退化成 UCS。 解决先记录 nullHeuristic 的展开节点数作为基线再替换成自己的启发式对比展开数量是否下降。同时检查最终路径长度有没有变长变长说明启发式不满足可采纳性。现象4图形窗口一闪而过看不到搜索过程。 原因SearchAgent 在游戏开始前已经把整条路径搜完游戏只是按结果播放路径为空时看起来就像没运行。 解决看终端输出的路径长度和展开节点数确认搜索确实执行了也可以手动在 SearchAgent 里把搜索得到的动作序列打印出来。想直观观察搜索过程可以临时在 search.py 里加打印。5.3 可视化调试与数据对比技巧纯看图形界面很难判断算法写没写对我更习惯把搜索过程留下的数据当成主要依据。比如在搜索函数里临时加两个统计变量统计展开节点数和最终路径代价然后在同一张地图上对比不同算法的表现。mediumMaze 上 BFS 和 A*曼哈顿启发式能找到相同代价的路径但 A* 展开的节点数通常少一个量级。这个数字对比比任何断言都更能说明启发式的价值。调整启发式时我一般同时记录四个值路径代价、展开节点数、启发式是否可采纳的自动校验结果、运行时间。layout 目录下的 .lay 文件也可以自己改把墙和豆子位置改一改就能造出新的测试场景。自定义地图时要注意布局文件第一行的空格会被忽略%表示墙.表示豆子P表示吃豆人初始位置改完后用同一套搜索命令跑就能验证算法在新场景下是否仍然成立。提示调试搜索算法时不要只盯着路径长短展开节点数才是评价搜索效率的核心指标路径代价则是评价正确性的核心指标两个值要同时看。6. 二次开发把吃豆人改造成自己的搜索算法试验台6.1 新增自定义Problem想验证一种新搜索策略最快的方式是复用一个已有的 Problem。比如在小范围内验证 A* 的加权变体可以直接在 searchAgents.py 里新增一个类继承 SearchProblem然后只重写 getStartState、isGoalState、getSuccessors、getCostOfActions 四个方法算法代码一行都不用动。比如把目标改成“收集地图上所有豆子”状态就要带上剩余豆子的坐标集合getSuccessors 里每走一步就移除被吃掉的豆子isGoalState 判断剩余豆子是否为空。这就是 FoodSearchProblem 的核心思路。把它改造成自己的问题定义时唯一要留意的是状态必须可哈希坐标和剩余豆子都存成 tuple。这种扩展方式之所以成立是因为这个项目的架构把“搜索算法”和“问题定义”彻底解耦了。理解了这一点就可以放心往 search.py 里加算法而不必担心弄坏游戏引擎。6.2 用参数化启发式跑实验想对比不同启发式对搜索效率的影响不用改 aStarSearch 本体。可以写一个带权启发式的包装函数通过参数传入权重系数在命令行里就能批量做实验。比如把 f(n) g(n) 1.5 * h(n)观察路径代价和展开节点数的此消彼长这是理解“可采纳 vs 更紧”这对矛盾最直观的方式。从那以后我每次改搜索算法都强制自己走一遍“跑测试、看展开节点数、对比路径代价”三步流程。这一套下来大部分隐藏的搜索bug都会现出原形。希望这些经验对你跑通这个项目有帮助。本文还有配套的精品资源点击获取 
长河君 · 2026/10/18 16:57:08 · 阅读 1.2k AI吃豆人项目：用Python实战BFS、DFS、UCS与A*搜索算法
简介伯克利大学AI吃豆人项目是探索搜索算法与游戏AI的经典实战这份配套解决方案面向具备Python基础的中级学习者也适合进修人工智能课程或准备算法面试的开发者。压缩包共23个文件以20个Python源码文件为主体覆盖游戏环境、图形显示、搜索代理、评分测试等核心模块并有说明文档便于快速上手整体仅67KB已有564人学习下载。源码实现了宽度优先搜索、深度优先搜索、A星搜索、迪杰斯特拉算法等基础搜索算法其中宽度优先搜索可定位最近食物或幽灵A星通过曼哈顿距离等启发函数高效寻路迪杰斯特拉用于全局最短路径规划。进阶部分引入最小最大搜索与阿尔法贝塔剪枝应对多幽灵对抗并用Q学习演示强化学习落地配套的自动评分与测试模块可一键执行便于随改随测直观验证算法效果。从幽灵追踪到路径规划模块化组织清晰代码直给既能辅助复盘原版作业也能迁移到其他状态空间搜索项目中是一份实用的AI实战参考。1. AI-Pacman项目从游戏里学透Python搜索算法我第一次在 AI-Pacman 搜索项目里跑通代码时最大的感受是原来用 Python 写的搜索算法不只是一堆教科书伪代码而是真的能让吃豆人在迷宫里自己找路、吃豆、绕开鬼。这套作业源自某高校人工智能导论课程的经典题目完整覆盖 DFS、BFS、UCS、A* 四种搜索算法以及启发式函数设计和自定义搜索问题的实现。适合两类人正在学搜索算法、想找一个能跑起来还能可视化验证的 Python 练手项目的人以及想快速回顾 AI 搜索经典实现、准备面试或做二次开发的工程师。整份资源代码量不大但分层非常讲究。2. 项目架构与代码地图从游戏状态到搜索框架这套项目的代码量不算大但信息密度很高。我拆它的时候没有从 search.py 的算法开始读而是先看了一遍 game.py 和 util.py 的接口再回到 searchAgents.py 的 Problem 定义最后才去看算法本体。这个顺序能少走很多弯路。2.1 目录结构与文件职责解压项目之后核心文件的职责划分非常清晰一眼能看出哪些文件是给你改的哪些是运行环境自带的文件职责是否要改search.pyDFS、BFS、UCS、A* 四种搜索算法的实现入口要改searchAgents.pySearchAgent、CornersProblem、启发式函数的实现要改pacman.py游戏主循环、命令行参数解析、游戏场景搭建不用改game.pyGameState、Agent、动作、状态转移的底层定义不用改util.pyStack、Queue、PriorityQueue 等数据结构实现不用改但要读懂graphicsDisplay.py图形化渲染把搜索路径实时画出来不用改layout/迷宫布局文件如 tinyMaze.lay、mediumMaze.lay可自定义search.py 和 searchAgents.py 是核心功课所在。前者写通用搜索算法后者写特定场景的 Problem 定义和启发式函数。剩下文件都是支撑框架改动它们的需求很低但读懂它们的接口对二次开发帮助很大。layout/ 目录下的 .lay 文件同样值得关注。每个文件用纯文本描述一张地图%表示墙、.表示豆子、P表示吃豆人起始位置。想造一个自己的测试场景直接复制一个 .lay 文件修改命令行 -l 换成新文件名就能加载。这是二次开发时很实用的抓手不用动任何 Python 代码就能生成新的搜索问题。2.2 游戏状态与SearchProblem抽象game.py 里的 GameState 把吃豆人的坐标、剩余豆子、鬼的位置、分数全部打包在一个对象里。但搜索算法不直接碰这个对象而是通过 SearchProblem 这个抽象接口来访问。这套设计的精妙之处在于搜索引擎永远只回答“从状态 A 怎么走到状态 B”完全不用管游戏里的鬼怎么运动、分数怎么算。class SearchProblem: def getStartState(self): # 返回搜索的初始状态吃豆人一开始站在哪个格子 util.raiseNotDefined() def isGoalState(self, state): # 判断传入的 state 是否是目标状态是则搜索结束 util.raiseNotDefined() def getSuccessors(self, state): # 返回 [(nextState, action, stepCost)] 三元组的列表 util.raiseNotDefined() def getCostOfActions(self, actions): # 给一串动作序列计算总代价用于评估路径开销 util.raiseNotDefined()这个接口一共四个方法。getStartState 告诉搜索从哪里开始isGoalState 判断终点getSuccessors 展开相邻状态每次返回后继状态、触发动作、单步代价三样东西getCostOfActions 是给外部评分用的搜索过程中不太会被频繁调用但测试框架依赖它判断返回的路径是否符合预期。只要实现这套接口搜索算法就是通用的。迷宫寻路是一个 Problem收集四个角落的豆子也可以做成另一个 Problem算法代码完全复用不需要动一行。这是整个项目最值得学习的设计思路。2.3 数据结构选型Stack与Queue如何决定搜索行为util.py 里实现了几种基础数据结构它们的差异直接决定了搜索算法的行为走向。class Stack: def __init__(self): self.list [] def push(self, item): self.list.append(item) def pop(self): return self.list.pop() def isEmpty(self): return len(self.list) 0 class Queue: def __init__(self): self.list [] def push(self, item): self.list.insert(0, item) def pop(self): return self.list.pop() def isEmpty(self): return len(self.list) 0Stack 用 list 的 append 和 pop后进先出Queue 用 insert(0, ...) 配合 pop()先进先出。DFS 用 Stack最新加入的节点最先被展开搜索会一头扎进一条分支直到走不动才回头BFS 用 Queue按层推进第一次遇到目标节点时找到的就是最短路径。PriorityQueue 和 PriorityQueueWithFunction 是给 UCS 和 A* 用的。前者 push 时手动传 (item, priority) 二元组后者传入一个计算优先级的函数push 时自动算出优先级。内部实现都是维护一个按优先级排序的列表每次插入做线性扫描。在这类地图规模的问题上绰绰有余如果二次开发要处理百万级节点的搜索再考虑换成堆结构。3. 核心模块拆解从DFS到UCS的搜索算法实现3.1 DFS栈驱动的深度优先搜索def depthFirstSearch(problem): from util import Stack frontier Stack() startState problem.getStartState() frontier.push((startState, [], 0)) visited set() while not frontier.isEmpty(): state, actions, cost frontier.pop() if problem.isGoalState(state): return actions if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): frontier.push((nextState, actions [action], cost stepCost)) return []栈里存的是三元组当前状态、从起点到当前状态的动作序列、累计代价。每次弹出栈顶节点先判目标再查重然后展开后继状态压入栈中。visited 在出栈时标记这是这套代码里最容易被忽视但也是关键的一处设计。如果在入栈时就标记 visitedDFS 会遇到一种经典问题某个状态先被一条较长路径访问到并标记之后更短的路径因为这个标记被跳过最终返回的路径就不是最短的。改成出栈时标记虽然可能让同一个状态被压入栈多次稍微增加内存开销但保证了路径正确性。很多人在这个项目里翻车就是没注意到标记时机。3.2 BFS换一个数据结构就是另一种算法def breadthFirstSearch(problem): from util import Queue frontier Queue() frontier.push((problem.getStartState(), [], 0)) visited set() while not frontier.isEmpty(): state, actions, cost frontier.pop() if problem.isGoalState(state): return actions if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): frontier.push((nextState, actions [action], cost stepCost)) return []BFS 和 DFS 的代码几乎一模一样只把 Stack 换成了 Queue。但行为差异是本质性的Queue 先进先出搜索一层一层往外推保证在单位代价的地图上第一次到达目标节点时路径一定最短。在这个吃豆人项目里普通迷宫寻路的每一步移动代价都是 1所以 BFS 是解决 mediumMaze、bigMaze 这类静态迷宫寻路的稳妥算法。有一个容易被忽视的细节actions 列表这里用的是actions [action]每次展开新节点都会生成一个新列表旧列表留在内存里等垃圾回收。路径短时无所谓但 A* 跑超大迷宫时大量节点展开会让内存开销明显上升。想优化的话可以改成动作链表加回溯不过课程作业场景里没必要。3.3 UCS把累计代价写进优先级def uniformCostSearch(problem): from util import PriorityQueueWithFunction def priorityFn(item): state, actions, cost item return cost frontier PriorityQueueWithFunction(priorityFn) frontier.push((problem.getStartState(), [], 0)) visited set() while not frontier.isEmpty(): state, actions, cost frontier.pop() if problem.isGoalState(state): return actions if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): frontier.push((nextState, actions [action], cost stepCost)) return []UCS 把优先队列的优先级设成累计代价 cost每次弹出的都是当前已知代价最小的节点。在地图上如果所有边的代价都一样UCS 退化成 BFS如果边的代价不同比如某些格子移动代价更高UCS 能找到真正的代价最小路径而 BFS 只保证步数最少。到这里会发现四种算法共享同一个模板初始化前沿、循环弹出、判目标、访问标记、展开后继。差别只有前沿数据结构和优先级计算方式。这就是通用图搜索框架的骨架理解了这个模板后面看 A* 就只是多一个启发式函数的事。4. A*搜索与启发式函数吃豆人怎么“看得见”终点4.1 A*在UCS基础上加一个启发式评估def aStarSearch(problem, heuristicnullHeuristic): from util import PriorityQueueWithFunction def priorityFn(item): state, actions, cost item return cost heuristic(state, problem) frontier PriorityQueueWithFunction(priorityFn) frontier.push((problem.getStartState(), [], 0)) visited set() while not frontier.isEmpty(): state, actions, cost frontier.pop() if problem.isGoalState(state): return actions if state in visited: continue visited.add(state) for nextState, action, stepCost in problem.getSuccessors(state): frontier.push((nextState, actions [action], cost stepCost)) return []A* 和 UCS 的结构完全同构唯一区别就是优先级计算从 cost 变成了cost heuristic(state, problem)。这里的 heuristic 接收当前 state 和 problem返回从当前状态到目标代价的估计值 h(n)加上已经花费的 g(n) 就是 f(n)。A* 的搜索质量完全取决于 h(n) 是否可采纳。nullHeuristic 是项目里预置的“恒返回 0”的启发式函数把它传给 aStarSearchA* 就会退化成 UCS。这个函数在调试启发式时是很好的基线基准。跑任务时经常用的 manhattanHeuristic是吃豆人当前坐标到目标坐标的曼哈顿距离也就是网格横向纵向距离之和不考虑斜线。4.2 自定义ProblemCornersProblem的完整实现第四个编程任务要求吃豆人访问地图上四个角落上的豆子。这个任务不能直接用“当前位置等于目标位置”来定义目标因为四个角落都要访问顺序还不固定。核心做法是把状态扩展成“坐标 角落访问记录”的复合结构。class CornersProblem(search.SearchProblem): def __init__(self, startingGameState): self.walls startingGameState.getWalls() self.startingPosition startingGameState.getPacmanPosition() top self.walls.height - 2 right self.walls.width - 2 self.corners ((1, 1), (1, top), (right, 1), (right, top)) self.cornersVisited [False, False, False, False] def getStartState(self): return (self.startingPosition, tuple(self.cornersVisited)) def isGoalState(self, state): position, visited state return all(visited) def getSuccessors(self, state): position, visited state successors [] for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: x, y position dx, dy Actions.directionToVector(action) nextx, nexty int(x dx), int(y dy) if not self.walls[nextx][nexty]: nextVisited list(visited) if (nextx, nexty) in self.corners: index self.corners.index((nextx, nexty)) nextVisited[index] True nextState (nextx, nexty), tuple(nextVisited) successors.append((nextState, action, 1)) return successorsgetStartState 返回的第二个元素强制转成 tuple这一步极其关键。因为 state 之后会被放进 visited 集合里判重而 list 是不可哈希的如果不转 tuple运行时会直接报 unhashable type 错误这个坑在后文还会展开讲。isGoalState 用 all(visited) 判断四个角落是否全部访问过。getSuccessors 里遍历四个方向用 Actions.directionToVector 把动作转成坐标增量检查下一步是否撞墙然后生成后继状态。如果走进了一个角落就更新 visited 里对应的下标为 True。每步代价固定为 1所以这个 Problem 是一个无权图搜索问题A* 配合好的启发式能大幅减少展开节点数。searchAgents.py 顶部已经统一导入了 Directions 和 Actions所以类方法里可以直接使用。4.3 启发式函数怎么保证A*不翻车def cornersHeuristic(state, problem): position, visited state corners problem.corners unvisited [c for i, c in enumerate(corners) if not visited[i]] if not unvisited: return 0 minDist min( abs(position[0] - c[0]) abs(position[1] - c[1]) for c in unvisited ) return minDist这个实现取“当前位置到最近未访问角落的曼哈顿距离”作为启发式。它永远不大于真实剩余的代价所以是可采纳的A* 使用它能保证返回最优路径。缺点是它过于保守只估计了前往其中一个角的最短代价完全没考虑后续还要覆盖其他角所以搜索展开节点数偏多。想让启发式更紧又不牺牲可采纳性一种常见做法是先求当前位置到所有未访问角落各自的最短曼哈顿距离取其中的最大值再根据未访问角落之间的相对位置估算一条覆盖链的代价取一个不超过真实最短路径的上界。调启发式时最忌讳“感觉差不多就行”每改一次都要对比最终路径长度和展开节点数。路径长度变长了说明启发式低估被打破A* 不再保证最优。下一章会讲具体怎么排查这类问题。5. 运行测试与常见问题排查从命令行到可视化调优5.1 环境准备与运行指南项目不需要安装任何第三方依赖所有数据结构都在 util.py 里手写实现只要能跑 Python 3 就能直接运行。装好 Python 后进入项目目录执行以下命令跑 DFS 搜 tinyMazepython pacman.py -l tinyMaze -p SearchAgent -a fndfs命令行参数里 -l 指定布局文件-p 指定代理类型-a 传给代理的参数。SearchAgent 在内部会按名字从 search 模块里找到对应的函数因此新增搜索算法后只要函数名对得上命令行直接就支持调用。更多场景的跑法# BFS 跑标准迷宫 python pacman.py -l mediumMaze -p SearchAgent -a fnbfs # UCS 跑统一代价搜索 python pacman.py -l mediumMaze -p SearchAgent -a fnucs # A* 配曼哈顿启发式 python pacman.py -l mediumMaze -p SearchAgent -a fnastar, heuristicmanhattanHeuristic # 跑四个角落收集任务 python pacman.py -l mediumCorners -p CornersProblem -a fnastar, heuristiccornersHeuristic如果不想开图形界面只想快速验证算法正确性用 autograder.py 评分脚本python autograder.py -q q2-q 参数控制跑哪道题q1 对应 DFSq2 对应 BFSq3 对应 UCSq4 对应 A*q5 对应 CornersProblem 和启发式函数。它会自动加载测试用例比对路径代价和展开节点数给出通过与否的结论。5.2 常见问题与踩坑记录这一节把我在跑这套代码时遇到的几个高频问题整理出来每条都按现象、原因、解决展开。现象1DFS 找到的路径比 BFS 长甚至明显绕路。 原因visited 集合在节点入栈时就标记了一个状态被先到达它的长路径“占位”后面更短的路径因为状态已访问而被跳过。 解决把 visited 标记逻辑放到 pop 出栈之后执行即先查重、后标记、再展开后继。虽然可能让一个状态被重复压栈多次但在 DFS 里这是保证能搜出合理路径的常用写法。现象2跑 CornersProblem 时直接抛 TypeError: unhashable type: list。 原因state 里带了 list 类型的 visited而 state 要被放进 set() 中判重list 不可哈希。 解决状态里所有可变容器都换成 tuplegetStartState 和 getSuccessors 里统一把 visited 转成 tuple 后再放进 state。这是这个项目里出现频率最高的报错。现象3A* 跑起来展开节点数量巨大比 BFS 还多。 原因启发式函数返回了不可接受的估计或者代码里写成了固定返回 0 的 nullHeuristic导致 A* 退化成 UCS。 解决先记录 nullHeuristic 的展开节点数作为基线再替换成自己的启发式对比展开数量是否下降。同时检查最终路径长度有没有变长变长说明启发式不满足可采纳性。现象4图形窗口一闪而过看不到搜索过程。 原因SearchAgent 在游戏开始前已经把整条路径搜完游戏只是按结果播放路径为空时看起来就像没运行。 解决看终端输出的路径长度和展开节点数确认搜索确实执行了也可以手动在 SearchAgent 里把搜索得到的动作序列打印出来。想直观观察搜索过程可以临时在 search.py 里加打印。5.3 可视化调试与数据对比技巧纯看图形界面很难判断算法写没写对我更习惯把搜索过程留下的数据当成主要依据。比如在搜索函数里临时加两个统计变量统计展开节点数和最终路径代价然后在同一张地图上对比不同算法的表现。mediumMaze 上 BFS 和 A*曼哈顿启发式能找到相同代价的路径但 A* 展开的节点数通常少一个量级。这个数字对比比任何断言都更能说明启发式的价值。调整启发式时我一般同时记录四个值路径代价、展开节点数、启发式是否可采纳的自动校验结果、运行时间。layout 目录下的 .lay 文件也可以自己改把墙和豆子位置改一改就能造出新的测试场景。自定义地图时要注意布局文件第一行的空格会被忽略%表示墙.表示豆子P表示吃豆人初始位置改完后用同一套搜索命令跑就能验证算法在新场景下是否仍然成立。提示调试搜索算法时不要只盯着路径长短展开节点数才是评价搜索效率的核心指标路径代价则是评价正确性的核心指标两个值要同时看。6. 二次开发把吃豆人改造成自己的搜索算法试验台6.1 新增自定义Problem想验证一种新搜索策略最快的方式是复用一个已有的 Problem。比如在小范围内验证 A* 的加权变体可以直接在 searchAgents.py 里新增一个类继承 SearchProblem然后只重写 getStartState、isGoalState、getSuccessors、getCostOfActions 四个方法算法代码一行都不用动。比如把目标改成“收集地图上所有豆子”状态就要带上剩余豆子的坐标集合getSuccessors 里每走一步就移除被吃掉的豆子isGoalState 判断剩余豆子是否为空。这就是 FoodSearchProblem 的核心思路。把它改造成自己的问题定义时唯一要留意的是状态必须可哈希坐标和剩余豆子都存成 tuple。这种扩展方式之所以成立是因为这个项目的架构把“搜索算法”和“问题定义”彻底解耦了。理解了这一点就可以放心往 search.py 里加算法而不必担心弄坏游戏引擎。6.2 用参数化启发式跑实验想对比不同启发式对搜索效率的影响不用改 aStarSearch 本体。可以写一个带权启发式的包装函数通过参数传入权重系数在命令行里就能批量做实验。比如把 f(n) g(n) 1.5 * h(n)观察路径代价和展开节点数的此消彼长这是理解“可采纳 vs 更紧”这对矛盾最直观的方式。从那以后我每次改搜索算法都强制自己走一遍“跑测试、看展开节点数、对比路径代价”三步流程。这一套下来大部分隐藏的搜索bug都会现出原形。希望这些经验对你跑通这个项目有帮助。本文还有配套的精品资源点击获取