简介一份面向哈工大计算机科学与技术学院学生的《人工智能导论》实验报告聚焦搜索算法与问题表示等核心知识点适合正在学习人工智能基础课程、需要参考实验思路与报告写法的本科生。压缩包为单份Word文档约537KB整体结构清晰从实验背景、方法介绍到结果分析一应俱全便于直接阅读或按需修改。报告围绕深度优先搜索、广度优先搜索、一致代价搜索、A星搜索等搜索算法逐一展开同时覆盖角点问题的表示与启发式、吃掉所有点的启发式、次优搜索等经典问题给出具体分析、解决方法和结果对比。阅读这份报告能够快速理解不同搜索策略的适用场景与优缺点也能借鉴其报告组织方式和实验记录习惯为完成同类人工智能实验提供直接参考。目前已有八百一十八人学习下载是人工智能导论实验值得收藏的实用资料。1. 吃豆人搜索实验一次把教科书算法变成可跑智能体的完整闭环在课堂上把 DFS、BFS、UCS、A* 的定义背熟很容易真正在哈工大人工智能导论实验里拿到 Pacman 项目时很多人第一行代码都写不出来栈换成队列为什么结果还是不对visited 集合到底加在哪这套实验把搜索算法压进一个有墙、有豆子、有幽灵的迷宫世界要求你在 search.py 和 searchAgents.py 里补齐 8 个问题最后用自动评分脚本验证。它不只是人工智能大作业的经典题源更是一份能直接看到算法边界与状态建模的素材。对正在做人工智能入门和复习的人来说这份实验报告的参考价值在于四个搜索算法共用同一套图搜索框架但每个算法的坑都不同后续的 Corners 与 Eating All The Dots 又在提醒你启发式和状态表示往往比算法本身更影响性能。2. 从栈到优先队列DFS、BFS、UCS 在图搜索里的统一写法2.1 先抽象一个通用搜索循环Pacman 项目里所有搜索算法都基于 SearchProblem 抽象getStartState 返回初始状态isGoalState 判断是否到达目标getSuccessors 返回后继状态、动作和单步代价。search.py 里的每个搜索函数接收一个 SearchProblem 实例返回从起点到目标的动作列表。这个接口设计很克制把“怎么搜”和“状态怎么来”完全解耦所以后面 Corners 问题才能复用同一套搜索函数。写实验时如果不理解这个抽象很容易把逻辑写死在 agent 里导致后面的问题全部返工。通用搜索循环可以写成这样def general_search(problem, fringe): if problem.isGoalState(problem.getStartState()): return [] visited set() start (problem.getStartState(), [], 0) fringe.push(start) while not fringe.isEmpty(): state, actions, cost fringe.pop() if state in visited: continue visited.add(state) if problem.isGoalState(state): return actions for successor, action, step_cost in problem.getSuccessors(state): if successor not in visited: fringe.push((successor, actions [action], cost step_cost)) return []逻辑说明这个循环把算法差异压缩到 fringe 的数据结构上。visited 在弹出时标记能保证第一次 pop 到目标时一定是当前搜索树中的最早可达但要注意对于 UCS 来说如果提前把状态加入 visited后续更短路径会被直接丢弃。参数说明actions [action] 会生成新列表避免不同分支互相污染cost 在 DFS/BFS 里用不到但保留对 UCS 优先级有用。实际项目里 SearchAgent 会把问题实例传给算法函数所以这里用 problem.getSuccessors 拿到的是 (nextState, action, cost) 三元组顺序不要搞反否则解出来的路径会错位。2.2 DFS 用栈BFS 用队列UCS 用优先队列实验前三个问题本质上就是选择不同容器DFS 把 Stack 当作 fringe后进先出BFS 用 Queue先进先出UCS 用 PriorityQueue按累计代价排序。项目里 Stack、Queue、PriorityQueue 都定义在 util.py 中搜索函数只需要接受一个带 push/pop 接口的对象。下面这张表是我拆解这份报告时整理的行为差异也是排查“为什么运行结果不对”的第一张对照表算法数据结构扩展顺序目标最优性典型陷阱DFSStack后进先出不保证栈深时递归过深visited 标记太晚导致重复扩展BFSQueue按层单步代价一致时最短若单步代价不同可能不是代价最优UCSPriorityQueue按累计代价单步代价非负时最优同一状态多次入队不判断旧代价会拖慢甚至出错这个表里最容易被忽略的是 UCS 的重复入队问题。第一次找到某状态时不一定是从最优路径找到的如果提前把它加入 visited后面更短路径会被直接丢掉。常见做法是允许同一状态多次入队弹出来时比较已知最小代价只处理代价更小的那条路径或者维护一个 cost_so_far 字典只在新区代价更小时才入队。项目框架不会自动去重很多人在 Q3 卡住通常就是 visited 加错位置或者根本没有处理“旧状态代价更高”的情况。对比三种算法在同一个迷宫上的表现python pacman.py -l mediumMaze -p SearchAgent -a fndfs python pacman.py -l mediumMaze -p SearchAgent -a fnbfs python pacman.py -l mediumMaze -p SearchAgent -a fnucs参数说明-l 指定地图-p 指定 agent-a 传递算法参数。注意 UCS 在单步代价全为 1 的地图上会退化成 BFS所以在 mediumMaze 上看不出差别要体会优先队列的价值需要换到 mediumDottedMaze 这种带代价地图上或者直接用 mediumScaryMaze 跑 StayWestSearchAgent观察不同策略在风险地图上的行为差异。2.3 visited 的加法UCS 和 DFS/BFS 不一样很多同学会写出“入队时标记 visited”的版本if successor not in visited: visited.add(successor) fringe.push((successor, actions [action], cost step_cost))这个写法在 DFS 和 BFS 里问题不大因为这两种算法第一次到达某个状态时在各自的扩展顺序里已经是最优层数。但 UCS 不行假设起点到状态 A 先找到一条代价 5 的路径后找到一条代价 2 的路径如果代价 5 已经让 A 进入 visited代价 2 的路径就被永久跳过最终结果就不是最优。所以 UCS 必须把 visited 的准入条件改成“只允许更小代价进入”或者干脆把 visited 判断放到 pop 之后用 closed 字典记录已知最小 cost。提示UCS 优先队列里的 cost 必须是可比较的整数或浮点数不能是 None。如果 getCostOfActions 返回 NonePriorityQueue 在比较元组时会直接抛 TypeError。3. A* 搜索与曼哈顿启发式从 f(n) 公式到 mediumMaze 的性能差异3.1 实现 A* 时最容易错的 visited 策略A* 在代码层面和 UCS 几乎一致差别只在优先级从累计代价变成 f(n)g(n)h(n)。aStarSearch 函数的典型签名是def aStarSearch(problem, heuristicNone): if heuristic is None: heuristic nullHeuristic closed {} pq util.PriorityQueue() start problem.getStartState() pq.push((start, [], 0), heuristic(start, problem)) while not pq.isEmpty(): state, actions, cost pq.pop() if state in closed and closed[state] cost: continue closed[state] cost if problem.isGoalState(state): return actions for successor, action, step_cost in problem.getSuccessors(state): new_cost cost step_cost priority new_cost heuristic(successor, problem) pq.push((successor, actions [action], new_cost), priority) return []逻辑说明closed 字典保存当前已知最小 g只有新代价更小才继续扩展这比简单的 visited 集合更贴近教科书里的 A*。注意启发式函数接收两个参数 state 和 problem如果只实现成 h(state)会在运行时出现参数数量错误的 TypeError另外 push 时 priority 是 f但弹出来要保留 costg否则无法判断新路径是否更短。参数说明如果 heuristic 返回 0这个实现就退化成 UCS扩展节点数会显著增加。实验中经常有人“写了 A* 但没变快”先检查是不是没传 heuristic再看 closed 的更新位置。3.2 为什么曼哈顿距离在这里是合适的 h曼哈顿距离 h |x1-x2| |y1-y2|对 Pacman 这类四方向迷宫任意两格之间的最短路径不会小于这个值因为每一步只改变一个坐标且步长为 1。所以 h 可采纳能保证 A* 返回最优路径同时它又足够紧凑扩展节点远少于 UCS。迷宫里的墙会让真实距离大于曼哈顿距离这是允许的低估只会让搜索范围变大不会破坏最优性。真正要小心的是 h 必须满足一致性单调性h(s) c(s,s) h(s)。如果不满足理论上 A* 可能需要重新扩展已关闭节点在实现里表现为 closed 判断失效出现大量重复扩展。在 bigMaze 上验证 A* 的命令python pacman.py -l bigMaze -z .5 -p SearchAgent -a fnastar,heuristicmanhattanHeuristic参数说明-z .5 把迷宫缩小显示方便看整体路径heuristicmanhattanHeuristic 是 SearchAgent 内部注册的名字。如果直接运行不指定 heuristic很多实现会默认走 UCS看到的大地图搜索路径虽然正确但扩展节点数会多出不少。这里也能对比 BFS在 bigMaze 上 BFS 要铺满大量等距节点后才找到目标A* 由于方向性明显扩展区域会集中在起点到目标之间的带状范围。这个差异不需要很精确的数据肉眼就能在图形界面里分辨出来。3.3 启发式强度与扩展节点的权衡启发式不是越强越好。h 越接近真实代价扩展节点越少但每次计算 h 的代价也可能上升。曼哈顿距离在单目标搜索里是“便宜又实用”的选择在 multi-goal 场景比如后面 Corners 和 Eating All The Dots就要换更强的启发式否则搜索空间会爆炸。一个简单的判断标准是如果 A* 扩展节点数仍然等于或接近 UCS说明 h 在大多数状态下返回 0如果 h 计算本身比搜索还慢则要考虑预先计算 mazeDistance 并用查表方式缓存。Berkeley 框架允许在 SearchAgent 之外自定义 heuristic通常我们会在 agent 初始化时先算好所有点对距离矩阵再在启发式里直接查表避免每次调用都做成一次内部 BFS。4. Corners 与 Eating All The Dots问题表征和启发式才是真正的实验分水岭4.1 CornersProblem 的状态表示把“去过哪些角落”编码进状态Corners 问题不是找单个目标点而是要求一条路径访问地图四个角。如果状态只保留 Pacman 当前位置目标判定会丢失历史信息你不知道哪些角已经去过。因此 getStartState 必须返回复合状态位置 一个四元组/bitset 记录哪些角落已访问。比如四个角固定排好序用 (visited0, visited1, visited2, visited3) 表示初始为 (False, False, False, False)。getSuccessors 每走一步判断新位置是否等于某个角落是就把对应位置为 TrueisGoalState 检查四个位是否全为 True。这样搜索状态从“单点位置”变成“位置 × 2^4 的访问组合”状态空间扩大但问题才被正确建模。典型的类骨架如下class CornersProblem(search.SearchProblem): def __init__(self, startingGameState): self.walls startingGameState.getWalls() self.startingPosition startingGameState.getPacmanPosition() self.corners [(1, 1), (self.walls.width - 2, 1), (1, self.walls.height - 2), (self.walls.width - 2, self.walls.height - 2)] def getStartState(self): return (self.startingPosition, (False, False, False, False)) def isGoalState(self, state): position, visited state return all(visited)逻辑说明corners 的顺序必须固定否则位掩码对不上取迷宫四个角用 walls.width/height 减 2是因为最外圈是墙。isGoalState 用 all(visited) 判断四个角都访问过。很多人在这里犯的错是让 visited 随 actions 列表传递而不是放进 state那样图搜索的 visited 集合会无法正确判重因为相同位置但不同历史路径被当成不同状态处理。运行python pacman.py -l mediumCorners -p SearchAgent -a fnbfs,probCornersProblem参数说明probCornersProblem 告诉 SearchAgent 使用哪个问题类。直接在 tinyCorners 上跑 BFS 还能立刻出解到 mediumCorners 就能感到变慢这就是状态空间扩大的直接证据也为下一问启发式做铺垫。4.2 cornersHeuristic从“取最大”到“最近节点 MST”很多实现直接用“所有未访问角落到当前位置的曼哈顿距离取最大”作为 h。这个值在很多地图上会高估真实代价不满足可采纳性A* 可能返回非最优路径。要保证可采纳至少要取“到最近未访问角落的距离”因为从当前状态出发无论怎么走都先要到达某个未访问角落。这个下界很松但方向是对的。更紧的下界是把“当前位置 未访问角落”看作完全图图上每条边权用曼哈顿距离先用 Prim 或 Kruskal 求出最小生成树再用“当前位置到最近角落的距离 MST 总代价”作为 h。代码如下def cornersHeuristic(state, problem): position, visited state unvisited [c for i, c in enumerate(problem.corners) if not visited[i]] if not unvisited: return 0 dist lambda a, b: abs(a[0]-b[0]) abs(a[1]-b[1]) h min(dist(position, c) for c in unvisited) nodes unvisited edges [(dist(nodes[i], nodes[j]), i, j) for i in range(len(nodes)) for j in range(i1, len(nodes))] edges.sort() parent list(range(len(nodes))) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] x parent[x] return x mst 0 for w, i, j in edges: ri, rj find(i), find(j) if ri ! rj: parent[ri] rj mst w return h mst逻辑说明MST 代价表示在未访问角落之间移动所需的最小连接成本它是“从最近角落出发、把所有未访问角落串起来”的下界。因为曼哈顿距离满足三角不等式最终形成的估计不会高估真实最短路径启发式可采纳。这个实现里 Kruskal 只处理最多 3 个点性能开销可以忽略真正耗时的反而是计算多个曼哈顿距离所以不必用更复杂的数据结构。4.3 foodHeuristic用“当前位置 剩余食物点”的 MST 替代食物计数Eating All The Dots 的目标是吃掉所有食物状态空间比 Corners 更大每个食物都有“在/不在”两种状态直接搜索会非常慢。如果启发式只返回剩余食物数量虽然可采纳但剪枝太弱A* 会展开大量“还要吃 N 个食物”的等价状态。一个更实用的做法是把当前位置和所有未吃食物点看成一组节点边权用曼哈顿距离求 MST 总代价作为 h。它表示“为了吃完这些食物至少要走完这么长的连接网络”是可采纳下界。def foodHeuristic(state, problem): position, foodGrid state foods [(x, y) for x in range(foodGrid.width) for y in range(foodGrid.height) if foodGrid[x][y]] if not foods: return 0 # 复用 MST 计算把 position 也放进节点集合 return mst_cost([position] foods)运行命令python pacman.py -l trickySearch -p AStarFoodSearchAgent参数说明-p AStarFoodSearchAgent 表示使用 A* 的吃豆 agent。如果 foodHeuristic 写得不对比如返回 0 或不满足可采纳性这条命令会长时间没有输出写对之后A* 能在合理时间内给出可吃完全部食物的路径。调试时可以在 searchAgents.py 里打印状态数量和 h 值一般如果 h 长期为 0优先检查状态表示是 position 还是包含 food 集合。下面给出一张启发式强度对照表方便实验后复盘启发式可采纳性对节点扩展的影响适用场景nullHeuristic可采纳但恒为0等价于 UCS节点最多调试打印路径到最近食物曼哈顿距离可采纳中等简单小地图剩余食物数量可采纳剪枝很弱不推荐当前位置 食物点 MST可采纳显著减少trickySearch / bigSearch 等高难度地图5. 次优搜索与调试技巧ClosestDotSearchAgent 的“够用就好”工程取舍5.1 AnyFoodSearchProblem 的目标判断Suboptimal Search 要处理的是 A* 在 bigSearch 这类大地图上太慢的问题。思路是放弃全局最优改成贪心每步先找最近的豆子走到吃掉再找下一个。这个策略在迷宫里的合理性在于豆子往往分布在整个地图先处理附近食物不会明显破坏后续路径。实现上最关键的是新增 AnyFoodSearchProblem它的 isGoalState 只判断当前位置有没有食物而不是所有食物都被吃光。与 FoodSearchProblem 的区别就在这里前者解决“任意一个目标”后者解决“全部目标”目标测试写错会让搜索永远找不到终点。5.2 findPathToClosestDot 为什么用 BFS 而不是 A*ClosestDotSearchAgent 的 findPathToClosestDot 只需要返回一条到最近食物的路径。单步代价全部为 1因此 BFS 就能保证最短而且不需要启发式开销。核心代码可以短到几乎只有两行class AnyFoodSearchProblem(search.SearchProblem): def isGoalState(self, state): x, y state return self.food[x][y] def findPathToClosestDot(self, gameState): anyFood AnyFoodSearchProblem(gameState) return search.breadthFirstSearch(anyFood)逻辑说明food 是 gameState.getFood() 返回的二维布尔数组直接用 x/y 索引判断当前格子是否有食物。注意坐标顺序是 food[x][y] 而不是 food[y][x]传反会不断访问错误行建议用 gameState.hasFood(x, y) 方法减少这类低级错误。得到路径后agent 只执行第一个动作下一帧会重新构造问题从而形成“吃最近豆”的循环。这里不需要 A* 的原因是每次只要找一个目标而且地图单步代价统一BFS 的时间和空间复杂度都可控。5.3 自动评分与三个实用调试技巧实验自带的自动评分脚本是监考老师也是调试工具python autograder.py -q q8参数说明-q q8 表示只测第 8 个问题输出重定向到文件后可以静默判断报错位置。第一个技巧是在 searchAgents.py 里临时打印启发式返回值快速确认函数到底有没有被调用。如果总是打印 0优先检查 state 结构是否符合你写的启发式假设Corners 的 state 是 (position, visited) 二元组food 问题则可能是 position解包错位是最常见的错误。第二个技巧是手动构造小地图验证比如先用 tinyCorners 跑通表示逻辑再切换 mediumCorners不要在最大地图上调试状态建模。第三个技巧更常用调整 getSuccessors 返回后继方向的顺序。同样一套 A*先返回朝向目标的方向往往能更快找到第一条解虽然总扩展数不一定减少但首次出解时间会明显变短这对次优搜索尤其关键因为贪心策略要的就是快点吃到第一颗豆。本文还有配套的精品资源点击获取