哈尔滨工业大学人工智能导论实验报告

人工智能导论实验 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 学院：计算机科学与技术学院专业：计算机科学与技术2016.12.20目录TOC\o"1-5"\h\zHYPERLINK\l"bookmark1"\o"CurrentDocument"人工智能导论实验报告1一、简介向该实验背景，方法以及目的的理解）3实验背景3实验方法3实验目的3二、方法（对每个问题的分析及解决问题的方法）4HYPERLINK\l"bookmark30"\o"CurrentDocument"Q1:DepthFirstSearch4HYPERLINK\l"bookmark33"\o"CurrentDocument"Q2:BreadthFirstSearch4HYPERLINK\l"bookmark40"\o"CurrentDocument"Q3:UniformCostSearch5HYPERLINK\l"bookmark43"\o"CurrentDocument"Q4:A*Search6HYPERLINK\l"bookmark46"\o"CurrentDocument"Q5:CornersProblem:Representation6HYPERLINK\l"bookmark49"\o"CurrentDocument"Q6:CornersProblem:Heuristic6HYPERLINK\l"bookmark52"\o"CurrentDocument"Q7:EatingAllTheDots:Heuristic7HYPERLINK\l"bookmark55"\o"CurrentDocument"Q8:SuboptimalSearch7三、实验结果（解决每个问题的结果）7HYPERLINK\l"bookmark58"\o"CurrentDocument"Q1:DepthFirstSearch7HYPERLINK\l"bookmark61"\o"CurrentDocument"Q2:BreadthFirstSearch9Q3:UniformCostSearch10Q4:A*Search12HYPERLINK\l"bookmark64"\o"CurrentDocument"Q5:CornersProblem:Representation13HYPERLINK\l"bookmark67"\o"CurrentDocument"Q6:CornersProblem:Heuristic14HYPERLINK\l"bookmark73"\o"CurrentDocument"Q7:EatingAllTheDots:Heuristic14HYPERLINK\l"bookmark76"\o"CurrentDocument"Q8:SuboptimalSearch15自动评分15四、 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 及讨论（对该实验的总结以及任何该实验的启发）15简介（对该实验背景，方法以及目的的理解）实验背景1）自人工智能概念被提出，人工智能的发展就受到了很大的关注，取得了长足的发展，成为一门广泛的交叉和前沿科学。到目前，弱人工智能取得了长足的发展，而强人工智能则暂时处于瓶颈。2）吃豆人Pacman居住在亮蓝色的世界里，在这个世界有弯曲的走廊和美味佳肴。游戏的目的就是控制游戏的主角小精灵吃掉藏在迷宫内所有的豆子，并且不能被幽灵抓到。高效地浏览世界将是吃豆人掌握世界的第一步。3）通过本学期的学习我们已经初步掌握了人工智能的基本知识，在实验中则应用这些知识使用人工智能操纵吃豆人游戏。实验方法1）在本实验中，Pacman智能体将找到通过迷宫世界的路径，既包括到达一个指定的位置，也包括高效地搜集食物。我们编辑文件search.py和searchAgents.py,编写一系列吃豆人程序，包括到达指定位置以及有效的吃豆，并将其应用到Pacman场景，完成对相关人工智能功能的完善。2）在本实验中，我们对下面8个问题进行研究，针对每个问题提出解决方法，逐步完成吃豆人游戏：Q1:DepthFirstSearchQ2:BreadthFirstSearchQ3:UniformCostSearchQ4:A*SearchQ5:CornersProblem:RepresentationQ6:CornersProblem:HeuristicQ7:EatingAllTheDots:HeuristicQ8:SuboptimalSearch实验目的1）完成实验报告中的问题，编写一系列吃豆人程序，包括到达指定位置以及有效的吃豆；2）通过分析吃豆人游戏巩固课堂上所学内容；3）复习python语言的使用。方法(对每个问题的分析及解决问题的方法)Q1:DepthFirstSearch应用深度优先算法找到一个特定的位置的豆，我们通过depthFirstSearch函数实现深度优深度优先遍历的方法是，从图中某顶点v出发:1)2)先搜索的功能。访问顶点v;3)依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历,直到图中所有顶点均被访问过为止。深度优先搜索的顺序如下图所示:j深度优先搜索在depthFirstSearch中，由于搜索过程中火重复访问到部分节点，所以需要对于每个节点设置标记，以指示该节点是否被访问过。先将每个后继节点压入搜索栈中，然后以深度优先的顺序进行搜索，判定是否符合目标状态，并将符合结果的节点放入结果集。Q2:BreadthFirstSearch应用宽度优先算法找到一个特定的位置的豆，我们通过breadthFirstSearch函数实现深度优先搜索的功能。广度优先搜索算法的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为变化。在这里注意，在深度优先搜索和广度优先搜索方法中，我们使用的图搜索算法是一样的，但是涉及到具体的数据结构却是不同的。在深度优先搜索算法中，我们使用栈进行操作，在深度优先搜索算法中，我们使用队列进行操作，如下图所示。这两种数据结构的不同之处就在于其中元素的输出次序，在深度优先搜索中需要按照压栈顺序的逆序进行搜索，咋子广度优先搜索中需要按照入队顺序的顺序进行搜索。d&fdepthFirstSearch(probtejjj):#深直优先搜索149search_stack-util,Stack()It5tdefbreadthfirstSear'ch(prc76tejn):#.!L度.优先搜索"***YOURCODEHERE*****1E9searchOueueutil.Queue()Q3:UniformCostSearch很多情况下，路径中的代价是可以改变的，在这个问题中，我们完成代价一致搜索方法。代价一致搜索，其实就是一个贪心搜索，取代扩展深度最浅的节点，代价一致搜索扩展的是路径消耗最低的节点n。如果所有单步耗散都相等的话，这种算法就和广度优先搜索算法是一样的。不过，这样在扩展到一个具有能返回到同一状态的零耗散行动的节点时就会陷入无限循环。在uniformCostSearch函数中，我们计算每条路径的总代价，将总代价作为优先级进行搜索，待搜索序列存储于队列中。对于每个节点，使用代价函数getCostOfActions计算其所产生的代价，并依次作为搜索的优先级进行搜索。同样的，对于每个节点添加是否被访问的标记。Q4:A*SearchA*算法是一种静态路网中求解最短路最有效的直接搜索方法，也是许多其他问题的常用启发式算法，对代价一致搜索算法进行了改进，加入了一个估计代价ho公式表示为：f(n)=g(n)+h(n),其中f(n)是从初始状态经由状态n到目标状态的代价估计，g(n)是在状态空间中从初始状态到状态n的实际代价，h(n)是从状态n到目标状态的最佳路径的估计代价(对于路径搜索问题，状态就是图中的节点，代价就是距离)。在本实验中，我们使用曼哈顿距离作为启发函数。在aStarSearch函数中，我们首先搜索具有最低组合成本和启发式的节点。类似于问题三，我们计算每个节点的代价，并以此为依据搜索产生结果集，在搜索的过程中，还需要标记节点是否已经被访问过。Q5:CornersProblem:Representation找到所有的角落，在角落迷宫的四个角上面有四个豆，通过这个函数找到一条访问所有四个角落的最短的路径。在CornersProblem类中，我们使用_init_函数存储墙壁的位置，吃豆人的起点和角落位置，定义新的函数getStartState用于获得节点起始状态，isGoalState函数判断当前节点是否为目标节点，getSuccessors函数返回后继状态，所需的操作以及代价，getCostOfActions函数计算动作序列所需的代价。查找后继节点时，在四个方向一次遍历，使用directionToVector移动位置，如果没有墙，则把下一个的状态，动作，花费的步数加入下一节点Q6:CornersProblem:Heuristic构建合适的启发函数，完成问题5中的角落搜索问题。在问题五使用的CornersProblem类中定义cornersHeuristic函数，为角落问题构造启发函数。在cornersHeuristic函数中使用了GetNextNodes函数获取下一个节点，isGoal函数判断是否为目标。Q7:EatingAllTheDots:Heuristic用尽可能少的步数吃掉所有的豆子。这个问题利用之前A*算法可以很容易找到解，此种方法在这里不再详述。下面在FoodSearchProblem类中定义函数foodHeuristic,构建合适的启发函数完成豆子搜索（启发式）问题。Q8:SuboptimalSearch次最优搜索，定义一个优先吃最近的豆子的函数，以此来提高搜索速度。补充AnyFoodSearchProblem目标测试函数，并在ClosestDotSearchAgent当中添加findPathToClosestDot函数，用于寻找最近的豆子。三、实验结果（解决每个问题的结果）Q1:DepthFirstSearchpythonpacman.py-ltinyMaze-pSearchAgentE\search_Code\5e=irch>r'ythonpadnan.py_1tinyMaze-pSearcTiAeentESearchAgent]usinsfunctionstSearch[SearchAgent]usingr>rablemtypePo^itionSearchPrcbleriPathfoundwithtotalcostof10in0.0secondsSearchnodesexpanded：20Pacnanemergesvictorious!Score:50CAverageScore：500.0Scores:500.0IinRate：1/1(L00)Record:TinSCORE:SOOpythonpacman.py-lmediumMaze-pSearchAgentE:\人工智能■导论E实验arch_Code\searchxp/thonpa^man.py-1nediuiriMaEe-pEeareJrA^erit[SearchA^ant]usir^g1metiandapthFirsTSearch[EearchAg&ntJusingprcblantypePositicnSsarchProbierPathfoundwithtotalcostof130in0.CsecondsSearchnDleseiparded:长2PaciTAnmm&rg旦宫victorions?Score:，£0A^eragt!jt-ui'-s:38(,0Scores'381.0VinRito：1/1(1.00)Record;Winpythonpacman.py-lbigMaze-z.5-pSearchAgentE:智能导论、麦验k曲drch_Culit：\seai'cliJpvthunracnan.py~1bigMaze_z>5-pSearchAgent:;SeaicliAgHiit]ijsltig£LUiuliuiidtjpiSydicl.[.LtdJ-cllAgbillt]iJoillgjrublhiilLWKPus!;ioiiuedicliTrlLIeiLrathfoundwithtotaltostcf210in0.0secondsCearchiiodesespiLided：569Pacrnancncrsoavictorious!Score300AveragesScore：300*0Scarce:300+DWinRato：1/1(1.00)WinSCORE:*8Q2:BreadthFirstSearchpythonpacman.py-lmediumMaze-pSearchAgent-afn=bfsE八人工智能导至l实筮犊健山_弓皿thentiaciua.n_py=1vniadLLurN^z^S巨archAgent-afn-^bfslut-areJriAgwijil]口#ir岫fUrielionbftrCearchAgADl]usingproblemiiyr'ePositianSearchfroblbhPathf™mdwithtotalco&tof6?in0..0secondsSe^rdhnode-sespanded；269PacrnaneirerfiesvictoriauF!Ecnre；442TOC\o"1-5"\h\zAverageScore：442.0Scoros：442.0VinRa«：L/L(1.00)Rflcard：Vin为WWgiSCORE:-30pythonpacman.py-lbigMaze-pSearchAgent-afn=bfs-z.5E:W工指能导论\密3毗北_。品…pjLjmn-p>'1tdgJlaTk!■Se1'_hAgeiita.&fUfLctiDtibfa.Saar:hASLTitJucinjc;prcblzmtvp。PositiDnSaarc^ProbicmFathfcun^viditotalcostof210in。0secondsnndfisindpri：Patmanuictoricus!Sccrm：30CAvsra^EStorm：3DO.)Scores：3DO.DFinRate：1/1(1.00)Rb-.nrd：WinSCORE:45Q3:UniformCostSearchpythonpacman.py-lmediumMaze-pSearchAgent-afn=ucsI.：VvIeBtK^feXEearch^CcicteVsearch^ythjinpcicmin.py-1rodiunflaz^-pSearchAgent-atn"u.:s^EarchAsontJtiringillicitonucs[SE-archAscntJuz:iEgprableiratypisPDsitionSearcIn-ProbLexPathfoundwithtotalcastof6Sin1secondsFe^rchnadesexpard-Fd:269Facranemergesvirtirrioiis!Score:442AverageScare：44k.DSccires：44EDWinRH1/1(1.00)Record:lin..SCO£tE:39pythonpacman.py-lmediumDottedMaze-pStayEastSearchAgent1:\A-L苜Ei&导\ktrar.h_Cldu」di。一pytliuripacjnnu,py-1niu11luiDjt.；uJlgj-pitafUdgl£ej_l七it-^aniins：Thisdo?snotlooklikeartsularsearchbam,whfoundwitLtoLaleoslotIin0.0secDikUSearchnodesCKp^ijdcd；186■Jn*_niin^™=r^ervictnri1Sccte2-4hTOC\o"1-5"\h\zriver£gaScor^:646.0Scares'&46.0^inRats：VI（：.00）Record:VinSCORE:72pythonpacman.py-lmediumScaryMaze-pStayWestSearchAgentEt工智能导论皿^检诂BardijCDdwL.earcli^pythnipkcbiclpyTEBdtLinSraTTffaie_pStayWestSHrchAg.tfitPathfixuidzlihirOl^tldo±i口[花71947986。i:.0.0NmjiLijoarchtiaclozoxpin^od：IOSPa;manemcr-esvictoriousScore：ILSTOC\o"1-5"\h\zkyerageScore：4?S.0:;'ires:41S.0VinRate：1H(1DO)Record:NMTH<.”8*PdEMQ4:A*Searchpythonpacman.py-lbigMaze-z.5-pSearchAgent-afn=astar,heuristic=manhattanHeuristicb:\^T^j[Bt^K;\5r3i\0vjrdi_Cocte\seir^h'：pyLhA]nptcaari-py-IbitjUize-t.6-pSejjajhAgMt-arn^^siirrhjtJruatlic^ifinhaliatFJ^uris^-i?.EbstiiAsentjusizie3mrt；tian丑以点工andrBifizlic：nE.tir.3LttaiiHaur1sti•:j.JTeareJlA^etiI]UditigpfobldtitypePositi_uS!?Hr^hPfnL1ezii"athtEmdwithtct»l<0Btaf210infk4弓颗"廊营earchnode三&jrp：±nded:543?3>snHnengr：2.E!s：^ictarious!Scot至300TOC\o"1-5"\h\zScart:3QOi0&匚bum300.Q/inRate：1J1(L00)Eecfird^VimQ5:CornersProblem:Representationpythonpacman.py-ltinyCorners-pSearchAgent-afn=bfs,prob=CornersProblemyPbcqutlpy-1'Se^rchAKiintiusi-iur[EMr?hAfeentJusingprobleirtyi?曰CaznersFroti™r°aI±lrciLo'id.vrtthtatj!i^St占r*m北秘rcliAger)+'athfoundwithtotalcostof60in44+SsecondsI/irirchnodfiflPitpflr.dRd;41^710-mF：」「二门一i-i】=^c-tp：STJUv?rageScore：570LlEccres：570.0finRaterVI(L.DO)R&cord：Win添CGIS3PacmariXQ8:SuboptimalSearchpythonpacman.py-lbigSearch-pClosestDotSearchAgent-z.5,:'A,工智能#论l具验\兰史占:r.jIHa\itdiJpyLhonparitian.py1bi或ipClcearcL_£dir:hAgcnrluth;functionri ppt 关于艾滋病ppt课件精益管理ppt下载地图下载ppt可编辑假如ppt教学课件下载triz基础知识ppt EiFirrtScarc?[Smr崩i叫problenitypeP口j11ioriSTai<}]fr1eir.raihf'Diindurithcast350.Pacmaneirer^esvictorious!S-ore：2：60TOC\o"1-5"\h\zScore：2360-0性9盹盐2360.0yinEire：1/1(LOO)KiecaEd:¥in7诚CS18$Patman—□XSCORE:279自动评分Finishedat13:42:45Provisionalgrades□nQuestionqlq2q3q4q5q6q723333343///^/////23333353otal:26/25四、总结及讨论（对该实验的总结以及任何该实验的启发）A*算法四种搜在这个实验中，我们对深度优先搜索、广度优先搜索、代价一致搜索和索方法进行了python代码实现，对这四种方法有了进一步的了解。与深度优先搜索和广度优先上搜索方法相比，代价一致搜索方法的效率更高，在代价一致上搜索方法失效时，等同于广度优先搜索。A*算法是最有效的直接搜索算法，使用公式进行预处理，这样能够省略大量不必要的搜索路径，提高了效率。在启发式搜索中，估价函数非常重要，准确的估价函数能够增大搜索函数的效率并且具有相当高的准确性。由此，在启发式搜索中对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。在本次实验中使用了大量python语言中的类，对之前的python知识有了很大的扩展。