哈工大人工智能導(dǎo)論試驗(yàn)報(bào)告

1、哈工大人工智能導(dǎo)論實(shí)驗(yàn)報(bào)告作者: 日期:人工智能導(dǎo)論實(shí)驗(yàn)報(bào)告學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)2021.12. 2 0目錄人工智能導(dǎo)論實(shí)驗(yàn)報(bào)告 3一、簡(jiǎn)介對(duì)該實(shí)驗(yàn)背景,方法以及目的的理解51實(shí)驗(yàn)背景5 2實(shí)驗(yàn)方法5 3實(shí)驗(yàn)?zāi)康?二、方法對(duì)每個(gè)問題的分析及解決問題的方法6Q1: Depth First Search 6Q2: Breadth First Search 6Q3: Uniform Cost Search 7Q4: A* Search 8Q5: Corners Problem: Represe ntati on 8Q6: Corners Problem: Heuristi

2、c 8Q7: Eating All The Dots: Heuristic 9Q8: Suboptimal Search 9三、實(shí)驗(yàn)結(jié)果解決每個(gè)問題的結(jié)果 9Q1: Depth First Search 9Q2: Breadth First Search 11Q3: Uniform Cost Search 12Q4: A* Search 1.4Q5: Corners Problem: Represe ntati on 1.5.Q6: Corners Problem: Heuristic 1.6.Q7: Eating All The Dots: Heuristic 16.Q8: Suboptim

3、al Search 17自動(dòng)評(píng)分17四、總結(jié)及討論對(duì)該實(shí)驗(yàn)的總結(jié)以及任何該實(shí)驗(yàn)的啟發(fā) 171.1)2)3)2.1)2)3.1)2)3)簡(jiǎn)介對(duì)該實(shí)驗(yàn)背景,方法以及目的的理解實(shí)驗(yàn)背景自人工智能概念被提出,人工智能的開展就受到了很大的關(guān)注,取得了長(zhǎng)足的開展,成為 一門廣泛的交叉和前沿科學(xué).到目前, 弱人工智能取得了長(zhǎng)足的開展,而強(qiáng)人工智能那么 暫時(shí)處于瓶頸.吃豆人Pacm a n居住在亮藍(lán)色的世界里,在這個(gè)世界有彎曲的走廊和美味佳肴. 游戲的并且不能被幽靈抓到.高在實(shí)驗(yàn)中那么應(yīng)用這些知識(shí)目的就是限制游戲的主角小精靈吃掉藏在迷宮內(nèi)所有的豆子, 效地瀏覽世界將是吃豆人掌握世界的第一步.通過本學(xué)期的學(xué)習(xí)我

4、們已經(jīng)初步掌握了人工智能的根本知識(shí), 使用人工智能操縱吃豆人游戲.實(shí)驗(yàn)方法在本實(shí)驗(yàn)中,P acman 智能體將找到通過迷宮世界的路徑,既包括到達(dá)一個(gè)指定的位置,也包括高效地搜集食物.我們編輯文件sear ch . py和searchAge n t s.p y,編寫一系列吃豆人程序,包括到達(dá)指定位置以及有效的吃豆,并將其應(yīng)用到 Pacm an場(chǎng)景,完成對(duì)相關(guān)人工智能功能的完善.在本實(shí)驗(yàn)中,我們對(duì)下面8個(gè)問題進(jìn)行研究,針對(duì)每個(gè)問題提出解決方法,逐步完成吃豆人游戲：Q1: Dep t h Fir s t S ear chQ 2： Breadth First S ea r chQ3: Unifo r

5、m Cost Sea r c hQ 4 : A* Sea rc hQ5: Co rner s Problem : Repre s en ta tio nQ6: Corne r s Probl em: H eu risticQ7: Eat i ng A II The Dot s : He uristi cQ8: Subo p t ima l Search實(shí)驗(yàn)?zāi)康耐瓿蓪?shí)驗(yàn)報(bào)告中的問題,編寫一系列吃豆人程序,包括到達(dá)指定位置以及有效的吃豆 通過分析吃豆人游戲穩(wěn)固課堂上所學(xué)內(nèi)容；復(fù)習(xí)pytho n語言的使用.方法對(duì)每個(gè)問題的分析及解決問題的方法Q1: De pt h F i r st Se ar ch

