9.6 KiB
Executable File
9.6 KiB
Executable File
Pacman Search Project - 实验报告
项目概述
本项目是UC Berkeley CS188人工智能课程的第一个项目，主要实现各种搜索算法来解决Pacman游戏中的路径规划问题。项目涵盖了从基础的深度优先搜索到复杂的启发式搜索算法，以及针对特定问题的搜索策略设计。
实验环境
- 操作系统：Linux 6.17.9-2-cachyos
- Python版本：Python 3.x
- 项目路径：/home/gh0s7/project/cs188/proj1
实验内容与实现思路
Q1: 深度优先搜索 (Depth First Search, DFS)
实现思路
深度优先搜索是一种图搜索算法，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。
核心算法
- 使用栈(Stack)数据结构实现LIFO（后进先出）的搜索策略
- 维护一个已访问状态集合，避免重复搜索（图搜索）
- 将状态和到达该状态的路径作为元组存储在栈中
- 每次从栈顶弹出元素，检查是否为目标状态
- 如果不是目标状态，将其未访问的后继状态加入栈中
代码实现要点
# 初始化栈用于深度优先搜索，存储(状态, 路径)元组
fringe = util.Stack()
# 记录已访问的状态，避免重复搜索
visited = set()
测试结果
- 所有测试用例通过
- mediumMaze中找到长度为130的路径
- 扩展节点数：146个
Q2: 广度优先搜索 (Breadth First Search, BFS)
实现思路
广度优先搜索是一种图搜索算法，它从根节点开始，沿着树的宽度遍历树的节点。如果所有节点在同一深度被访问，那么算法将完全按照层级顺序进行访问。
核心算法
- 使用队列(Queue)数据结构实现FIFO（先进先出）的搜索策略
- 维护一个已访问状态集合，避免重复搜索
- 将状态和到达该状态的路径作为元组存储在队列中
- 每次从队列头部弹出元素，检查是否为目标状态
- 如果不是目标状态，将其未访问的后继状态加入队列中
代码实现要点
# 初始化队列用于广度优先搜索，存储(状态, 路径)元组
fringe = util.Queue()
# 记录已访问的状态，避免重复搜索
visited = set()
测试结果
- 所有测试用例通过
- mediumMaze中找到长度为68的最短路径
- 扩展节点数：269个
Q3: 一致代价搜索 (Uniform Cost Search, UCS)
实现思路
一致代价搜索是广度优先搜索的扩展，它考虑了路径的代价。算法总是扩展当前代价最小的节点，确保找到最优解。
核心算法
- 使用优先队列(PriorityQueue)数据结构，按照累积代价排序
- 维护一个已访问状态及其最小代价的字典
- 将状态、路径和累积代价作为元组存储在优先队列中
- 每次弹出代价最小的元素，检查是否为目标状态
- 如果不是目标状态，将其后继状态加入优先队列中
代码实现要点
# 初始化优先队列用于统一代价搜索，存储(状态, 路径, 累积代价)元组
fringe = util.PriorityQueue()
# 记录已访问的状态及其最小代价
visited = {}
测试结果
- 所有测试用例通过
- 在不同代价函数的迷宫中都能找到最优路径
- testSearch中找到长度为7的最优路径
Q4: A搜索 (A Search)
实现思路
A*搜索是一种启发式搜索算法，它结合了实际代价和启发式估计代价。算法使用f(n) = g(n) + h(n)作为评估函数，其中g(n)是从起始状态到当前状态的实际代价，h(n)是从当前状态到目标状态的启发式估计代价。
核心算法
- 使用优先队列，按照f(n)值排序
- 维护一个已访问状态及其最小g(n)代价的字典
- 将状态、路径和g(n)代价作为元组存储在优先队列中
- 每次弹出f(n)值最小的元素，检查是否为目标状态
- 如果不是目标状态，将其后继状态加入优先队列中
代码实现要点
# 计算新的f(n)值 = g(n) + h(n)
fValue = newCost + newHeuristic
# 将后继状态加入优先队列，优先级为f(n)值
fringe.push((successor, newActions, newCost), fValue)
测试结果
- 所有测试用例通过
- mediumMaze中扩展221个节点，比UCS的269个节点更少
- 证明了启发式的有效性
Q5: 角落问题 (Corners Problem)
实现思路
角落问题要求Pacman访问迷宫中的四个角落。这是一个更复杂的搜索问题，需要设计合适的状态表示和状态转移。
状态表示
状态表示为元组：(当前位置, 已访问的角落元组)
- 当前位置：Pacman的坐标
- 已访问的角落：四个布尔值，分别对应四个角落是否已被访问
核心算法
- 设计合理的状态表示，包含位置信息和角落访问状态
- 实现getStartState()方法，返回初始状态
- 实现isGoalState()方法，检查是否所有角落都已访问
- 实现getSuccessors()方法，生成所有合法的后继状态
代码实现要点
# 状态表示为：(当前位置, 已访问的角落元组)
cornersVisited = tuple([corner == self.startingPosition for corner in self.corners])
return (self.startingPosition, cornersVisited)
测试结果
- 所有测试用例通过
- tinyCorner中找到长度为28的路径
Q6: 角落启发式 (Corners Heuristic)
实现思路
为角落问题设计一个一致且可接受的启发式函数，以加速A*搜索。
启发式策略
- 计算当前位置到最远未访问角落的曼哈顿距离
- 计算未访问角落之间的最大距离
- 返回两个距离中的较大值作为启发式估计
代码实现要点
# 找出所有未访问的角落
unvisitedCorners = []
for i, corner in enumerate(corners):
if not cornersVisited[i]:
unvisitedCorners.append(corner)
# 计算到最远未访问角落的曼哈顿距离
maxDistance = 0
for corner in unvisitedCorners:
distance = util.manhattanDistance(currentPosition, corner)
maxDistance = max(maxDistance, distance)
测试结果
- 所有测试用例通过
- 启发式测试通过，证明了一致性
- 扩展节点数：961个，满足要求
Q7: 食物启发式 (Food Heuristic)
实现思路
为食物收集问题设计一个一致且可接受的启发式函数，以加速A*搜索。
启发式策略
- 计算到最远食物的曼哈顿距离
- 计算食物之间的最大距离
- 使用食物数量作为基础代价
- 返回三个策略中的最大值，确保启发式是可接受的且更准确
代码实现要点
# 计算到最近食物的曼哈顿距离
minDistance = float('inf')
for food in foodList:
distance = util.manhattanDistance(position, food)
if distance < minDistance:
minDistance = distance
# 加上剩余食物数量的估计
return minDistance + len(foodList) - 1
测试结果
- 18个测试用例全部通过
- 高级测试用例扩展节点数：8763个（满足阈值要求）
- 得分：4/4（满分）
Q8: 寻找最近点路径 (Find Path to Closest Dot)
实现思路
实现一个贪婪算法，每次都走向最近的食物点。这是一个次优但快速的策略。
核心算法
- 实现AnyFoodSearchProblem的isGoalState()方法
- 在findPathToClosestDot()中使用BFS找到最近的食物点
- 重复执行直到所有食物都被收集
代码实现要点
# 目标状态是Pacman到达任何食物的位置
return self.food[x][y]
# 使用广度优先搜索找到最近的食物点
path = search.bfs(problem)
测试结果
- 所有测试用例通过
- 13个测试用例全部通过
实验总结
成果
- 成功实现了8个搜索算法和启发式函数
- 总得分：25/25（100%满分）
- Q1-Q8全部通过，获得满分
遇到的挑战
- Q7的食物启发式设计较为复杂，需要在可接受性和一致性之间找到平衡
- 状态表示的设计对搜索效率有很大影响
- 启发式函数的质量直接影响搜索性能
- 通过多次迭代优化，成功将启发式函数改进为满分版本
学到的知识
- 掌握了各种搜索算法的原理和实现
- 理解了启发式搜索的设计原则
- 学会了如何针对特定问题设计合适的状态表示
- 深入理解了可接受性和一致性的概念
改进方向
- 可以进一步优化Q7的启发式函数，减少扩展节点数
- 可以尝试更复杂的启发式策略，如最小生成树
- 可以研究更高效的搜索算法变体
代码结构
主要文件
search.py：包含所有搜索算法的实现searchAgents.py：包含搜索代理和特定问题的实现util.py：提供数据结构和工具函数
关键函数
depthFirstSearch()：深度优先搜索breadthFirstSearch()：广度优先搜索uniformCostSearch()：一致代价搜索aStarSearch()：A*搜索CornersProblem：角落问题类cornersHeuristic()：角落启发式函数foodHeuristic()：食物启发式函数findPathToClosestDot()：寻找最近点路径
运行方法
单个问题测试
python autograder.py -q q1 # 测试Q1
python autograder.py -q q2 # 测试Q2
...
python autograder.py -q q8 # 测试Q8
全部问题测试
python autograder.py # 测试所有问题
运行Pacman游戏
python pacman.py -l tinyMaze -p SearchAgent # 运行Pacman游戏
结论
通过完成这个项目，我深入理解了各种搜索算法的原理和实现，掌握了启发式搜索的设计方法，学会了如何针对特定问题设计合适的搜索策略。这些知识对于解决人工智能中的路径规划问题具有重要意义。