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

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 6Q7: Eating All The Dots

2、: 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 Search 1.5自动评分 1.6四、总结及讨论对该

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

4、cman智能体将找到通过迷宫世界的路径，既包括到达一个指定的位置，也包括高效地搜集食物。我们编辑文件，编写一系列吃豆人程序，包括到达指定位置以 及有效的吃豆，并将其应用到Pacman场景，完成对相关人工智能功能的完善。2在本实验中，我们对下面8个问题进行研究，针对每个问题提出解决方法，逐步完成吃 豆人游戏：Q1: Depth First SearchQ2: Breadth First SearchQ3: Un iform Cost SearchQ4: A* SearchQ5: Corners Problem: Represe ntati onQ6: Corners Problem: Heuri

5、sticQ7: Eat ing All The Dots: HeuristicQ8: Suboptimal Search3. 实验目的1完成实验报告中的问题，编写一系列吃豆人程序，包括到达指定位置以及有效的吃豆;2通过分析吃豆人游戏稳固课堂上所学内容；3复习python语言的使用。方法对每个问题的分析及解决问题的方法Q1: Depth First Search应用深度优先算法找到一个特定的位置的豆，我们通过depthFirstSearch函数实现深度优先搜索的功能。深度优先遍历的方法是，从图中某顶点v出发：1)访问顶点V；2)依次从v的未被访问的邻接点出发， 的顶点都被访问；对图进行深度优先遍

6、历； 直至图中和v有路径相通3)假设此时图中尚有顶点未被访问，那么从一个未被访冋的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。深度优先搜索的顺序如以下图所示:在depthFirstSearch中，由于搜索过程中火重复访问到局部节点，所以需要对于每个节点设 置标记，以指示该节点是否被访问过。先将每个后继节点压入搜索栈中，然后以深度优先的顺序进行搜索，判定是否符合目标状态，并将符合结果的节点放入结果集。Q2: Breadth First Search应用宽度优先算法找到一个特定的位置的豆，我们通过breadthFirstSearch函数实现深度优先搜索的功能。广度优先搜索算法的

7、思想是：从图中某顶点v出发，在访问了 v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的 顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，那么需要另选一个未曾被访问过的顶点作为新化。在这里注意，在深度优先搜索和广度优先搜索方法中，我们使用的图搜索算法是一样的，但是涉及到具体的数据结构却是不同的。在深度优先搜索算法中， 我们使用栈进行操作， 在深度优先搜索算法中，我们使用队列进行操作，如以下图所示。这两种数据结构的不同之处就在于其中元素的输出次序，在深度优先搜索中需要

8、按照压栈顺序的逆序进行搜索，咋子广度优先搜索中需要按照入队顺序的顺序进行搜索。147 d&f depthFirstSearch(probtejjj):148 井深应优先搜索149search_stack - uti匚k()It5 t def breadthfirstSear'chtpro/jtejn): 16L哎.优先搜索187 "* YOUR CODE HERE *1881E9searchOueue util.Queue()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次最优搜索，定义一个优先吃最近的豆子的函数，以此来提高搜索速度。补 充 An yFoodSearchProblem目标测试函数，并在 ClosestDotSearchAge nt 当 中添加fin dPathToClosestDot函数，用于寻找最近的豆子。三、 实验结果解决每个问题的结果Q1: Depth First Searchpyth on pa

14、cma n.py -l tiny Maze -p SearchAge ntEsearch_Code5e=irch>r'ython padnan. py _1 tinyMaze -p SearcTiAeentESearchAerit us ins func tianst SearchSearchAgent using r>rablem tvpetlcinEg自rchPrcblriPa.th found with total cost of 10 in 0. 0 secondsSearch nodes expanded： 20Pacnan emerges victorious!

15、 Score: 50CAverage Score: 500.0Scores:500.0I in Rate：1/1(L 00)Record:Tin|总 Ciiaa 知 cm.SCORE: 500pyth on pacma n.py -l mediumMaze -p SearchAge ntE： 入工智能导论实脸 ar ch_Co de s e ar chp/thon paman. py -1 rnediuirMaEe -p EearelrAerLt SearchAant usirg i me tian dap thFirsiSe arch.EearchAg&ntJ using prcbl