6、應(yīng)用深度優(yōu)先算法找到一個(gè)特定的位置的豆,我們通過depthFirstS ear ch函數(shù)實(shí)現(xiàn)深度優(yōu)先搜索的功能.深度優(yōu)先遍歷的方法是,從圖中某頂點(diǎn)v出發(fā)：1訪問頂點(diǎn)V；2依次從v的未被訪問的鄰接點(diǎn)出發(fā),對(duì)圖進(jìn)行深度優(yōu)先遍歷；直至圖中和v有路徑相通的 頂點(diǎn)都被訪問；3假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問, 那么從一個(gè)未被訪問的頂點(diǎn)出發(fā),重新進(jìn)行深度優(yōu)先遍歷,直到圖中所有頂點(diǎn)均被訪問過為止.深度優(yōu)先搜索的順序如下列圖所示 ：深戟憂先捜索在d e p thFir s t S earc h中,由于搜索過程中火重復(fù)訪問到局部節(jié)點(diǎn) ,所以需要對(duì)于每個(gè)節(jié)點(diǎn) 設(shè)置標(biāo)記,以指示該節(jié)點(diǎn)是否被訪問過. 先將每個(gè)后繼節(jié)點(diǎn)壓入

7、搜索棧中,然后以深度優(yōu)先的 順序進(jìn)行搜索,判定是否符合目標(biāo)狀態(tài),并將符合結(jié)果的節(jié)點(diǎn)放入結(jié)果集.Q 2 : B readth F i r s t Sear c h應(yīng)用寬度優(yōu)先算法找到一個(gè)特定的位置的豆,我們通過breadthF irstS ea rch函數(shù)實(shí)現(xiàn)深度優(yōu)先搜索的功能.廣度優(yōu)先搜索算法的思想是：從圖中某頂點(diǎn)v出發(fā),在訪問了 v之后依次訪問v的各個(gè)未曾訪問過的鄰接點(diǎn),然后分另以這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn),并使得“先被訪問的頂 點(diǎn)的鄰接點(diǎn)先于后被訪問的頂點(diǎn)的鄰接點(diǎn)被訪問,直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都IIJ和層軸層只是搜索的次序發(fā)生T I,但,在深Q3: Un iform C

8、ost S e arc h很多情況下,路徑中的代價(jià)是可以改變的,在這個(gè)問題中,我們完成代價(jià)一致搜索方法.被訪問到.如果此時(shí)圖中尚有頂點(diǎn)未被訪問,那么需要另選一個(gè)未曾被訪問過的頂點(diǎn)作為新的起始點(diǎn),重復(fù)上述過程,直至圖中所有頂點(diǎn)都被訪問到為止.如下列圖：在這里注意,在深度優(yōu)先搜索和廣度優(yōu)先搜索方法中,我們使用的圖搜索算法是一樣的 是涉及到具體的數(shù)據(jù)結(jié)構(gòu)卻是不同的.在深度優(yōu)先搜索算法中,我們使用棧進(jìn)行操作 度優(yōu)先搜索算法中,我們使用隊(duì)列進(jìn)行操作,如下列圖所示.這兩種數(shù)據(jù)結(jié)構(gòu)的不同之處就在于其中元素的輸出次序, 在深度優(yōu)先搜索中需要根據(jù)壓棧順序的逆序進(jìn)行搜索,咋子廣度優(yōu)先搜索中需要根據(jù)入隊(duì)順序的順序進(jìn)

9、行搜索.在br ead thFirstS e ar ch中,大體的搜索思路與深度優(yōu)先算法 了變化.147148149150def depthFirstSearch(probLerti)searchstack = util»Sta匚k()searchOueueuti1Oueue()IdS t 6&f breadthfirstSearchtprotLein)186187108189VOUR CODE HERE *代價(jià)一致搜索,其實(shí)就是一個(gè)貪心搜索取代擴(kuò)展深度最淺的節(jié)點(diǎn),代價(jià)一致搜索擴(kuò)展的是路 徑消耗最低的節(jié)點(diǎn) n.如果所有單步耗散都相等的話,這種算法就和廣度優(yōu)先搜索算法是一樣 的

