哈工大人工智能導論實驗報告

1、.人工智能導論實驗報告學院：計算機科學與技術(shù)學院專業(yè)：計算機科學與技術(shù)2016.12.20目錄人工智能導論實驗報告1一、簡介(對該實驗背景，方法以及目的的理解)31.實驗背景32.實驗方法33.實驗目的3二、方法（對每個問題的分析及解決問題的方法）4Q1: Depth First Search4Q2: Breadth First Search4Q3: Uniform Cost Search5Q4: A* Search6Q5: Corners Problem: Representation6Q6: Corners Problem: Heuristic6Q7: Eating All The Dot

2、s: Heuristic7Q8: Suboptimal Search7三、實驗結(jié)果（解決每個問題的結(jié)果）7Q1: Depth First Search7Q2: Breadth First Search9Q3: Uniform Cost Search10Q4: A* Search12Q5: Corners Problem: Representation13Q6: Corners Problem: Heuristic14Q7: Eating All The Dots: Heuristic14Q8: Suboptimal Search15自動評分15四、總結(jié)及討論（對該實驗的總結(jié)以及任何該實驗的啟發(fā)

3、）15一、 簡介(對該實驗背景，方法以及目的的理解)1. 實驗背景1) 自人工智能概念被提出，人工智能的發(fā)展就受到了很大的關(guān)注，取得了長足的發(fā)展，成為一門廣泛的交叉和前沿科學。到目前，弱人工智能取得了長足的發(fā)展，而強人工智能則暫時處于瓶頸。2) 吃豆人Pacman 居住在亮藍色的世界里，在這個世界有彎曲的走廊和美味佳肴。游戲的目的就是控制游戲的主角小精靈吃掉藏在迷宮內(nèi)所有的豆子，并且不能被幽靈抓到。高效地瀏覽世界將是吃豆人掌握世界的第一步。3) 通過本學期的學習我們已經(jīng)初步掌握了人工智能的基本知識，在實驗中則應用這些知識使用人工智能操縱吃豆人游戲。2. 實驗方法1) 在本實驗中, Pacman

4、 智能體將找到通過迷宮世界的路徑, 既包括到達一個指定的位置，也包括高效地搜集食物。我們編輯文件search.py和searchAgents.py，編寫一系列吃豆人程序，包括到達指定位置以及有效的吃豆，并將其應用到Pacman場景，完成對相關(guān)人工智能功能的完善。2) 在本實驗中，我們對下面8個問題進行研究，針對每個問題提出解決方法，逐步完成吃豆人游戲： Q1: Depth First Search Q2: Breadth First Search Q3: Uniform Cost Search Q4: A* Search Q5: Corners Problem: Representation

5、Q6: Corners Problem: Heuristic Q7: Eating All The Dots: Heuristic Q8: Suboptimal Search3. 實驗目的1) 完成實驗報告中的問題，編寫一系列吃豆人程序，包括到達指定位置以及有效的吃豆；2) 通過分析吃豆人游戲鞏固課堂上所學內(nèi)容；3) 復習python語言的使用。二、 方法（對每個問題的分析及解決問題的方法）Q1: Depth First Search應用深度優(yōu)先算法找到一個特定的位置的豆，我們通過depthFirstSearch函數(shù)實現(xiàn)深度優(yōu)先搜索的功能。深度優(yōu)先遍歷的方法是，從圖中某頂點v出發(fā)：1) 訪問頂

6、點v；2) 依次從v的未被訪問的鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點都被訪問；3) 若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發(fā)，重新進行深度優(yōu)先遍歷，直到圖中所有頂點均被訪問過為止。深度優(yōu)先搜索的順序如下圖所示：在depthFirstSearch中，由于搜索過程中火重復訪問到部分節(jié)點，所以需要對于每個節(jié)點設(shè)置標記，以指示該節(jié)點是否被訪問過。 先將每個后繼節(jié)點壓入搜索棧中，然后以深度優(yōu)先的順序進行搜索，判定是否符合目標狀態(tài)，并將符合結(jié)果的節(jié)點放入結(jié)果集。Q2: Breadth First Search應用寬度優(yōu)先算法找到一個特定的位置的豆，我們通過bread

7、thFirstSearch函數(shù)實現(xiàn)深度優(yōu)先搜索的功能。廣度優(yōu)先搜索算法的思想是：從圖中某頂點v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使得“先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。如下圖：在breadthFirstSearch中，大體的搜索思路與深度優(yōu)先算法一致，只是搜索的次序發(fā)生了變化。在這里注意，在深度優(yōu)先搜索和廣度優(yōu)先搜索方法中，我們使用的圖

8、搜索算法是一樣的，但是涉及到具體的數(shù)據(jù)結(jié)構(gòu)卻是不同的。在深度優(yōu)先搜索算法中，我們使用棧進行操作，在深度優(yōu)先搜索算法中，我們使用隊列進行操作，如下圖所示。這兩種數(shù)據(jù)結(jié)構(gòu)的不同之處就在于其中元素的輸出次序，在深度優(yōu)先搜索中需要按照壓棧順序的逆序進行搜索，咋子廣度優(yōu)先搜索中需要按照入隊順序的順序進行搜索。Q3: Uniform Cost Search很多情況下，路徑中的代價是可以改變的，在這個問題中，我們完成代價一致搜索方法。代價一致搜索，其實就是一個貪心搜索，取代擴展深度最淺的節(jié)點，代價一致搜索擴展的是路徑消耗最低的節(jié)點n。如果所有單步耗散都相等的話，這種算法就和廣度優(yōu)先搜索算法是一樣的。不過，這

