完整版哈工大人工智能导论试验报告

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

2、All The Dots: Heuristic7Q8: Suboptimal Search73、 实验结果（解决每个问题的结果） 7Q1: Depth First Search7Q2: Breadth First Search 9Q3: Uniform Cost Search 10Q4: A* Search 1.2Q5: Corners Problem: Representation 13Q6: Corners Problem: Heuristic 1.4Q7: Eating All The Dots: Heuristic1.4.Q8: Suboptimal Search15自动评分1.54、

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

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

5、: 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 Search应用深度优先算法找到一个特定的位置的

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

7、点放入结果集。Q2: Breadth First Search应用宽度优先算法找到一个特定的位置的豆，我们通过breadthFirstSearch函数实现深度优先搜索的功能。广度优先搜索算法的思想是：从图中某顶点v出发，在访问了 v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。如下图：化。在这里注意，在深度优先搜索和广度优先

8、搜索方法中，我们使用的图搜索算法是一样的，但是涉及到具体的数据结构却是不同的。在深度优先搜索算法中， 我们使用栈进行操作， 在深度优先搜索算法中，我们使用队列进行操作，如下图所示。这两种数据结构的不同之处就在于其中元素的输出次序， 在深度优先搜索中需要按照压栈顺序的逆序进行搜索，咋子广度优先搜索中需要按照入队顺序的顺序进行搜索。147 d皂f depthFirstSearch(probtejjj):148#深座优先里,素149search_&tack - util,Stack()It S t def breadthFirstSear'ch(pro6tejT?):18b#广堂优先

9、搜索1B7"* YOUR CODEHERE *h"18S189searchOueueutil.Queue()Q3: Uniform Cost Search很多情况下，路径中的代价是可以改变的，在这个问题中，我们完成代价一致搜索方法。二臂上停HARBIN INSnTWTE OF TECHNOLOGY代价一致搜索，其实就是一个贪心搜索，取代扩展深度最浅的节点，代价一致搜索扩展的是路径消耗最低的节点 no如果所有单步耗散都相等的话，这种算法就和广度优先搜索算法是一样的。不过，这样在扩展到一个具有能返回到同一状态的零耗散行动的节点时就会陷入无 限循环。在uniformCostSea

10、rch函数中，我们计算每条路径的总代价，将总代价作为优先级进行搜索，待搜索序列存储于队列中。对于每个节点，使用代价函数getCostOfActions计算其所产生的代价，并依次作为搜索的优先级进行搜索。同样的，对于每个节点添加是否被访问的标记。Q4: A* SearchA*算法是一种静态路网中求解最短路最有效的直接搜索方法，也是许多其他问题的常用启 发式算法，对代价一致搜索算法进行了改进，加入了一个估计代价ho公式表示为：f(n尸g(n)+h(n),其中f(n)是从初始状态经由状态 n到目标状态的代价估计，g(n)是在状态空间中从初始状态到状态n的实际代价，h(n)是从状态n到目标状态的最佳路

11、径的估计代价(对于路径搜索问题，状态就是图中的节点，代价就是距离)。在本实验中，我们使用曼哈顿距离作为启发函数。在 aStarSearch函数中，我们首先搜索具 有最低组合成本和启发式的节点。类似于问题三，我们计算每个节点的代价，并以此为依据搜索产生结果集，在搜索的过程中，还需要标记节点是否已经被访问过。Q5: Corners Problem: Representation找到所有的角落，在角落迷宫的四个角上面有四个豆，通过这个函数找到一条访问所有四个角落的最短的路径。在CornersProblem类中，我们使用_init_函数存储墙壁的位置，吃豆人的起点和角落位置， 定义新的函数 getSt

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

13、ersHeuristic函数中使用了 GetNextNodes函数获取下一个节点，isGoal函数判断 是否为目标。%南Q#次停HARBIN IhlTITUTE OF TECHNOLOGYQ7: Eating All The Dots: Heuristic用尽可能少的步数吃掉所有的豆子。这个问题利用之前A*算法可以很容易找到解，此种方法在这里不再详述。下面在FoodSearchProblem 类中定义函数 foodHeuristic ,构建合适的启发函数完成豆子搜 索（启发式）问题。Q8: Suboptimal Search次最优搜索，定义一个优先吃最近的豆子的函数，以此来提高搜索速度。补 充

14、 AnyFoodSearchProblem 目标测试函数，并在 ClosestDotSearchAgent 当 中添加 findPathToClosestDot函数，用于寻找最近的豆子。三、实验结果（解决每个问题的结果）Q1: Depth First Searchpython pacman.py -l tinyMaze -p SearchAgentE：人工智百自导检实北口七白红pacmari.py _1 tinyMaze SearchAeent SearchAgent us ins function dert-ir st Search.Searchent using Drablem ty)&g

