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

1、人工智能导论实验报告学院：计算机科学与技术学院专业：计算机科学与技术目录人工智能导论实验报告错误!未定义书签。一、简介（对该实验背景，方法以及目的的理解）错误!未定义书签。实验背景错误!未定义书签。实验方法错误!未定义书签。实验目的错误!未定义书签。二、方法（对每个问题的分析及解决问题的方法）错误味定义书签。Q1: Depth First Search错误!未定义书签。Q2: Breadth First Search错误!未定义书签。Q3: Uniform Cost Search错误!未定义书签。Q4: A* Search错误!未定义书签。Q5: Corners Problem: Repres

2、entation 错误!未定义书签。Q6: Corners Problem: Heuristic 错误!未定义书签。Q7: Eating All The Dots: Heuristic错误!未定义书签。Q8: Suboptimal Search 错误味定义书签。三、实验结果（解决每个问题的结果）错误!未定义书签。Q1: Depth First Search错误!未定义书签。Q2: Breadth First Search 错误!未定义书签。Q3: Uniform Cost Search 错误!未定义书签。Q4: A* Search错误!未定义书签。Q5: Corners Problem: Re

3、presentation 错误味定义书签。Q6: Corners Problem: Heuristic 错误味定义书签。Q7: Eating All The Dots: Heuristic错误!未定义书签。Q8: Suboptimal Search错误!未定义书签。自动评分错误!未定义书签。四、 总结及讨论（对该实验的总结以及任何该实验的启发）.错误!未定义书签。简介（对该实验背景，方法以及目的的理解）实验背景1）自人工智能概念被提出，人工智能的发展就受到了很大的关注，取得了长足的发展，成 为一门广泛的交叉和前沿科学。到目前，弱人工智能取得了长足的发展，而强人工智能 则暂时处于瓶颈。2）吃豆人

4、Pacman居住在亮蓝色的世界里，在这个世界有弯曲的走廊和美味佳肴。游戏的 目的就是控制游戏的主角小精灵吃掉藏在迷宫内所有的豆子，并且不能被幽灵抓到。高 效地浏览世界将是吃豆人掌握世界的第一步。3）通过本学期的学习我们已经初步掌握了人工智能的基本知识，在实验中则应用这些知识 使用人工智能操纵吃豆人游戏。实验方法1）在本实验中，Pacman智能体将找到通过迷宫世界的路径，既包括到达一个指定的位 置，也包括高效地搜集食物。我们编辑文件和，编写一系列吃豆人程序，包括到达指定 位置以及有效的吃豆，并将其应用到Pacman场景，完成对相关人工智能功能的完善。2）在本实验中，我们对下面8个问题进行研究，针

5、对每个问题提出解决方法，逐步完成吃 豆人游戏：Q1: Depth First SearchQ2: Breadth First SearchQ3: Uniform Cost SearchQ4: A* SearchQ5: Corners Problem: RepresentationQ6: Corners Problem: HeuristicQ7: Eating All The Dots: HeuristicQ8: Suboptimal Search实验目的1）完成实验报告中的问题，编写一系列吃豆人程序，包括到达指定位置以及有效的吃豆;2）通过分析吃豆人游戏巩固课堂上所学内容；3）复习python

6、语言的使用。二、方法（对每个问题的分析及解决问题的方法）Q1: Depth First Search应用深度优先算法找到一个特定的位置的豆，我们通过depthFirstSearch函数实现深度优 先搜索的功能。深度优先遍历的方法是，从图中某顶点v出发：1）访问顶点v；2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通 的顶点都被访问；3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。深度优先搜索的顺序如下图所示:深度优先搜索在depthFirstSearch中，由于搜索过程中火重复访问到部分节点，所以

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

8、中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新 的起始点，重复上述过程，直至图中所有顶点都被访问到为止。如下图：在breadthFirstSearch中，大体的搜索思路与深度优先算法一致，只是搜索的次序发生了 变化。在这里注意，在深度优先搜索和广度优先搜索方法中，我们使用的图搜索算法是一样的，但 是涉及到具体的数据结构却是不同的。在深度优先搜索算法中，我们使用栈进行操作，在深 度优先搜索算法中，我们使用队列进行操作，如下图所示。这两种数据结构的不同之处就在 于其中元素的输出次序，在深度优先搜索中需要按照压栈顺序的逆序进行搜索，咋子广度优 先搜索中需要按照入队顺序的顺序进行搜索。de

9、f depthFirstSearch(probt.errr):#深虎优先瘦索149searchstack = util.Stack() def breadthFirstSearchtfirotitejTT):#广夏优先搜索* YOUR CODE HERE *1S8search_Queue = util.Queue()Q3: Uniform Cost Search很多情况下，路径中的代价是可以改变的，在这个问题中，我们完成代价一致搜索方法。代价一致搜索，其实就是一个贪心搜索，取代扩展深度最浅的节点，代价一致搜索扩展的是 路径消耗最低的节点n。如果所有单步耗散都相等的话，这种算法就和广度优先搜索算