10、.不過,這樣在擴(kuò)展到一個(gè)具有能返回到同一狀態(tài)的零耗散行動(dòng)的節(jié)點(diǎn)時(shí)就會(huì)陷入無限循 環(huán).在u n iform Co st Searc h函數(shù)中,我們計(jì)算每條路徑的總代價(jià),將總代價(jià)作為優(yōu)先級(jí) 進(jìn)行搜索,待搜索序列存儲(chǔ)于隊(duì)列中.對(duì)于每個(gè)節(jié)點(diǎn),使用代價(jià)函數(shù)ge tC ost O fAc t ions計(jì)算其所產(chǎn)生的代價(jià),并依次作為搜索的優(yōu)先級(jí)進(jìn)行搜索.同樣的,對(duì)于每個(gè)節(jié)點(diǎn)添加是否被訪問的標(biāo)記.Q 4 : A 伙 SearchA*算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法,也是許多其他問題的常用啟發(fā)式算法,對(duì)代價(jià)一致搜索算法進(jìn)行了改良,參加了一個(gè)估計(jì)代價(jià) h.公式表示為：f (n)=g(n)+ h

11、(n ),其中f (n)是從初始狀態(tài)經(jīng)由狀態(tài)n到目標(biāo)狀態(tài)的代價(jià)估計(jì),g (n)是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實(shí)際代價(jià),h(n )是從狀態(tài)n到目標(biāo)狀態(tài)的最正確路徑的估計(jì)代價(jià)(對(duì)于路徑搜索問題,狀態(tài)就是圖中的節(jié)點(diǎn),代價(jià)就是距離).在本實(shí)驗(yàn)中,我們使用曼哈頓距離作為啟發(fā)函數(shù).在aSta rSea rch函數(shù)中,我們首先搜索具有最低組合本錢和啟發(fā)式的節(jié)點(diǎn).類似于問題三,我們計(jì)算每個(gè)節(jié)點(diǎn)的代價(jià),并以此為依據(jù)搜索產(chǎn)生結(jié)果集,在搜索的過程中,還需要標(biāo)記節(jié)點(diǎn)是否已經(jīng)被訪問過.Q5: Corne r s P r ob 1 em: Representation找到所有的角落,在角落迷宮的四個(gè)角上面有四個(gè)豆,通

12、過這個(gè)函數(shù)找到一條訪問所有四個(gè)角落的最短的路徑.在Co r nersPr o b 1em類中,我們使用 i n i t_函數(shù)存儲(chǔ)墻壁的位置,吃豆人的起點(diǎn)和角 落位置,定義新的函數(shù)g et S ta r tSt ate用于獲得節(jié)點(diǎn)起始狀態(tài),is Go alS t a t e函數(shù)判斷當(dāng)前節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn),getSucc e ssors函數(shù)返回后繼狀態(tài),所需的操作以及代價(jià),getCost O fA cti o ns函數(shù)計(jì)算動(dòng)作序列所需的代價(jià).查找后繼節(jié)點(diǎn)時(shí),在四個(gè)方向一次遍歷,使用di re ct i onT o V ect or移動(dòng)位置,如果沒有 墻,那么把下一個(gè)的狀態(tài),動(dòng)作,花費(fèi)的步數(shù)參加下一

13、節(jié)點(diǎn)Q6 : Corners Pr o b 1 e m : H e ur i stic構(gòu)建適宜的啟發(fā)函數(shù),完成問題5中的角落搜索問題.在問題五使用的 Corners P ro b lem類中定義cor nersHeur i stic函數(shù),為角落問題構(gòu)造啟發(fā) 函數(shù).在 corne rs He u r is tic函數(shù)中使用了 GetNex t Nodes函數(shù)獲取下一個(gè)節(jié)點(diǎn),i sG o al函數(shù)判斷是否為目標(biāo).Q7: Eat i n g All T he Dots: H e uri Stic用盡可能少的步數(shù)吃掉所有的豆子.這個(gè)問題利用之前A*算法可以很容易找到解,此種方法在這里不再詳述.下面在F

14、oodSearchPr o b 1 em類中定義函數(shù)f o o dHe u r i stic,構(gòu)建適宜的啟發(fā)函數(shù)完成 豆子搜索啟發(fā)式問題.Q8 :Sub o ptimal Se a rch次最優(yōu)搜索,定義一個(gè)優(yōu)先吃最近的豆子的函數(shù),以此來提升搜索速度.補(bǔ)充 An yFoodSea rchP roblem 目標(biāo)測(cè)試函數(shù),并在 Closest Do tSe arch A gent 當(dāng)中添 加fi n dPathT o Clo se st Do t函數(shù),用于尋找最近的豆子.三、 實(shí)驗(yàn)結(jié)果解決每個(gè)問題的結(jié)果Q 1 : D e pth Firs t Sea r c hpy t h o n pacman.