15、t;e PoaitionSearchProblenPath found with total cost of 10 in 0. 0 secondsSearch nodes espanded： 20Pacnan eiriBrges victoriDus! Score： 50CAverage Score: 500. 0Scores ：50(1 0fin Rate:1/1(L00)Record:Winf CSIBSacirTL.期SCORE: 500python pacman.py -l mediumMaze -p SearchAgentE! 人工智能导论'实验 8虹ch_Ca da s e

16、 srchpython pa4man. py -1 nediuiriMaEe -p EeareJrA5erit SearchAant usirg 1 me tian dap thFirsTSe arch EearchAg&ntJ using prcblan type Posi t i cnSsar chPr obi erPath found with total cost of 130 in 0.C secondsSearch nDles eiparded ： Ito2PaciTAn ejn&rsaff victorions? Score： W£。Aeragt!jt.

17、ui'-s: 38(, 0Scores'381.0Vin Rito：1/1 (1.00)Rec ord;Winpython pacman.py -l bigMaze -z .5 -p SearchAgent1：人二智能导论实险工£曰11口由1_。如七3敌11<；11>»¥山口口1513翊.口¥ -1, 5 w Sea-i'chAeurit=StciicliAgHiit jsltig £luiuLluii dtjp lliTlrs t.Sudixl.LctdJ. ullAgbillt iJolhg pl'

18、;ubllziiu ,ype 'nsi ; i oiiu e di cl iTr l LI en.Path found with total tost cf 210 in 0. 0 second*Gear ch iiodes eKpandei： 569Pacnari cncrcoa victorious! Score： 300Avcroc Score： 200,Scarce：300+D布口 Rato：1/1(1. 00)Roccxd：WinQ2: Breadth First Searchpython pacman.py -l mediumMaze -p SearchAgent -a f

19、n=bfsE '人工智能片至l手康口曲geareK小ythori tiaciua.n_ py 三I vniadLLurNz 三口 SearchAgent 三理 fn-bfs lut-areJriAgwijil ush唱 fUriel ion bf t rCearchAgADl using probl'em type Posi t ianSearchfrobl bhPath found total 弋口写t of 63 in 0. 0 secondsSerdh node-s eKpanded； 269Pacman eirerfies victoriauF! Ecnre； 442A

20、verageScore： 442.0Scoros：442.0Vin Ra«：L/L(1.00)Rflcard：Vin£飞必南城学»JHARBIM 喷 TIT WE OF TEC HNOLQGYpython pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5E -工智能导七、实殓 yr r h_c odeS sEarch>pjrthan pTjjm匚-py 1 bi 1 S e 1' _ hAg ei it a"2 . &.S=arcfJrfUj wii巩 fUriGtiDti bf

21、a .Saar:hASLTitJ ucinjc; prcblzm tvpo Pos i ti DnSa arcPr obi c mFath fcund vidi total cost of 210 in Q 0 seconds1日三丁匚nndfis Fifi indPii：H工Patmanuictoricus! Sccr口：30CAvsraE 总二arm： 3DO. ?Scares ：3 DO. Dfin Rate：JH (1.00)Rb.nrd：WinC&laflPMWri-XSCORE: 45Q3: Uniform Cost Searchpython pacman.py -l me

22、diumMaze -p SearchAgent -a fn=ucspcicmin. py -1 rodiunflaz -p SearchAgent -a tn"u.:s EarchAsontJ uine illicit on ucsSE-archAscntJ uz:iEg prableira typis PDsitionSearcIn-ProbLexPath found with total cast of 6S in 1 secondsFerch nades expard-Fd ： 26HFacran emerges virtirrioiis! Score ： 442Average

23、Scare： 44)DSccires：4蚣0Win RaLe：1/1(1. 00)Record:linpython pacman.py -l mediumDottedMaze -p StayEastSearchAgent1: A-L 哲坨号 让 '.工 验 七 buiir _ h_C l du -diFT 壮 juu pacjnnu, py _1 niu 11 luiDl_p i ta 丁口 L E 匕 心'11氏 3taniins： This do?s not look like a rtsular search found witL toLal eosl ot I in 0