10、法是 一样的。不过，这样在扩展到一个具有能返回到同一状态的零耗散行动的节点时就会陷入无 限循环。在uniformCostSearch函数中，我们计算每条路径的总代价，将总代价作为优先级进行搜索， 待搜索序列存储于队列中。对于每个节点，使用代价函数getCostOfActions计算其所产生 的代价，并依次作为搜索的优先级进行搜索。同样的，对于每个节点添加是否被访问的标记。Q4: A* SearchA*算法是一种静态路网中求解最短路最有效的直接搜索方法，也是许多其他问题的常用启发 式算法，对代价一致搜索算法进行了改进，加入了一个估计代价h。公式表示为：f(n)=g(n)+h(n),其中f(n)是

11、从初始状态经由状态n到目标状态的代价估计，g(n)是在状 态空间中从初始状态到状态n的实际代价，h(n)是从状态n到目标状态的最佳路径的估计 代价(对于路径搜索问题，状态就是图中的节点，代价就是距离)。在本实验中，我们使用曼哈顿距离作为启发函数。在aStarSearch函数中，我们首先搜索具 有最低组合成本和启发式的节点。类似于问题三，我们计算每个节点的代价，并以此为依据 搜索产生结果集，在搜索的过程中，还需要标记节点是否已经被访问过。Q5: Corners Problem: Representation找到所有的角落，在角落迷宫的四个角上面有四个豆，通过这个函数找到一条访问所有四个 角落的最

12、短的路径。 在CornersProblem类中，我们使用_init_函数存储墙壁的位置，吃豆人的起点和角落位 置，定义新的函数getStartState用于获得节点起始状态，isGoalState函数判断当前节点 是否为目标节点，getSuccessors函数返回后继状态，所需的操作以及代价， getCostOfActions函数计算动作序列所需的代价。查找后继节点时，在四个方向一次遍历，使用directionToVector移动位置，如果没有墙， 则把下一个的状态，动作，花费的步数加入下一节点Q6: Corners Problem: Heuristic构建合适的启发函数，完成问题5中的角落搜

13、索问题。在问题五使用的CornersProblem类中定义cornersHeuristic函数，为角落问题构造启发函 数。在cornersHeuristic函数中使用了 GetNextNodes函数获取下一个节点，isGoal函数 判断是否为目标。Q7: Eating All The Dots: Heuristic用尽可能少的步数吃掉所有的豆子。这个问题利用之前A*算法可以很容易找到解，此种方 法在这里不再详述。下面在FoodSearchProblem类中定义函数foodHeuristic，构建合适的启发函数完成豆子搜 索（启发式）问题。Q8: Suboptimal Search次最优搜索，定

14、义一个优先吃最近的豆子的函数，以此来提高搜索速度。补充AnyFoodSearchProblem目标测试函数，并在ClosestDotSearchAgent当中添加findPathToClosestDot函数，用于寻找最近的豆子。实验结果（解决每个问题的结果）Q1: Depth First Searchpython -l tinyMaze -p SearchAgentE : . T智能导准.实验0打巾_寄耕.=中般卜r.y-.hnn pa CTTisn. py -1 +i ryVaTR 一口 Rarc-：? Agpnt. rMpAr.-：hg=!T-it.| ng fi nc+.i nn rip

15、p+.-iFi Ts-tSipaTcl-i ITSearch.ssntl using ?rotl&m tvpe ?o=itionSearc?iPrcblenPs.th with ccst of ID in C. C secondsearch nodes eipandei： 20Picnan emerges vic-orious! Score: 53CAverageScore: 500.0Scores:500.0in Rate：1/1(1. 3C；Record：Winpython -l mediumMaze -p SearchAgentIE:，人工智能导论、实验search_C de -iZ：已

16、；-r:z：h/pythun pacnan. py -1 nediuirMaze -p Sear匚:hA,目已nt SearchAgent using Junerion dsprirEitSearch SearchAgent using problem type PositionGearchProbl em Path famid with total cost, of 1E：O in j. C seconds Search njdes expanded： lb2P a eman mer 3 日 vic + zirious ! S c or 9 : 2 E 0AverageScore: JUL,

17、JSzores:3S0.Jf_in Rate：1 门(1.0)；Record;Win浏 CSTfiB 七口丫5SCORE: -69python -l bigMaze -z .5 -p SearchAgent|E:八二智器界论、奏股LIlli- .it-iLiii. uv -1- . 5 阮妃ihAuwi：EEarcliAgent _i5 i 115 fjnLtioii de liF i r s t S e ar ch LEcaxchAgcntJ .13iprDslcm 口 Poci-ionEcc.xXTi=: L-iHFacnan 日merm日m victori yis Score: 300v

18、hiatiScuLti； 333.)Eccres :333.)hjin Rate：1/1Q. DD)p.eccrc. ：JinSCORE: -58Q2: Breadth First Searchpython -l mediumMaze -p SearchAgent -a fn=bfsE:Mssarch_Codeearchpythen pacman. py -1 nueiiiinrl酒白-p SearctiAgent -a fn=bfsSearcliAgent using function bfHSearcliAgent using problem type PositionSearchProb

