2022年哈工大人工智能导论实验报告.docx

《2022年哈工大人工智能导论实验报告.docx》由会员分享，可在线阅读，更多相关《2022年哈工大人工智能导论实验报告.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源人工智能导论试验报告学院：电脑科学与技术学院专业：电脑科学与技术欢迎下载精品学习资源目录人工智能导论试验报告1一、简介 对该试验背景，方法以及目的的懂得31. 试验背景32. 试验方法33. 试验目的3二、方法对每个问题的分析及解决问题的方法4Q1: Depth First Search4Q2: Breadth First Search4Q3: Uniform Cost Search5Q4: A* Search6Q5: Corners Problem: Representation6Q6: Corners Problem: Heuristic6Q7: Eating All The

2、Dots: Heuristic.7Q8: Suboptimal Search7三、试验结果解决每个问题的结果7Q1: Depth First Search7Q2: Breadth First Search9Q3: Uniform Cost Search.1.0.Q4: A* Search .1.2.Q5: Corners Problem: Representation.1.3.Q6: Corners Problem: Heuristic.1.4.Q7: Eating All The Dots: Heuristic.1.4.Q8: Suboptimal Search .1.5.自动评分 .1.6

3、.四、总结及争论对该试验的总结以及任何该试验的启示.1.6.欢迎下载精品学习资源一、 简介对该试验背景，方法以及目的的懂得1. 试验背景1) 自人工智能概念被提出， 人工智能的进展就受到了很大的关注，取得了长足的进展，成为一门广泛的交叉和前沿科学；就临时处于瓶颈；到目前， 弱人工智能取得了长足的进展，而强人工智能2) 吃豆人 Pacman 居住在亮蓝色的世界里， 在这个世界有弯曲的走廊和美味佳肴； 嬉戏的目的就是掌握嬉戏的主角小精灵吃掉藏在迷宫内全部的豆子， 并且不能被幽灵抓到； 高效地浏览世界将是吃豆人把握世界的第一步；3) 通过本学期的学习我们已经初步把握了人工智能的基本学问， 在试验中就

4、应用这些学问使用人工智能操纵吃豆人嬉戏；2. 试验方法1) 在本试验中 , Pacman 智能体将找到通过迷宫世界的路径 , 既包括到达一个指定的位置， 也包括高效地搜集食物； 我们编辑文件， 编写一系列吃豆人程序， 包括到达指定位置以及有效的吃豆，并将其应用到 Pacman 场景，完成对相关人工智能功能的完善；2) 在本试验中， 我们对下面 8 个问题进行争论， 针对每个问题提出解决方法， 逐步完成吃豆人嬉戏：Q1: Depth First Search Q2: Breadth First Search Q3: Uniform Cost Search Q4: A* SearchQ5: Cor

5、ners Problem: Representation Q6: Corners Problem: HeuristicQ7: Eating All The Dots: Heuristic Q8: Suboptimal Search3. 试验目的1) 完成试验报告中的问题，编写一系列吃豆人程序，包括到达指定位置以及有效的吃豆；2) 通过分析吃豆人嬉戏稳固课堂上所学内容；3) 复习 python 语言的使用；欢迎下载精品学习资源二、 方法对每个问题的分析及解决问题的方法Q1: Depth First Search应用深度优先算法找到一个特定的位置的豆，我们通过 depthFirstSearch函数

6、实现深度优先搜寻的功能；深度优先遍历的方法是，从图中某顶点v 动身：1) 拜访顶点 v；2) 依次从 v 的未被拜访的邻接点动身，对图进行深度优先遍历； 直至图中和 v 有路径相通的顶点都被拜访；3) 假设此时图中尚有顶点未被拜访，就从一个未被拜访的顶点动身，重新进行深度优先遍历，直到图中全部顶点均被拜访过为止；深度优先搜寻的次序如以下图所示：在 depthFirstSearch中，由于搜寻过程中火重复拜访到部分节点，所以需要对于每个节点设 置标记，以指示该节点是否被拜访过；先将每个后继节点压入搜寻栈中，然后以深度优先的次序进行搜寻，判定是否符合目标状态，并将符合结果的节点放入结果集；Q2:

7、Breadth First Search应用宽度优先算法找到一个特定的位置的豆，我们通过breadthFirstSearch函数实现深度优先搜寻的功能；广度优先搜寻算法的思想是：从图中某顶点v 动身， 在拜访了 v 之后依次拜访 v 的各个未曾拜访过的邻接点，然后分别从这些邻接点动身依次拜访它们的邻接点，并使得“先被拜访的顶点的邻接点先于后被拜访的顶点的邻接点被拜访，直至图中全部已被拜访的顶点的邻接点欢迎下载精品学习资源都被拜访到； 假如此时图中尚有顶点未被拜访，就需要另选一个未曾被拜访过的顶点作为新的起始点，重复上述过程，直至图中全部顶点都被拜访到为止；如以下图：在 breadthFirst