15、 p y -l tinyMaz e -p S ea rc h A ge n tEsearch_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 victoriou

16、s! Score: 50CAverage Score: 500.0Scores:500.0I in Rate：1/1(L 00)Record:Tinpy t hon pa c man.py -l m e diumM a ze -p SearchAgentp y th o n pac m a n . pl b igM a ze -z . 5 - p Se a r chA gen tp Stm'chAfibuiTcore: 300E： 人工智能昌論、實(shí)驗(yàn).弓eWeszrch'pythciti paman. py -1 rnediuirMaEe -p EearelrAerLtSear

17、chAant LsarchAj&rit.rath foundSearch nDlesPacrrAn ejnrga?Aeragt! jk,utrt!:Scores'Win Rats：Record:usirg i me tian dap thFirsiSe archusing fjrcblefnPol t i cnScarchProbi snwith tn tai cost of 130 in 0. C seconds eiparded: 1()2victoricns? Score: 5E0380.03SQ.01/1 (1.00)Win_CuiJfc!b!arclL：-L'

18、V thou t-'aciLau. py *1 bij=;MiZ ii dtjp tJifirstStidi'Ll.L type uwi ; i oiiu e di cl iTr l LI eiLof 210 in 0. 0 secondaijsitig LluiuLl ijriins pruble. tLi total tost expanded： 5SO i3 victorious :200. J300. D 1/1 (1. 00) Win.fr|i',11r*SCORE: 69MiSCORE: 58Q2: B r eadth Firs t Sear c hpyt

19、h o n pacman.py 1 medi um Maze p Se a r c hAgent- a f n = b f sE: 扎丄智耳任導(dǎo)二侖 '實(shí)驗(yàn)、*沙l±i_C _山 - earc h>pyBJ lut l Ipiaciii3.n_ py 三 1 vmadLiurNdz 三p S&archAgent fn-bfs t*sreJiAgwtji I ftn亡目門 bf tSearchAgADl using probl 'em type Posit ianSeaixHP 匚 obi anPath ffflind totail co&t of

20、 &8 in 0. 0 secondsSe«dh node-s expanded； 269Pacrnan eirerfies victoriauF! EcnrE： 442AverageScore： 442. 0Scoros：442. 0Vin Ra«：L/L (1.00)Raard:VinSCORE: -30p ython pacm a n.py-l b i g M aze -p Sea rc hAgen t -a fn = bf s -z .5E -工暫軌耳 £ 實(shí)險(xiǎn)'e-ar _h_C 匚 d歸 siearch>py than pi Li

21、kin- p>' 1 td! Sel' -hAgefit a £ti-l'fs "i . &£=str討血1 furiGtiDti bfa.Saar:hASLTitJ uc 血 prcblzm tvpo Pos i ti DnSa arcPr obi c mFath fcun viih total cost of 210 in Q* C1 secondsnndfis indpd： *52 JPaman &nr9S uictoriQUs! Seers; 30?AvsraE£=orm : 3 DO.?Scores

22、:3 DO.Dfin Rate：J/l(1.00)Re-, nrd：WinSCORE: 45Q 3: Uniform Co s t Searc hp y t hon p acm an. p y -l m ed iu m Maz e -p Sear c h Age nt -a fn = ucstlVXSifcKXsearch.CcIcVsearchzythjin pa in. py -1 mdimllazc -p EearchAgent -a tn"u.:s rScarchAoni' uineSs-archAaCnt I uing problem tyjMS Pdslti&am

23、p;nSsarchProbLexPath found with total cast of 6S in Q» 1 secondsFe-rch ncdES espardEd： 269?acwn emerges virtirrioiis! Score： 442AT=ragF Scots： 44乙 DSantes:442.0Win Riile!1/1 U. OOjRecord：linCttN Pace尸pyth on p ac ma n .py 1 m edi u mD otte dMaze -p Sta y E astS e archAge n tE; fioar oh_C dastho

24、u paciBarL py -1 rodlutrOc tie dKas -p StayE as tE QarchAgantaniins： This dws not look like a rt*ular search bam?alti found witL toal edit ot I in 0.0 sec DikiiSearch nodes CKpijdcd； 186-'acnin m=r£Tm v > cteir 5 mis 1 Sctte ： -4hriver£gg S-:or-3:. 646. 0Ecor&s:&46. 0in Rats