19、ieniPath louiid tfith total cost of 6E inL。secondsSearch nodes expanded; 269Pacman erarg&s victorious! Score; 442Score: 442- 0Scores:442- 0Win Rate;L/l fl. 00)Kecord:VlnSCORE: -30python -l bigMaze -p SearchAgent -a fn=bfs -z .5|l：广、I 音Wk导炬任-er 】_： ,11fi-.：，：iuylh，：. paejran. py -1 bi glaze p SearchA

20、gent -a fn=bfE -z . 5 LSgarchAgBntJ using function bfslESearchAgentl using problem type Positi onSearchProblemPath found with total cost of 210 in 1. 0 secondsSearch nodes expanded： 620Paciruan emerges victorious! -pYthan pacman. pt -1 EEdii-inJlaze -p Se：archAgent -a fn=tiSearchAgent using function

21、 licc SearchAgent using prob lam type P de l t l onSa ar chPr ob L emPath found with total czist of 6E in C. 1 secondsEe：arch nadss sspanded： 269Pacman emerges victorious! Score： 442 TOC o 1-5 h z AverageScare: 442.0 HYPERLINK l bookmark92 o Current Document Scores:442.0pn Rate:1/1(L iTlRecord：VI np

22、ython -l mediumDottedMaze -p StayEastSearchAgentE: sea1, ch_C o des earchpytlion pacmarL py -1 ffiedimnD o tte dlaza -p EtayE as t S earcliAgentWarning： this does not look like a regular :-earch mazePath found vith total cost of 1 in 0- 0 secondsEear ch node ezn-anded： 136F板匚man emerge e vi ctoriDLi

23、s! S匚口re I 646.verageScora; 646.0Scores!646.(Ikn Rate;1/1(1. 00.)Tscord：Win74 CS1BB F占izn inSCORE: 72python -l mediumScaryMaze -p StayWestSearchAgentB ： 人工智能导论 ，A验日四匚匚 11_。口日、三日* 匚Dpythcin pacraan. py T 住 diumS匚aryN 日工已-p StayWestSearchAg.ent Path found with total cost of 6E719479864 in 0. 0 seconds

24、Searc?. nades expanded.： 108Paciran emerges victor! ous! Score : 418erageScore; 41S. 0Scores：418. 0in Rate：1/1 (1. 110)Eficord:TinT3 CSiiSO PiemanSCORE;pectird:ictoriinijs! Score: 300 3Q0. 0 300. 0(1.00)SCORE： -12Q4: A* Searchpython -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeur

25、isticE-:than paenan. py -1 bigflaze -z . 5 -p SearchAgent -a fn=8Star：1 heuristic=iTarijatt3r neairistic SBarzhAgen.t using. protlem type PasitinSearchProbleni Path :found with total cost- af 210 in 0. 4 seconds Search nodes expanded: 549 racmanQ5: Corners Problem: Representationpython -l tinyCorner

26、s -p SearchAgent -a fn=bfs,prob=CornersProblempython -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblemE:X/3&sMrth_Coi=ise：arclipythQn patnen. py -1 nedrunCcimere -p SearchAg.en.t -a fn=bfs：1 prob =CornersProbiem SearchAgent UEing function bis SBsrchf.EBnt using prctlem type ComersPrablen

27、i Path found with tota 1 cost of 106 in i . 1 secondsSearch nodeE exj：and&dl i960Faenan energ.es victorious! Score: 434Average Score： 43i0Scores:434 0lin Rate:1/1(1. Ld)Rjsc ord：I inQ6: Corners Problem: Heuristicpython -l mediumCorners -p AStarCornersAgent -z，人.工智能导论实验粕日口能柘瞬pacnsn. py T mediunCorija

28、rs -p AStarCDTij&rsA.gant -2 0. 5 Path found irith total cost af 106 in 0. 3 senndsEearcti nodSL： gpmdsd： 692Facman Bmerges victari dus ! Score : 434veraEEcore： 434. Q TOC o 1-5 h z HYPERLINK l bookmark71 o Current Document Scores:4340NJn ?7t-：1/1 .-i.Kecurd;VinQ7: Eating All The Dots: Heuristicpython -l trickySearch -p AStarFood