人工智能导论实验报告吃豆人游戏.docx

人工智能实验报告 人工智能导论实验报告 学院：计算机科学与技术学院专业：计算机科学与技术 2016.12.20 目录 人工智能导论实验报告 1 一、 简介(对该实验背景，方法以及目的的理解) 2 实验背景 2 实验方法 3 实验目的 3 二、 方法（对每个问题的分析及解决问题的方法） 3 Q1: Depth First Search 3 1 人工智能实验报告 Q2: Breadth First Search 4 Q3: Uniform Cost Search 5 Q4: A* Search 6 Q5: Corners Problem: Representation 6 Q6: Corners Problem: Heuristic 6 Q7: Eating All The Dots: Heuristic. 7 Q8: Suboptimal Search 7 三、 实验结果（解决每个问题的结果） 7 Q1: Depth First Search 7 Q2: Breadth First Search 9 Q3: Uniform Cost Search 10 Q4: A* Search 1. 2 Q5: Corners Problem: Representation 13 Q6: Corners Problem: Heuristic 14 Q7: Eating All The Dots: Heuristic. 14 Q8: Suboptimal Search 1. 5 自动评分 1. 5 四、 总结及讨论（对该实验的总结以及任何该实验的启发） 15 一、 简介(对该实验背景，方法以及目的的理解) 实验背景 则暂时处于瓶颈。自人工智能概念被提出，人工智能的发展就受到了很大的关注，取得了长足的发展，成为一门广泛的交叉和前沿科学。到目前，弱人工智能取得了长足的发展，而强人工智能 则暂时处于瓶颈。 2 人工智能实验报告 吃豆人 Pacman 居住在亮蓝色的世界里，在这个世界有弯曲的走廊和美味佳肴。游戏的目的就是控制游戏的主角小精灵吃掉藏在迷宫内所有的豆子，并且不能被幽灵抓到。高效地浏览世界将是吃豆人掌握世界的第一步。 通过本学期的学习我们已经初步掌握了人工智能的基本知识，在实验中则应用这些知识使用人工智能操纵吃豆人游戏。 实验方法 在本实验中, Pacman 智能体将找到通过迷宫世界的路径, 既包括到达一个指定的位置， 也包括高效地搜集食物。我们编辑文件 search.py 和 searchAgents.py，编写一系列吃豆人程序，包括到达指定位置以及有效的吃豆，并将其应用到Pacman 场景，完成对相关人工智能功能的完善。 在本实验中，我们对下面 8 个问题进行研究，针对每个问题提出解决方法，逐步完成吃豆人游戏： Q1: Depth First Search Q2: Breadth First Search Q3: Uniform Cost Search Q4: A* Search Q5: Corners Problem: Representation Q6: Corners Problem: Heuristic Q7: Eating All The Dots: Heuristic Q8: Suboptimal Search 实验目的 完成实验报告中的问题，编写一系列吃豆人程序，包括到达指定位置以及有效的吃豆； 通过分析吃豆人游戏巩固课堂上所学内容； 复习 python 语言的使用。 二、 方法（对每个问题的分析及解决问题的方法） Q1: Depth First Search 应用深度优先算法找到一个特定的位置的豆，我们通过 depthFirstSearch 函数实现深度优先搜索的功能。 深度优先遍历的方法是，从图中某顶点v 出发： 访问顶点v； 依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和 v 有路径相通的顶点都被访问； 3 人工智能实验报告 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历， 直到图中所有顶点均被访问过为止。 深度优先搜索的顺序如下图所示： 在 depthFirstSearch 中，由于搜索过程中火重复访问到部分节点，所以需要对于每个节点设置标记，以指示该节点是否被访问过。 先将每个后继节点压入搜索栈中，然后以深度优先的顺序进行搜索，判定是否符合目标状态，并将符合结果的节点放入结果集。 Q2: Breadth First Search 应用宽度优先算法找到一个特定的位置的豆，我们通过breadthFirstSearch 函数实现深度优先搜索的功能。 广度优先搜索算法的思想是：从图中某顶点 v 出发，在访问了