地圖中最短路徑地搜索算法研究的地的綜述

《地圖中最短路徑地搜索算法研究的地的綜述》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、實(shí)用標(biāo)準(zhǔn)文案地圖中最短路徑的搜索算法研究學(xué)生:李小坤導(dǎo)師：董巒摘要：目前為止,國內(nèi)外大量專家學(xué)者對(duì)“最短路徑問題”進(jìn)行了深入的研究。本文通過理論分析,結(jié)合實(shí)際應(yīng)用，從各個(gè)方面較系統(tǒng)的比較廣度優(yōu)先搜索算法(BFS)、深度優(yōu)先搜索算法(DFS)、A*算法的優(yōu)缺點(diǎn)。關(guān)鍵詞:最短路徑算法；廣度優(yōu)先算法；深度優(yōu)先算法；A*算法；Theshortestpathofmap'ssearchalgorithmAbstract:Sofar,alargenumberofdomesticandforeignexpertsa

2、ndscholarsonthe"shortestpathproblem"in-depthstudy.Inthispaper,throughtheoreticalanalysisandpracticalapplication,comprisewiththebreadth-firstsearchalgorithm(BFS),depth-firstsearchalgorithm(DFS)andtheA*algorithmsfromanyaspectsofsystematic.Keywords:shorte

3、stpathalgorithm;breadth-firstalgorithm;algorithm;A*algorithm;前言：最短路徑問題是地理信息系統(tǒng)（GIS）網(wǎng)絡(luò)分析的重要內(nèi)容之一，而且在圖論中也有著重要的意義。實(shí)際生活中許多問題都與“最短路徑問題”有關(guān),比如:網(wǎng)絡(luò)路由選擇,集成電路設(shè)計(jì)、布線問題、電子導(dǎo)航、交通旅游等。本文應(yīng)用深度優(yōu)先算法，廣度優(yōu)先算法和A*算法，對(duì)一具體問題進(jìn)行討論和分析，比較三種算的的優(yōu)缺點(diǎn)。在地圖中最短路徑的搜索算法研究中，每種算法的優(yōu)劣的比較原則主要遵循以下三點(diǎn):[1

4、](1)算法的完全性：提出一個(gè)問題，該問題存在答案，該算法能夠保證找到相應(yīng)的答案。算法的完全性強(qiáng)是算法性能優(yōu)秀的指標(biāo)之一。(2)算法的時(shí)間復(fù)雜性:提出一個(gè)問題，該算法需要多長(zhǎng)時(shí)間可以找到相應(yīng)的答案。算法速度的快慢是算法優(yōu)劣的重要體現(xiàn)。(3)算法的空間復(fù)雜性:算法在執(zhí)行搜索問題答案的同時(shí)，需要多少存儲(chǔ)空間。算法占用資源越少，算法的性能越好。地圖中最短路徑的搜索算法:1、廣度優(yōu)先算法廣度優(yōu)先算法(Breadth-First-Search)，又稱作寬度優(yōu)先搜索，或橫向優(yōu)先搜索，是最簡(jiǎn)便的圖的搜索算法之一，

5、這一算法也是很多重要的圖的算法的原型,Dijkstra精彩文檔實(shí)用標(biāo)準(zhǔn)文案單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。廣度優(yōu)先算法其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位址，徹底地搜索整張圖，直到找到結(jié)果為止。BFS并不使用經(jīng)驗(yàn)法則算法。廣度優(yōu)先搜索算法偽代碼如下：[2-3]BFS(v)//廣度優(yōu)先搜索G，從頂點(diǎn)v開始執(zhí)行//所有已搜索的頂點(diǎn)i都標(biāo)記為Visited(i)=1.//Visit

6、ed的初始分量值全為0Visited(v)=1;Q=[];//將Q初始化為只含有一個(gè)元素v的隊(duì)列whileQnotnulldou=DelHead(Q);for鄰接于u的所有頂點(diǎn)wdoifVisited(w)=0thenAddQ(w,Q);//將w放于隊(duì)列Q之尾Visited(w)=1;endifendforendwhileendBFS這里調(diào)用了兩個(gè)函數(shù)：AddQ(w,Q)是將w放于隊(duì)列Q之尾；DelHead(Q)是從隊(duì)列Q取第一個(gè)頂點(diǎn)，并將其從Q中刪除。重復(fù)DelHead(Q)過程，直到隊(duì)列Q空為止

7、。完全性：廣度優(yōu)先搜索算法具有完全性。這意指無論圖形的種類如何，只要目標(biāo)存在，則BFS一定會(huì)找到。然而，若目標(biāo)不存在，且圖為無限大，則BFS將不收斂（不會(huì)結(jié)束）。時(shí)間復(fù)雜度：最差情形下，BFS必須尋找所有到可能節(jié)點(diǎn)的所有路徑，因此其時(shí)間復(fù)雜度為,其中

8、V

9、是節(jié)點(diǎn)的數(shù)目，而

10、E

11、是圖中邊的數(shù)目?？臻g復(fù)雜度：因?yàn)樗泄?jié)點(diǎn)都必須被儲(chǔ)存，因此BFS的空間復(fù)雜度為，其中

12、V

13、是節(jié)點(diǎn)的數(shù)目，而

14、E

15、是圖中邊的數(shù)目。另一種說法稱BFS的空間復(fù)雜度為O(B),其中B是最大分支系數(shù)，而M是樹的最長(zhǎng)路徑長(zhǎng)度。由于對(duì)空間

16、的大量需求，因此BFS并不適合解非常大的問題。[4-5]精彩文檔實(shí)用標(biāo)準(zhǔn)文案2、深度優(yōu)先算法深度優(yōu)先搜索算法（DepthFirstSearch）英文縮寫為DFS，屬于一種回溯算法，正如算法名稱那樣，深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖。[6]其過程簡(jiǎn)要來說是沿著頂點(diǎn)的鄰點(diǎn)一直搜索下去，直到當(dāng)前被搜索的頂點(diǎn)不再有未被訪問的鄰點(diǎn)為止，此時(shí)，從當(dāng)前輩搜索的頂點(diǎn)原路返回到在它之前被搜索的訪問的頂點(diǎn)，并以此頂點(diǎn)作為當(dāng)前被搜索頂點(diǎn)。繼續(xù)這樣的過程，直至不能執(zhí)行為止。