哈工大人工智能导论实验报告

1、人工智能实验报告人工智能导论实验报告学院：计算机科学与技术学院专业：计算机科学与技术人工智能实验报告目录人工智能导论实验报告 1一、简介 （对该实验背景，方法以及目的的理解 ） 31. 实验背景 32. 实验方法 33. 实验目的 3二、方法（对每个问题的分析及解决问题的方法） 4Q1: Depth First Search 4Q2: Breadth First Search 4Q3: Uniform Cost Search 5Q4: A* Search 6Q5: Corners Problem: Representation 6Q6: Corners Problem: Heuristic 6

2、Q7: Eating All The Dots: Heuristic7Q8: Suboptimal Search 7三、实验结果（解决每个问题的结果） 7Q1: Depth First Search 7Q2: Breadth First Search 9Q3: Uniform Cost Search 1.0Q4: A* Search 1.2Q5: Corners Problem: Representation 1.3 Q6: Corners Problem: Heuristic 1.4Q7: Eating All The Dots: Heuristic1.4 Q8: Suboptimal Se

3、arch 1.5自动评分 1.5四、总结及讨论（对该实验的总结以及任何该实验的启发） 1.5.人工智能实验报告简介 (对该实验背景，方法以及目的的理解)1. 实验背景1) 自人工智能概念被提出， 人工智能的发展就受到了很大的关注， 取得了长足的发展， 成 为一门广泛的交叉和前沿科学。 到目前， 弱人工智能取得了长足的发展， 而强人工智能 则暂时处于瓶颈。2) 吃豆人 Pacman 居住在亮蓝色的世界里， 在这个世界有弯曲的走廊和美味佳肴。 游戏的 目的就是控制游戏的主角小精灵吃掉藏在迷宫内所有的豆子， 并且不能被幽灵抓到。 高 效地浏览世界将是吃豆人掌握世界的第一步。3) 通过本学期的学习我们

4、已经初步掌握了人工智能的基本知识， 在实验中则应用这些知识 使用人工智能操纵吃豆人游戏。2. 实验方法1) 在本实验中 , Pacman 智能体将找到通过迷宫世界的路径 , 既包括到达一个指定的位置， 也包括高效地搜集食物。 我们编辑文件 search.py 和 searchAgents.py ，编写一系列吃豆 人程序， 包括到达指定位置以及有效的吃豆，并将其应用到Pacman 场景， 完成对相关人工智能功能的完善。2) 在本实验中， 我们对下面 8 个问题进行研究， 针对每个问题提出解决方法， 逐步完成吃 豆人游戏：Q1: Depth First SearchQ2: Breadth Firs

5、t SearchQ3: Uniform Cost SearchQ4: A* SearchQ5: Corners Problem: RepresentationQ6: Corners Problem: HeuristicQ7: Eating All The Dots: HeuristicQ8: Suboptimal Search3. 实验目的1) 完成实验报告中的问题，编写一系列吃豆人程序，包括到达指定位置以及有效的吃豆；2) 通过分析吃豆人游戏巩固课堂上所学内容；3) 复习 python 语言的使用。人工智能实验报告方法(对每个问题的分析及解决问题的方法)Q1: Depth First Sea

6、rch应用深度优先算法找到一个特定的位置的豆， 我们通过 depthFirstSearch 函数实现深度优先 搜索的功能。深度优先遍历的方法是，从图中某顶点 v 出发：1) 访问顶点 v；2) 依次从 v 的未被访问的邻接点出发， 对图进行深度优先遍历； 直至图中和 v 有路径相通 的顶点都被访问；3) 若此时图中尚有顶点未被访问， 则从一个未被访问的顶点出发， 重新进行深度优先遍历， 直到图中所有顶点均被访问过为止。深度优先搜索的顺序如下图所示：在 depthFirstSearch 中，由于搜索过程中火重复访问到部分节点，所以需要对于每个节点设 置标记，以指示该节点是否被访问过。 先将每个后

7、继节点压入搜索栈中，然后以深度优先 的顺序进行搜索，判定是否符合目标状态，并将符合结果的节点放入结果集。Q2: Breadth First Search应用宽度优先算法找到一个特定的位置的豆，我们通过 breadthFirstSearch 函数实现深度优 先搜索的功能。广度优先搜索算法的思想是： 从图中某顶点 v 出发，在访问了 v 之后依次访问 v的各个未曾 访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的 顶点的邻接点先于后被访问的顶点的邻接点被访问， 直至图中所有已被访问的顶点的邻接点人工智能实验报告都被访问到。 如果此时图中尚有顶点未被访问， 则需要另选

8、一个未曾被访问过的顶点作为新化。在这里注意， 在深度优先搜索和广度优先搜索方法中， 我们使用的图搜索算法是一样的， 但 是涉及到具体的数据结构却是不同的。 在深度优先搜索算法中， 我们使用栈进行操作， 在深 度优先搜索算法中， 我们使用队列进行操作， 如下图所示。 这两种数据结构的不同之处就在 于其中元素的输出次序， 在深度优先搜索中需要按照压栈顺序的逆序进行搜索， 咋子广度优 先搜索中需要按照入队顺序的顺序进行搜索。Q3: Uniform Cost Search很多情况下，路径中的代价是可以改变的，在这个问题中，我们完成代价一致搜索方法。人工智能实验报告代价一致搜索， 其实就是一个贪心搜索，

