實驗內容：
實驗要求采用且不限于課程第四章內各種搜索算法此編寫一系列吃豆人程序解決以下列出的問題1-8，包括到達指定位置以及有效的吃豆等。
代碼下載地址：
簡介：
參考網址：http://ai.berkeley.edu/search.html內容，以下為實驗簡介。
基本代碼和支持文件可以從search.zip中獲取。其中，一些需要參考的文件如下：
需要編輯的文件：search.py和searchAgents.py
需要參考的文件：
pacman.py吃豆人游戲的程序。 文件包括一個描述”吃豆人”gamestate的類型。
game.py吃豆人游戲的運行邏輯. 文件包括以下類型AgentState, Agent, Direction, and Grid.
util.py搜索策略可以用到的數據結構.
可以忽略的支持性文件：graphicsDisplay.py graphicsUtils.py textDisplay.py ghostAgents.py keyboardAgents.pylayout.pyautograder.py?? testParser.pytestClasses.py test_cases/ searchTestClasses.py
解壓縮search.zip，在此目錄下，運行以下指令可打開吃豆人游戲。
python pacman.py
運行python autograder.py可以幫助你對自己的程序打分。
searchAgents.py中最簡單的Agent叫做GoWestAgent，一路向西，偶爾能實現(xiàn)目標：
python pacman.py --layout testMaze --pacman GoWestAgent
但是其不能實現(xiàn)轉彎：
python pacman.py --layout tinyMaze --pacman GoWestAgent
如果程序卡死，可通過CTRL-c來終止。
此項目中用到的指令也都儲存在commands.txt文件中，可用于復制和粘貼。
問題1：應用深度優(yōu)先算法找到一個特定的位置的豆
首先，運行一下命令測試SearchAgent是不是正常工作：
python pacman.py -l tinyMaze -p SearchAgent -afn=tinyMazeSearch
然后，完成完整的通用算法幫助吃豆人規(guī)劃路線。搜索算法的偽代碼見附錄。注意一個搜索節(jié)點不僅包含節(jié)點的狀態(tài)，而且要包含構建搜索路徑所需要的信息。
注意：所有的搜索函數必須返回一個從初始狀態(tài)到目標狀態(tài)的操作序列。所有操作必須合法（不能翻墻）。
注意：利用util.py文件中提供的Stack, Queue 和 PriorityQueue數據結構！這是自動評分系統(tǒng)的兼容性要求。
你的code應該能順利解決以下問題：
python pacman.py -l tinyMaze -p SearchAgent
pythonpacman.py -l mediumMaze -p SearchAgent
python pacman.py -l bigMaze -z .5 -p SearchAgent
注意：因為不同的搜索方法的不同之處僅僅在于open表的排序不同，因此請定義一個通用的搜索算法解決問題1-4。提示：問題1-4的不同之處在于用不同的數據結構對open表進行排序。
問題2：寬度優(yōu)先算法
利用寬度優(yōu)先算法實現(xiàn)解決以上問題。并利用以下命令測試你的code：
pythonpacman.py -l mediumMaze -p SearchAgent -a fn=bfs
pythonpacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5
問題3：代價一致算法
很多情況下，路徑中的代價是可以改變的。完成代價一致搜索方法(search.py文件中的uniformCostSearch函數)，并用以下命令測試你得code：
pythonpacman.py -l mediumMaze -p SearchAgent -a fn=ucs
pythonpacman.py -l mediumDottedMaze -p StayEastSearchAgent
pythonpacman.py -l mediumScaryMaze -p StayWestSearchAgent
完成A*搜索方法(search.py文件中的aStarSearch函數)，利用曼哈頓距離作為啟發(fā)函數，用以下命令測試你得code：
pythonpacman.py -l bigMaze -z .5 -p SearchAgent -afn=astar,heuristic=manhattanHeuristic
問題5：找到所有的角落
在角落迷宮的四個角上面有四個豆。這個搜索問題要求找到一條訪問所有四個角落的最短的路徑。
完成searchAgents.py文件中的CornersProblem搜索問題，你需要重新定義狀態(tài)，使其能夠表示角落是否被訪問。用以下命令測試你得code：
pythonpacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem
pythonpacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem
提示：新的狀態(tài)只包含吃豆人的位置和角落的狀態(tài)。
問題6：角落問題（啟發(fā)式）
構建合適的啟發(fā)函數，完成searchAgents.py文件中的cornersHeuristic角落搜索問題。用以下命令測試你得code：
pythonpacman.py -l mediumCorners -p AStarCornersAgent -z 0.5
問題7：吃掉所有的豆子
用盡可能少的步數吃掉所有的豆子。完成searchAgents.py文件中的FoodSearchProblem豆子搜索問題。此問題利用之前A*算法可以很容易找到解，可用以下命令測試：
pythonpacman.py -l testSearch -p AStarFoodSearchAgent
構建合適的啟發(fā)函數，完成searchAgents.py文件中的foodHeuristic豆子搜索（啟發(fā)式）問題。用以下命令測試你得code：
pythonpacman.py -l trickySearch -p AStarFoodSearchAgent
問題8：次最優(yōu)搜索
定義一個優(yōu)先吃最近的豆子函數是提高搜索速度的一個好的辦法。補充完成searchAgents.py文件中的AnyFoodSearchProblem目標測試函數，并完成searchAgents.py文件中的ClosestDotSearchAgent部分，在此Agent當中缺少一個關鍵的函數：找到最近豆子的函數。用以下命令測試你得code：
pythonpacman.py -l bigSearch -p ClosestDotSearchAgent -z .5
深度優(yōu)先搜索：
?? 深度優(yōu)先搜索采用堆棧尋找路徑，首先從起始結點出發(fā)，判斷是否為目標結點，若否，尋找與該結點的鄰接點，先搜索一條分支上的所有節(jié)點，然后再去搜索起始節(jié)點的其它分支結點，找出并存進待擴展結點表，等待擴展，每次先判斷待擴展結點表是否為空，若否，則從待擴展結點表中取出一個結點進行擴展，并將擴展后的結點存進該表，若是，則返回失敗。
廣度優(yōu)先搜索：
屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結果。換句話說，它并不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止，且搜索出來的路徑為最短路徑。
代價一致算法：
擴展的是路徑消耗g(n)最小的節(jié)點n,用優(yōu)先隊列來實現(xiàn)，對解的路徑步數不關心，只關心路徑總代價。即使找到目標節(jié)點也不會結束，而是再檢查新路徑是不是要比老路徑好，確實好，則丟棄老路徑。
A*算法：
公式表示為： f(n)=g(n)+h(n),其中 f(n) 是從初始點經由節(jié)點n到目標點的估價函數，g(n) 是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價，h(n) 是從n到目標節(jié)點最佳路徑的估計代價。保證找到最短路徑（最優(yōu)解的）條件，關鍵在于估價函數f(n)的選取：首先將起始結點S放入OPEN表，CLOSE表置空，算法開始時：
1、如果OPEN表不為空，從表頭取一個結點n，如果為空算法失敗。
2、n是目標解嗎？是，找到一個解（繼續(xù)尋找，或終止算法）。
3、將n的所有后繼結點展開，就是從n可以直接關聯(lián)的結點（子結點），如果不在CLOSE表中，就將它們放入OPEN表，并把S放入CLOSE表，同時計算每一個后繼結點的估價值f(n)，將OPEN表按f(x)排序，最小的放在表頭，重復算法，回到1。