9、樣在擴展到一個具有能返回到同一狀態(tài)的零耗散行動的節(jié)點時就會陷入無限循環(huán)。在uniformCostSearch函數(shù)中，我們計算每條路徑的總代價，將總代價作為優(yōu)先級進行搜索，待搜索序列存儲于隊列中。對于每個節(jié)點，使用代價函數(shù)getCostOfActions計算其所產(chǎn)生的代價，并依次作為搜索的優(yōu)先級進行搜索。同樣的，對于每個節(jié)點添加是否被訪問的標記。Q4: A* SearchA*算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法，也是許多其他問題的常用啟發(fā)式算法，對代價一致搜索算法進行了改進，加入了一個估計代價h。公式表示為： f(n)=g(n)+h(n),其中 f(n) 是從初始狀態(tài)經(jīng)由狀態(tài)n到目

10、標狀態(tài)的代價估計，g(n) 是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實際代價，h(n) 是從狀態(tài)n到目標狀態(tài)的最佳路徑的估計代價（對于路徑搜索問題，狀態(tài)就是圖中的節(jié)點，代價就是距離）。在本實驗中，我們使用曼哈頓距離作為啟發(fā)函數(shù)。在aStarSearch函數(shù)中，我們首先搜索具有最低組合成本和啟發(fā)式的節(jié)點。類似于問題三，我們計算每個節(jié)點的代價，并以此為依據(jù)搜索產(chǎn)生結(jié)果集，在搜索的過程中，還需要標記節(jié)點是否已經(jīng)被訪問過。Q5: Corners Problem: Representation找到所有的角落，在角落迷宮的四個角上面有四個豆，通過這個函數(shù)找到一條訪問所有四個角落的最短的路徑。在CornersPr

11、oblem類中，我們使用_init_函數(shù)存儲墻壁的位置，吃豆人的起點和角落位置，定義新的函數(shù)getStartState用于獲得節(jié)點起始狀態(tài)，isGoalState函數(shù)判斷當前節(jié)點是否為目標節(jié)點，getSuccessors函數(shù)返回后繼狀態(tài)，所需的操作以及代價，getCostOfActions函數(shù)計算動作序列所需的代價。查找后繼節(jié)點時，在四個方向一次遍歷，使用directionToVector移動位置，如果沒有墻，則把下一個的狀態(tài)，動作，花費的步數(shù)加入下一節(jié)點Q6: Corners Problem: Heuristic構(gòu)建合適的啟發(fā)函數(shù)，完成問題5中的角落搜索問題。在問題五使用的CornersPr

12、oblem類中定義cornersHeuristic函數(shù)，為角落問題構(gòu)造啟發(fā)函數(shù)。在cornersHeuristic函數(shù)中使用了GetNextNodes函數(shù)獲取下一個節(jié)點，isGoal函數(shù)判斷是否為目標。Q7: Eating All The Dots: Heuristic用盡可能少的步數(shù)吃掉所有的豆子。這個問題利用之前A*算法可以很容易找到解，此種方法在這里不再詳述。下面在FoodSearchProblem類中定義函數(shù)foodHeuristic，構(gòu)建合適的啟發(fā)函數(shù)完成豆子搜索（啟發(fā)式）問題。Q8: Suboptimal Search次最優(yōu)搜索，定義一個優(yōu)先吃最近的豆子的函數(shù)，以此來提高搜索速度。

13、補充AnyFoodSearchProblem目標測試函數(shù)，并在ClosestDotSearchAgent當中添加findPathToClosestDot函數(shù)，用于尋找最近的豆子。三、 實驗結(jié)果（解決每個問題的結(jié)果）Q1: Depth First Search python pacman.py -l tinyMaze -p SearchAgent python pacman.py -l mediumMaze -p SearchAgentpython pacman.py -l bigMaze -z .5 -p SearchAgentQ2: Breadth First Search python p

14、acman.py -l mediumMaze -p SearchAgent -a fn=bfspython pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5Q3: Uniform Cost Search python pacman.py -l mediumMaze -p SearchAgent -a fn=ucspython pacman.py -l mediumDottedMaze -p StayEastSearchAgentpython pacman.py -l mediumScaryMaze -p StayWestSearchAgen

15、tQ4: A* Search python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristicQ5: Corners Problem: Representation python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblempython pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblemQ6: Co

16、rners Problem: Heuristic python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5Q7: Eating All The Dots: Heuristic python pacman.py -l trickySearch -p AStarFoodSearchAgentQ8: Suboptimal Searchpython pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5自動評分四、 總結(jié)及討論（對該實驗的總結(jié)以及任何該實驗的啟發(fā)）1. 在這個實驗中，我們對深度優(yōu)先搜索、廣度優(yōu)先搜索、代價一致搜索和A*算法四種搜索方法進行了python代碼實現(xiàn)，對這四種