8、Search中，大体的搜寻思路与深度优先算法一样，只是搜寻的次序发生了变化；在这里留意， 在深度优先搜寻和广度优先搜寻方法中，我们使用的图搜寻算法是一样的，是涉及到详细的数据结构却是不同的；在深度优先搜寻算法中， 我们使用栈进行操作，但在深度优先搜寻算法中， 我们使用队列进行操作，如以下图所示； 这两种数据结构的不同之处就在于其中元素的输出次序，在深度优先搜寻中需要根据压栈次序的逆序进行搜寻，咋子广度优先搜寻中需要根据入队次序的次序进行搜寻；Q3: Uniform Cost Search很多情形下，路径中的代价是可以转变的，在这个问题中，我们完成代价一样搜寻方法；欢迎下载精品学习资源代价一样搜

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

10、搜寻方法，也是很多其他问题的常用启发式算法，对代价一样搜寻算法进行了改良，加入了一个估量代价h ；公式表示为： fn=gn+hn,其中 fn是从初始状态经由状态n 到目标状态的代价估量，gn 是在状态空间中从初始状态到状态n 的实际代价， hn是从状态 n 到目标状态的最正确路径的估量代价对于路径搜寻问题，状态就是图中的节点，代价就是距离；在本试验中，我们使用曼哈顿距离作为启示函数；在aStarSearch 函数中，我们第一搜寻具有最低组合成本和启示式的节点；类似于问题三， 我们运算每个节点的代价，并以此为依据搜寻产生结果集，在搜寻的过程中，仍需要标记节点是否已经被拜访过；Q5: Corner

11、s Problem: Representation找到全部的角落， 在角落迷宫的四个角上面有四个豆，通过这个函数找到一条拜访全部四个角落的最短的路径；在 CornersProblem类中，我们使用 init 函数储备墙壁的位置， 吃豆人的起点和角落位置， 定义新的函数getStartState用于获得节点起始状态，isGoalState 函数判定当前节点是否为目标节点， getSuccessors 函数返回后继状态， 所需的操作以及代价， getCostOfActions函数运算动作序列所需的代价；查找后继节点时， 在四个方向一次遍历， 使用 directionToVector移动位置， 假如

12、没有墙， 就把下一个的状态，动作，花费的步数加入下一节点Q6: Corners Problem: Heuristic构建合适的启示函数，完成问题5 中的角落搜寻问题；在问题五使用的CornersProblem类中定义cornersHeuristic函数，为角落问题构造启示函 数；在 cornersHeuristic函数中使用了 GetNextNodes函数猎取下一个节点，isGoal 函数判定是否为目标；欢迎下载精品学习资源Q7: Eating All The Dots: Heuristic用完可能少的步数吃掉全部的豆子；这个问题利用之前A* 算法可以很简单找到解，此种方法在这里不再详述；下面

13、在 FoodSearchProblem类中定义函数 foodHeuristic ，构建合适的启示函数完成豆子搜寻启示式问题；Q8: Suboptimal Search次最优搜寻，定义一个优先吃最近的豆子的函数，以此来提高搜寻速度；补 充 AnyFoodSearchProblem目 标 测试 函 数 ， 并 在 ClosestDotSearchAgent当 中 添 加findPathToClosestDot函数，用于查找最近的豆子；三、 试验结果解决每个问题的结果Q1: Depth First Searchpython pacman.py -l tinyMaze -p SearchAgentpy

14、thon pacman.py -l mediumMaze -p SearchAgent欢迎下载精品学习资源python pacman.py -l bigMaze -z .5 -p SearchAgent欢迎下载精品学习资源Q2: Breadth First Searchpython pacman.py -l mediumMaze -p SearchAgent -a fn=bfs欢迎下载精品学习资源python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5Q3: Uniform Cost Searchpython pacman.py -l

15、 mediumMaze -p SearchAgent -a fn=ucs欢迎下载精品学习资源python pacman.py -l mediumDottedMaze -p StayEastSearchAgentpython pacman.py -l mediumScaryMaze -p StayWestSearchAgent欢迎下载精品学习资源Q4: A* Searchpythonpacman.py-lbigMaze-z.5-pSearchAgent-afn=astar,heuristic=manhattanHeuristic欢迎下载精品学习资源Q5: Corners Problem: Rep

16、resentationpython pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblempython pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem欢迎下载精品学习资源Q6: Corners Problem: HeuristicQ7: Eating All The Dots: Heuristicpython pacman.py -l trickySearch -p AStarFoodSearchAgent欢迎下载精

17、品学习资源Q8: Suboptimal Searchpython pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5欢迎下载精品学习资源自动评分四、 总结及争论 对该试验的总结以及任何该试验的启示1. 在这个试验中，我们对深度优先搜寻、广度优先搜寻、代价一样搜寻和A*算法四种搜寻方法进行了 python代码实现，对这四种方法有了进一步的明白；与深度优先搜寻和广度优先上搜寻方法相比，代价一样搜寻方法的效率更高，在代价一样上搜寻方法失效 时， 等同于广度优先搜寻； A* 算法是最有效的直接搜寻算法，使用公式进行预处理， 这样能够省略大量不必要的搜寻路径，提高了效率；2. 在启示式搜寻中， 估价函数特别重要， 精确的估价函数能够增大搜寻函数的效率并且具有相当高的精确性；由此， 在启示式搜寻中对位置的估价是特别重要的；采纳了不同的估价可以有不同的成效；3. 在本次试验中使用了大量python语言中的类， 对之前的 python 学问有了很大的扩展；欢迎下载