24、.0 secDikUSearch nodes e硝融dcd； 186,HLmn =rer vi ctnri1 Sccte2 -4hriver£ga Scor ： 646. 0646. 0in Rats：VI （：, 00）Record：VinSCORE: 72python pacman.py -l mediumScaryMaze -p StayWestSearchAgentEI VA工智 12导诒、实验Ea汇41_£口I .1 in j. dj_Aa. py 1 lit*diLlitikiC.il yWd.lt! ptdf .liAg.« iLPath fixui

25、d 'zlih loltl 已口£工 of 'jE71 ?4.7?gfi4 i：L 0. C £七凸iL:So arch tiadoz oxpinod： IOSPa;man emcr-es victorious Score： ILSSrore： 4 '.S.0:;，ires:41S.0Vin Rate：1H.(1 M)Record：VinQ4: A* Searchpython pacman.py-l bigMaze-z .5 -p SearchAgent-afn=astar,heuristic=manhattanHeuristicb :TjBtK;5

26、r3i0vjrdi_Cocteseirh'：pyLhAn ptcaari-py -I bitjUize -t .6 -p Sejj ajhAgMt -a rnsiirrhjt Jruatliciifinhaliat FJuri s-i ?.Ebst iiAsent j usizie 3mrt；tian 3金心五 and rBir.，!L：=lic： nE.tir.3Ltt aiiHaur 1st i »:j.JTeareJI Uditig pfoblEi type Posi ti _uS!?Hr hPTn'L 1 ezii"a th f!?md with &

27、lt;0Bt af 210 in (4ear ch node 三 &jrp：inded: 543?3>sn-0n engr：2.E!s： ictarious! Scot归：300Scar t: 3QOi0M匚ptuh300.Qfin Rate：1J1(L 00)EecfirdVin制 M4W-xSCORE; 26Q5: Corners Problem: Representationpython pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem口:口工曾能贴&演魄”jeari?h_C&

28、amp;dg'Si.rth>i；yttu3ft pimaiL j>y -1rSti3ir'ZhAKn.tl umiw fimcion bf与，£涧hA4日( using problear type CaznersFrotiFiUl raLoid. vrt th iat j! <?Mt at 22 in 0. 0 scfihdsteiuh nscles expindeii： 252f ainan sTiErges pictcrinuE! Scots： 512阳蚯4*Scare: E11Q代解T3：512.0Vin Rite*1/1 (LOO)Rgecr

29、d:VintlrCsmera -p 施白ehAgemt -pr6b"Cn1 Pr jbl ui,泰1ciE白眸-XSCORE: 7python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblemE:1.人工自彳尼l其独4-啕m二式配过正 子ytEijfl pu.i.riurL py -1 H2d： LinCottnuu ± -p *自"亡hAg-iuffiab J a, prat =Liir；ieriPt jbl&mrSewrch/|iMnt urim fu:tia

30、R bis l£iaaixhA掌日nt UEing prctji0m tyre ComsrEPtablem 卜白dh found with lotH cost ot 105 Ln 0. 1 的七on型 为崎。h n>d««事孙，5d1篝寻 ?a-snam. &rer»ea viitaricus1 Scare: 434S-ccre 44.0舐 oce.；4M«0tin lte：l/l (1.00)M<Drd:HuC510& p BCFTidfliQ6: Corners Problem: Heuristicpython

31、pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5E：A工皆能异itA实验白打小J口由匕pacman.py "1 isdiunCmore -p ASsrC口Tnoralgant -2 0. 5F'atli fcrund th total cr-st af 106 in 0* 3 ssnndsSear-sh n&doc aKpandod： 92F'aananvictari bus1 Sesr® ： 434AverEe Scars： 0Scaras ：43i Q»in Rate：1/LLOO)Record：VLnQ7: Eating All The Dots: Heuristicpython pacman.py -l trickySearch -p AStarFoodSearchAgentA工 m 吨导咤、实航 sedts甘覆rdV”thrn 帆亡in5江-J tricJciOar<h i> iSt也r' m此时rcliAger)1 Fath found with tDlal cojt of 60 in 64+ 5 seconds工MTvh nodfifl Pitpflr.dRd