16、an type Posi t i cnSsar chPr obi errath found with tutai cost of 130 in 0.C secondsSearch nDles eiparded:氐2PiciTAn ejnrga? victoricns? Score: 5E0Aeragt! jk,urt!: 380, 0Scores'38Q. 0VLn Rito：1/ (1.00)Record;pyth on pacma n.py -l bigMaze -z .5 -p SearchAge ntE:A 二智 s a Arch _Cu lie ear y thai l t-

17、'atiiiaij. py -1. 5 p Sea-i'chAeurit=StciicliAgHiit jsltig £luiuLluii dtjp lliflrs t-Sudixl.LctdJ. ullAgKllt iJolhg pl'ublhiiu"uwi ; i oiiu e di cl iTr l LI eiLPath found witti total tost cf 210 in 0. 0 second*Gear ch mdes eKpandei： 569Pacrnari cncrcoa victorious! Score: 300Avc

18、rocScore： 200,Scarce：300+DWin Rato：1/1(1.00)Roccxd：WinQ2: Breadth First Searchpyth on pacma n.py -l mediumMaze -p SearchAge nt -a fn=bfsE: 人工彗能导尬 l实?鈣then tiaciua.n_ py 三 1 vniadLLurNz 三p S&archAgent fn-bfslut-areJiAgwijilfun亡目门 bf trCearchAgADl using problemi iyr'e Posi t ianSearcHProbl bhP

19、ath found total co&t of 6? in 0. 0 secondsSerdh node-s espanded； 269Pacrnan eirerfies victoriauF! Ecnre； 442AverageScore： 442. 0Scoros：442. 0Vin Ra«：L/L (1.00)Raard:Vinpyth on pacma n.py -l bigMaze -p SearchAge nt -a fn=bfs -z .5E:工暫±earch_C DdB sear eh>py thon pdLjmn- p>' 1

20、tdS e 1' _ hAg ei it a £ti-l'fs "i . bfUactiDti bfa.ScarhAscnt ucinjc; pre bl zm tvpo Pc i xi znSo arcPr obi z mFath feun vidi totL cost of 210 in Q* 0 secondsSatc! nnrJfis ftp indpri：斤2Pacman eniiT&ms viciorious! Seers; 300AvsraES:or3： 300iDScores：300.DJin Rate：J/l(1.00)Rffcnr

21、d:Wincsiaap»nSCORE: 45Q3: Uniform Cost Searchpyth on pacma n.py -l mediumMaze -p SearchAge nt -a fn=ucsI. ： VvIeiSt XfeXEearchCcicteVsearchythjin pcicminP7 -1 rodiunflaz -p EearchAgent -a tn"u.:s SEQrchAsontJ uine function ucsSE-archAscntuNm prableira tms PDsitionSearcIn-ProbLexPath found

22、with total tosrt of 6S in 1 secondsFerch nades expard-Fd: 269Facran emerges virtirrioiis! Score: 442Average Scare： 44A.DSccires：44.0Win RaLe：1/1(1. 00)Record:linSCO£tE: 39pyth on pacma n.py -l mediumDottedMaze -p StayEastSearchAge nt1: A-L 哲 直屯异 I £ ktrar - h_C l du=di J . py tliuri pacjan

23、u, py -1 mu 11 luiDt. ；u 山辽匕 -p i ta vH 皿 l S e u陶3 it- aniins： This do?s not look like a rtsular search bamfound witL toLal eosl ot I in 0.0 secDikUSearch nodes CKpijdcd； 1S&Jn*_niin =rer vi ctnri 1 Sccte2 -4hriver£gaScor: 646. 0Scares'&46. 0in Rats：VI ：. 00Record:VinSCORE: 72pyth