25、： VI (1.00)Record IWinp yt h on pa c ma n .py -l m edi umS c a r yMaze - p St ayW e stSe a rc hA gentEI工智龍導(dǎo)論 班chjCndB'lMdrchpythHn pa匚nan. py T ite di unScbxs p StayWe lMrchAg.tfitPath fixuid 'zlih lottl do±i ut -jEVI?4.7?gfi4 i：. 0. C門ikSo arch tiadoz oxpinod： IOSPa;man emcr-es victori

26、ous Score： IISSrore： 4 '.S.0:;'ires:41S.0Vin Rate：1J 1.(1. DO)Record：WinSCORE: -12Q 4 : A * Searchpy t ho n p a cman . py - 1 bigMaz e z .5 - p Sear chA gent -a f n =a star,heuris t i c =man hat tan H euris t i c?<3iap-'jr'!eih_Co£teWetrh'：pyLhAn ptcaarL py -I b；t2j!iZ

27、63; -t .6 -p Sejj ajhAgMt -a rn-isiirrhjt JruatlicifinhaiiatFJeied ci 0.Ebst iiAsent j usizig tuzxtl 口n 凱and 壬gimtiu nE.tir.att aiiHaur 1st i :J.JTeiai,cJlAelrI Uding pfobllEiti type P口si tl -uSar hPTn'L 1 ezii"a th found with total ccrt af 210 in 0i 4 mcandKear ch 皿血三 &jrp：±nded:

28、543?3>snHn bfbi邑bs icitirLous! Scdtg： 300Scar t:3QOi0託pgruM3Q0.Q/in Rate：1J1(L 00)EecfirdVim胡I CUM mcw-«S< ORE; 26Q 5 : Co r ne rs Prob le m: Re prese n tati o npy t hon pacman.py -l tiny C orn e rs -p Sea rchA g en t - a fn=bfs , prob=Corn e rsP r obl emK:導(dǎo)論實(shí)菱kefliTchCodBWeftT&i加ytha

29、n ptcurL. py -1 tlnydonKfl -p SearQhAgMt f轉(zhuǎn)bb o&rsPTQblan*w*Ar'：hAK«titiSi?2ir ;hAKen.tl us Im- pToblein CQmrsFrQtil&®:aiti fcijmd Trith tot il cost oi 2S in 0, 0 EBcnnisSearchxpindd: 252旳citb" enei es： yiatorious! Score: 513旳范和勰Score： 510Scektss：512.0Vin Rate：1/1 (100)teo

30、crd:Vinp yth on pa cm a n . p y l me d iu m Corner s - p Sear c h A g ent -a f n =bfs,pr o b= Cor ne r sP r oblemL:- iJr' 5aS ajftk yth jui pu.i.nurL py -1 jrdL LiifCcttia i -p :呵Lti'fiab J a, prat =L iir；jbl &mrSeirch?iMnt ueif fu:tiaD bfsISeirhfi&ent- UEing prctiiem tyre ComarEPtab

31、lem旳 th found with k.titai cost ot 105 Ln 0. 1訂皤日hi an>d«« txT-indsd： 1 篝目?a-2jiain. erergea viitorLcus1 Scare: 434'.v&'afe S-ccre" 4J4.0酮 oce麻；4M< 0in Rate:l/l (1. 00)Kasrd:Hn7d CSmCmfHiSCOREQ6: C orners P ro bl e m : Heur is ticp y th o n p ac man .p y - l me di u

32、m C o r n e r s -p AS tar Co rners Ag ent-z 0.5E:；人工首'能異論電甜aparch工tide諒&arcti>pythtin pieman, py -1 mcdlunforriffl'E -ji AStarComarffABant -2 0. 5 r'ath fu jndtotal cGift u£ 106 In . j srMTCli rv>ri眄騁2Faamn croorscmm victoriovc! Scores 431后曰!玉呂日S匚口rm： 434.Scores:434 0VLn1/1 (L 00)lycord"VLtiSCORE: 17Q7: Eatin g A l l The Dots: Heuristicp y t ho n pacm a n. p y -l t r ick y Sea r ch - p AStarFo o dSearc h Age nt*,: A工 m1 夠?qū)д撌Ⅱ?yàn) xs今ar<h_codtsmarthen 誹亡朋n.-J tricJcyp iStar?odJerdtAgeniI'd th fou