深度优先搜索与广度优先搜索在Pacman游戏中的应用

在本报告中，我们探讨了如何在Python编程中实现深度优先搜索（Depth-First Search, DFS）和广度优先搜索（Breadth-First Search, BFS）算法，特别是在`search.py`文件中的`depthFirstSearch`和`breadthFirstSearch`函数中。报告由学生林逸晗于2016年1月7日提交，主题涉及Pacman游戏中的路径寻找。 1. 深度优先搜索（DFS）: - 在`depthFirstSearch`函数中，使用栈（Stack）作为数据结构，它存储了动作（action）和状态（state）的组合，形成一个搜索树的支撑结构。通过递归的方式实现DFS，创建了一个名为`DFS`的新函数，它接受问题实例`problem`和起始节点`root`作为参数。搜索过程从根节点开始，展开子节点，选择一个子节点作为新的根，将action和state入栈，然后继续下一层搜索。当达到目标状态（goal）时，返回一系列动作列表。然而，这种方法虽然能够快速找到一条路径，但在解决复杂问题时可能无法找到最优解，因为它可能会陷入局部最优。 2. 广度优先搜索（BFS）: - 在`breadthFirstSearch`函数中，采用队列（Queue）作为数据结构。搜索从起始节点（root）开始，首先将离根节点最近的节点加入队列，随后处理下一批节点。同时，将与节点关联的动作一同放入队列。当处理队首节点时，会获取其未探索过的后继节点并压入栈中，以确保优先处理更远的节点。为了解决多目标问题，作者对`isGoalState`函数进行了修改，记录每个节点到目标的路径，并将这些路径信息与节点一起存储在队列中，以便后续遍历。 通过这两个算法的应用，报告展示了Pacman游戏在特定布局（mediumMaze）下的搜索结果，包括解决方案长度（246），以及在找到解的过程中总共扩展的节点数（269）。虽然找到了解，但BFS在寻找最优解方面通常比DFS更为高效，但实际应用中选择哪种方法取决于具体问题的性质和需求。 总结来说，这份报告深入讲解了在游戏AI中的搜索算法应用，不仅演示了代码实现，还对算法的性能进行了分析，对于理解搜索算法在路径规划中的作用和权衡至关重要。