9、 取代扩展深度最浅的节点， 代价一致搜索扩展的是 路径消耗最低的节点 n 。如果所有单步耗散都相等的话， 这种算法就和广度优先搜索算法是 一样的。 不过， 这样在扩展到一个具有能返回到同一状态的零耗散行动的节点时就会陷入无 限循环。在 uniformCostSearch 函数中，我们计算每条路径的总代价， 将总代价作为优先级进行搜索， 待搜索序列存储于队列中。 对于每个节点， 使用代价函数 getCostOfActions 计算其所产生的 代价，并依次作为搜索的优先级进行搜索。同样的，对于每个节点添加是否被访问的标记。Q4: A* SearchA*算法是一种静态路网中求解最短路最有效的直接搜索

10、方法，也是许多其他问题的常用启 发式算法，对代价一致搜索算法进行了改进，加入了一个估计代价 h 。公式表示为： f(n)=g(n)+h(n), 其中 f(n) 是从初始状态经由状态 n 到目标状态的代价估计， g(n) 是在状态 空间中从初始状态到状态 n 的实际代价， h(n) 是从状态 n 到目标状态的最佳路径的估计代 价(对于路径搜索问题，状态就是图中的节点，代价就是距离) 。在本实验中，我们使用曼哈顿距离作为启发函数。在 aStarSearch 函数中，我们首先搜索具 有最低组合成本和启发式的节点。 类似于问题三， 我们计算每个节点的代价， 并以此为依据 搜索产生结果集，在搜索的过程中

11、，还需要标记节点是否已经被访问过。Q5: Corners Problem: Representation找到所有的角落， 在角落迷宫的四个角上面有四个豆， 通过这个函数找到一条访问所有四个 角落的最短的路径。在 CornersProblem 类中，我们使用 _init_函数存储墙壁的位置， 吃豆人的起点和角落位置， 定义新的函数 getStartState 用于获得节点起始状态， isGoalState 函数判断当前节点是否为 目标节点， getSuccessors 函数返回后继状态， 所需的操作以及代价， getCostOfActions 函数 计算动作序列所需的代价。查找后继节点时， 在四

12、个方向一次遍历， 使用 directionToVector 移动位置， 如果没有墙， 则 把下一个的状态，动作，花费的步数加入下一节点Q6: Corners Problem: Heuristic构建合适的启发函数，完成问题 5 中的角落搜索问题。在问题五使用的 CornersProblem 类中定义 cornersHeuristic 函数，为角落问题构造启发函 数。在 cornersHeuristic 函数中使用了 GetNextNodes 函数获取下一个节点， isGoal 函数判断 是否为目标。人工智能实验报告Q7: Eating All The Dots: Heuristic用尽可能少的

13、步数吃掉所有的豆子。这个问题利用之前A* 算法可以很容易找到解，此种方 法在这里不再详述。面在 FoodSearchProblem 类中定义函数 foodHeuristic ，构建合适的启发函数完成豆子搜 索（启发式）问题。Q8: Suboptimal Search次最优搜索，定义一个优先吃最近的豆子的函数，以此来提高搜索速度。补 充 AnyFoodSearchProblem 目 标 测 试 函 数 ， 并 在 ClosestDotSearchAgent 当 中 添 加 findPathToClosestDot 函数，用于寻找最近的豆子。三、 实验结果（解决每个问题的结果）Q1: Depth

14、First Searchpython pacman.py -l tinyMaze -p SearchAgentpython pacman.py -l mediumMaze -p SearchAgent人工智能实验报告python pacman.py -l bigMaze -z .5 -p SearchAgent8人工智能实验报告Q2: Breadth First Searchpython pacman.py -l mediumMaze -p SearchAgent -a fn=bfs9人工智能实验报告python pacman.py -l bigMaze -p SearchAgent -a f

15、n=bfs -z .5Q3: Uniform Cost Searchpython pacman.py -l mediumMaze -p SearchAgent -a fn=ucs10人工智能实验报告python pacman.py -l mediumDottedMaze -p StayEastSearchAgentpython pacman.py -l mediumScaryMaze -p StayWestSearchAgent11人工智能实验报告Q4: A* Searchpython pacman.py -l bigMaze fn=astar,heuristic=manhattanHeuri

16、stic-z .5 -p SearchAgent -a12人工智能实验报告Q5: Corners Problem: Representationpython pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblempython pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem13人工智能实验报告Q6: Corners Problem: Heuristicpython pacman.py -l mediumCorners

17、-p AStarCornersAgent -z 0.5Q7: Eating All The Dots: Heuristicpython pacman.py -l trickySearch -p AStarFoodSearchAgent14人工智能实验报告Q8: Suboptimal Searchpython pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5自动评分四、 总结及讨论 （对该实验的总结以及任何该实验的启发）1. 在这个实验中，我们对深度优先搜索、广度优先搜索、代价一致搜索和A*算法四种搜15人工智能实验报告索方法进行了 python 代码实现，对这四种方法有了进一