24、on pacma n.py -l mediumScaryMaze -p StayWestSearchAge nt(» 1)in0 'OOE0!0OE:pjnay :日冋uIfl：=i_£n 咄:SIDSrQQE ;ajam£ jsnoijci|i saEiaja hikii? j6fg :戸口credit serpcru qzxed 砂42柚 Ft Ul却 *sa> E疋* MIXA 吟心丄 >4IMiqaqojnam TTSa J a4Ai maTqDHd 9trim: Iisrnstrem"jLi'aai I'Ti

25、sii-TLar put 工&口电 uDiixm:月口号sn iua'3：xsa-as:t!T.O1E1U4 iria&rj? irag tf- j' j- 苗冋q卜 初 丸科叩叫1皿 啪玄阳珂碑。门丹破叭哦壬、抚皆第联工*：却orsu nHUEl 冋 UEiuaqs!noi|'EiSE=uje- ;ua6vi|0Jeas d- g- z-aze|/|6!q|-Adueiuoeduo屮人dMOJees N :K)uPUPq魂丼了尽uN:卩蜩(oti) in:旳明町习u 'STt：EajEnD30 'Sih血j:制git ：3M5S ET&

26、#187;TJO45tA SczIMO UBB：M got Topurdito cop du ho j?FPEMY 0 0 巩 f9®6Aol2.89 J£Pld xjiy. piraj1 LT冃 yT_- jph§工阪sXp-).g d- exp評jnip 冃u讯hw討 W叩njFH?he珥彈迫电占泄岳工¥':团SCORE： 261Il |SPI1 1MlQ5: Corners Problem: Representationpyth on pacma n.py -l tinyCorners -p SearchAge nt -a fn=bfs,p

27、rob=Cor nersProblem1二皆匸 3实脸、BEHFfhjZod&l匪ylhe pbcuuil -1 tlnyCl賞 15*0 -p SearcbiAgerjt -h. tn- bfs, j>Tob=C uTir P丄 ibl"SercliAKenti usi-iur fimction bis| _ g&aGhA 鼻日nt us i ns probLear typ曰 CccTLersF robl Ial±L rciD'id. wlth latjl erat at 2S in 0* 0 直色亡血白血expanded.： 22Qcina

28、n sTTErgBs pictorinuE! Scure： 512£亡arm: E12.0畸 or 語：512.0in Rateij/1 (1- 00)e&Qrd:Vin霏亡問血-xSCORE: 7pyth on pacma n.py -l mediumCor ners -p SearchAge nt -a fn=bfs,prob=Cor nersProbleml:.3Lt.a.ar-rCDdeediFch ：,j>yth jh pui.riurL. py -1 肥ii： liflCsmiEi l； -p Se-ir chA«rLi 由prat Ciirrit

29、rPi dblemrSBrch?,wntJ ueifl=: fu:tian bfsISsirch.sent using :prctjieE tyre ComsrEPtab 1 ent邛 th f ound with Lcital cost ot 1.06 Ln 0. 1 抽芒血於淪dull n>d#« s-XT'iiKisd 1 篝$ererg.es vitoricus1 畧c：口re: 434'.V&lft Sco-9： 4M4.0丸OTEi：4M< 0riti Rate:l/l (1. 00)Ftacd:HnSCORE: -17Q6: Corn

30、ers Problem: HeuristicE：A工首'龍异0 arch_C dcXsaar cti>pythan pieman, py -1 mcdlunCorrifirs -r> AStarC omarffAB ant -a 0. 5Tsdi lu'jijd yflth tuidLl gt'H；t a£ 106 111 Q. j 詛呂emiL血rejirch nodes Bpandrj：Facman iwrgss vitoriow! Score： 434Aver stgScare: 434. 0Scores:434 0VLn te:1/1 <1.00)RwcordlVLn定 LSlfc PaznwnSCORE: 17Q7: Eating All The Dots: Heuristicpyth on pacma n.py -l trickySearch -p AStarFoodSearchAge ntF- - AHIts总冬ula Kr ch_g dt s. ma r chythm g总戸tsy 丄 tri. CJCyr.:盅 rchh.A £ 曲氏 3?;mAQ.1Agerdlu-h foundvir*h