我給妳看壹份文件:
地圖最短路徑搜索算法研究
學生:李導師:董鑾
摘要:到目前為止，國內外大量的專家學者對“最短路徑問題”進行了深入的研究。通過理論分析和實際應用，從各個方面系統地比較了廣度優先搜索算法(BFS)、深度優先搜索算法(DFS)和A*算法的優缺點。
關鍵詞:最短路徑算法；廣度優先搜索；深度優先算法；A*算法；
地圖最短路徑搜索算法
摘要:迄今為止，國內外大量專家學者對“最短路徑問題”進行了深入的研究。本文通過理論分析和實際應用，從系統的任何方面對廣度優先搜索算法(BFS)、深度優先搜索算法(DFS)和A *算法進行了研究。
關鍵詞:最短路徑算法；廣度優先算法；算法；A *算法；
前言:
最短路徑問題是地理信息系統(GIS)網絡分析的重要內容之壹，在圖論中也具有重要意義。現實生活中的許多問題都與“最短路徑問題”有關，如網絡路由、集成電路設計、布線問題、電子導航、交通和旅遊等。本文應用深度優先算法、廣度優先搜索算法和A*算法對壹個具體問題進行了討論和分析，並比較了三種算法的優缺點。
在地圖最短路徑搜索算法的研究中，各種算法優缺點的比較原則主要遵循以下三點:[1]
(1)算法的完備性:提出壹個問題，這個問題有壹個答案，算法可以保證找到對應的答案。算法的完備性是算法性能的優秀指標之壹。
(2)算法的時間復雜度:問壹個問題，算法需要多長時間找到對應的答案。算法的速度是算法優劣的重要體現。
(3)算法的空間復雜度:算法在搜索問題答案時需要多大的存儲空間？算法占用的資源越少，算法的性能越好。
地圖中最短路徑的搜索算法:
1，廣度優先搜索
廣度優先搜索，也稱為寬度優先搜索或橫向優先搜索，是最簡單的圖搜索算法之壹，該算法也是許多重要圖算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了類似寬度優先搜索的思想。廣度優先搜索(width-first-search)的別名是BFS，屬於壹種盲搜索方法，旨在系統地展開並檢查圖中的所有節點以找到結果。換句話說，它徹底搜索整個圖，而不考慮結果的可能地址，直到找到結果。BFS不使用經驗法則算法。
廣度優先搜索算法的偽代碼如下:[2-3]
BFS(v)//廣度優先搜索G，從頂點v開始
//所有搜索到的頂點I都標記為已訪問(i)=1。
//Visited//的初始組件值都是0。
已訪問(v)= 1；
q =[]；//將Q初始化為只有壹個元素v的隊列。
當Q不為空時
u = del head(Q)；
For與u的所有頂點w do相鄰。
如果已訪問(w)=0，則
AddQ(w，Q)；//將W放在隊列q的末尾。
已訪問(w)= 1；
endif
結束
結束時間
結束BFS
這裏調用了兩個函數:AddQ(w，Q)將w放在隊列Q的末尾；DelHead(Q)從隊列Q中取出第壹個頂點，並將其從Q中刪除。重復DelHead(Q)過程，直到隊列Q為空。
完備性:廣度優先搜索算法完備。這意味著無論哪種圖形，只要目標存在，BFS就壹定會找到它。然而，如果目標不存在，並且圖是無限的，則BFS不會收斂(不會結束)。
時間復雜度:在最壞的情況下，BFS必須找到到可能節點的所有路徑，所以它的時間復雜度是，其中|V|是圖中節點的數量，|E|是圖中邊的數量。
空間復雜度:因為必須存儲所有節點，所以BFS的空間復雜度為，其中|V|是圖中節點的數量，而|E|是圖中邊的數量。另壹種說法是BFS的空間復雜度是O(B)，其中B是樹的最大分支系數，m是樹的最長路徑長度。由於對空間的巨大需求，BFS不適合解決非常大的問題。[4-5]
2.深度優先算法
深度優先搜索，英文縮寫為DFS，屬於回溯算法。就像算法的名字壹樣，深度優先搜索所遵循的搜索策略是盡可能深地搜索圖。[6]簡而言之，過程就是沿著頂點的鄰點進行搜索，直到當前搜索到的頂點沒有未被訪問過的鄰點。此時，前任搜索到的頂點的原始路徑返回到其之前搜索到的訪問過的頂點，並將該頂點作為當前搜索到的頂點。繼續這個過程，直到不能執行為止。
深度優先搜索算法的偽代碼如下:[7]
DFS(v) //訪問v到達的所有頂點。
已訪問(v)= 1；
For與v的每個頂點w do相鄰。
如果已訪問(w)=0，則
DFS(w)；
endif
結束
結束DFS
作為壹種搜索算法，DFS在尋找解決NP(包括NPC)問題的方法中起著重要的作用。然而，該搜索算法的時間復雜度為O(n！)，其效率相對較低，當數據規模變大時，這種算法就顯得力不從心了。[8]深度優先搜索的效率問題有很多解決方案。最通用的是剪枝，也就是去掉無用的搜索分支。可行剪枝和最優剪枝兩種。
BFS:對解決最短或最少問題特別有效，搜索深度小，但缺點是內存消耗大(需要打開大量數組單元格來存儲狀態)。
DFS:對於解決所有的遍歷和尋找問題都是有效的，在問題搜索深度較小時速度很快，深度較大時效率很低。
3.A*算法
1968的壹篇論文，“P. E .哈特，N. J .尼爾森和b .拉斐爾。啟發式確定圖中最小費用路徑的形式基礎。IEEE Trans。系統。Sci。還有控制論，SSC-4(2):100-107，1968 .[9]此後，壹種巧妙而高效的算法——a*算法問世，並被廣泛應用於相關領域。A*算法實際上是在寬度優先搜索的基礎上引入了壹個評價函數。它不是壹次展開所有可展開的節點，而是利用評價函數對所有未展開的節點進行評價，從而找出最應該展開的節點並展開，直到找到目標節點。
A*算法主搜索過程的偽代碼如下:[10]
創建兩個表，打開的表保存所有已經生成但沒有調查的節點，關閉的表記錄已經訪問過的節點。
計算起點的估計值；
將起點放入打開的表中；
而(開！=NULL) //從打開的表中取估計值f最小的節點n；
If(n節點= =目標節點)break
endif
For(當前節點n的每個子節點x)
計算x的估計值；
如果(X打開)
if(x的估計值小於開表的估計值)
把n設為x的父親；
更新開放表中的估計值；//取最小路徑的估計值；
endif
endif
如果(X包括在內)
if(x的估計值小於CLOSE表的估計值)
把n設為x的父親；
更新結算表中的估計值；
將X節點放入OPEN //中，得到最小路徑的估計值。
endif
endif
如果(X不在路徑中)
把n設為x的父親；
求x的估計值；
並將x插入到打開的表中；//尚未排序
endif
結束於
在關閉表中插入n個節點；
根據估計值對開放表中的節點進行排序；//其實就是比較開放表中節點F的大小，從路徑最短的節點向下進行。
end while(打開！=空)
保存路徑，即從終點開始，每個節點沿著父節點移動，直到起點，這就是妳的路徑；
A *算法分析:
DFS和BFS在擴展子節點時都屬於盲搜索，即不會在下壹次搜索中選擇哪個節點更好，而跳轉到那個節點進行下壹次搜索。在運氣不好的情況下，需要探索整個解集空間，顯然，它只能應用於搜索小規模的問題。A*算法與DFS、BFS等盲搜索的最大區別在於，當前搜索節點選擇下壹個節點時，可以通過壹個啟發式函數進行選擇，選擇代價最小的節點作為下壹個搜索節點，並在其上跳轉。【11】a*算法是利用對問題的理解和對問題求解過程的理解，尋求壹些有利於問題求解的啟發式信息，從而利用這些啟發式信息來搜索最優路徑。它不需要遍歷整個地圖，而是在每壹步根據啟發式函數在某個方向進行搜索。當地圖較大且復雜時，其計算復雜度遠優於D ijks tr a算法。這是壹種搜索速度非常快、效率高的算法。但是，相應的A*算法也有其不足之處。啟發式信息是人為添加的，主觀性很大，直接依賴於操作人員的經驗。不同的情況使用不同的啟發信息和啟發函數，它們的選擇比較困難，很大程度上找不到最優路徑。
總結:
本文描述了最短路徑算法的壹些步驟，總結了每種算法的壹些優缺點，以及算法之間的壹些關系。對於BFS或者DFS來說，雖然好用，但是由於時間和空間的限制，只能解決小規模的問題，而BFS應該用於最短或者最少的問題，而DFS應該在遍歷和解決所有問題的時候使用。至於A*算法，是壹種啟發式搜索算法，也是壹種最優優先級算法。適用於小規模、大規模和超大規模問題，但啟發式搜索算法主觀性很大，其質量取決於程序員的經驗和選擇的啟發式函數，所以用A*算法寫出壹個優秀的程序相對困難。每種算法都有自己的優缺點。針對不同的問題選擇合理的算法是最好的方法。
參考資料:
[1]陳，滕，，陳清華。四種最短路徑算法的案例分析[J].計算機知識與技術(學術交流)，2007(16):1030-1032
陰，陰。圖的最短路徑算法及其在網絡中的應用[J].軟件指南，2011(07):51-53。
劉文海，徐榮聰。幾種最短路徑的算法及比較[J].福建計算機，2008(02):9-12。
鄧春燕。兩種最短路徑算法的比較[J].計算機知識與技術，2008(12):511-513
王蘇南，魏松人，江文勝人。最短路徑算法的比較[J].系統工程與電子，1994 (05): 43-49。
許、李天智。求解所有最短路徑的算法[J].計算機工程與科學，2006 (12): 83-84
李，劉潤濤。壹種基於Dijkstra的最短路徑算法[J].哈爾濱理工大學學報，2008 (03): 35-37
許道。壹種求最短路徑的新算法[J].計算機工程與科學，2006(02)。
[9]顏春申。壹種改進的基於圖的深度優先算法和Dijkstra算法的警察巡邏程序[J].2010電氣工程與自動控制國際會議，2010(3) : 73-77
[10]布松雅VC++實現基於Dijkstra算法的最短路徑[J].科技信息(科學教學與研究)，2008 (18): 36-37
楊，王，馬。壹種最短路徑分析優化算法的實現[J].吉林大學學報(信息科學版)，2002 (02): 70-74