地圖中最短路徑的搜索算法研究 畢業(yè)論文

1、<p><b>　　本科生畢業(yè)論文</b></p><p><b>　　目 錄</b></p><p><b>　　摘要1</b></p><p><b>　　1 問題分析2</b></p><p>　　1.1 技術(shù)分析2</p&g

2、t;<p>　　1.2 需求分析2</p><p>　　2 系統(tǒng)總體框架及算法設(shè)計(jì)3</p><p>　　2.1 系統(tǒng)總體框架3</p><p>　　2.2 算法設(shè)計(jì)3</p><p>　　2.2.1 廣度優(yōu)先算法3</p><p>　　2.2.2 深度優(yōu)先算法5</p><

3、;p>　　2.2.3 A*算法6</p><p>　　3 程序運(yùn)行結(jié)果與分析8</p><p>　　3.1 圖中各種算法的運(yùn)行效果8</p><p>　　3.1.1 廣度優(yōu)先算法運(yùn)行結(jié)果8</p><p>　　3.1.2 深度優(yōu)先算法運(yùn)行結(jié)果9</p><p>　　3.13 A*算法運(yùn)行結(jié)果10<

4、;/p><p>　　3.2 算法的總體比較與分析10</p><p><b>　　4 結(jié)論12</b></p><p><b>　　參考文獻(xiàn)13</b></p><p><b>　　謝辭14</b></p><p>　　地圖中最短路徑的搜索算法研究&

5、lt;/p><p>　　摘要：目前為止, 國內(nèi)外大量專家學(xué)者對“最短路徑問題”進(jìn)行了深入的研究。本文通過理論分析, 結(jié)合實(shí)際應(yīng)用，從各個方面較系統(tǒng)的比較了廣度優(yōu)先搜索算法(BFS)、深度優(yōu)先搜索算法(DFS)、A* 算法的優(yōu)缺點(diǎn)，并描述了算法之間的一些關(guān)系，以及每種算法的適用情況。廣度優(yōu)先搜索算法占內(nèi)存多但速度較快，深度優(yōu)先搜索算法占內(nèi)存少但速度較慢，A*算法是啟發(fā)式搜索算法，適合于解決小規(guī)模、大規(guī)模以及超大規(guī)模的問

6、題。程序通過調(diào)試運(yùn)行，實(shí)現(xiàn)了設(shè)計(jì)的目標(biāo)。</p><p>　　關(guān)鍵詞：最短路徑算法；廣度優(yōu)先算法；深度優(yōu)先算法；A*算法；</p><p>　　The Research of Search Algorithm of Shortest Path in Map</p><p>　　Name:Li Xiaokun Tutor:Dong Luan</p>

7、<p>　　Abstract: So far, a large number of domestic and foreign experts and scholars on the" shortest path problem" in-depth study. In this paper, through theoretical analysis and practical application, co

8、mprise with the breadth-first search algorithm ( BFS ), depth-first search algorithm ( DFS ) and the A * algorithms from any aspects of systematic. And describes some relationships between the algorithms,and the applicat

9、ion of each algorithm. Breadth-first search algorithm need more memory but fast, d</p><p>　　Key words: Shortest path algorithm; Breadth-first algorithm; Algorithm; A * algorithm;</p><p>　　地圖中最短路

10、徑的搜索算法很早就廣泛的應(yīng)用于各個領(lǐng)域，最短路徑問題也是圖論研究中的一個經(jīng)典問題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算法” [1]。此次畢業(yè)設(shè)計(jì)，是大學(xué)生走進(jìn)社會的最后一次學(xué)校學(xué)習(xí)，也是一次鍛煉，本設(shè)計(jì)基于VC++的基礎(chǔ)上，自主構(gòu)建若干個固定結(jié)點(diǎn)，并描述各個結(jié)點(diǎn)之間的路徑關(guān)系，然后用深度優(yōu)先算法、廣度優(yōu)先算法和A*算法求出圖中兩個結(jié)點(diǎn)的最短路徑，并

11、進(jìn)行全面的分析。</p><p><b>　　1 問題分析</b></p><p><b>　　1.1 技術(shù)分析</b></p><p>　　C++是一種靜態(tài)類型，支持多重編程范式的通用程序設(shè)計(jì)語言[1]。它廣泛的支援多種程序設(shè)計(jì)風(fēng)格（程序化程序設(shè)計(jì)、資料抽象化、面向?qū)ο蟪绦蛟O(shè)計(jì)、泛型程序設(shè)計(jì)）。 它是由C語言發(fā)展而來的，

12、既可以用于面向過程的結(jié)構(gòu)化程序設(shè)計(jì)，也可以用于面向?qū)ο蟮某绦蛟O(shè)計(jì),是一門功能強(qiáng)大的程序設(shè)計(jì)語言[2]。</p><p>　　Visual C++6.0是Microsoft公司在1998年推出的基于Windows 9X和Windows NT一個優(yōu)秀集成開發(fā)環(huán)境[3]。該開發(fā)環(huán)境為用戶提供了良好的可視化編程環(huán)境，程序員可以利用該開發(fā)環(huán)境輕松地訪問C++源代碼編輯器、資源編輯器和使用內(nèi)部調(diào)試器，并且可以創(chuàng)建項(xiàng)目文件。V

13、isual C++6.0不僅包括編譯器，而且它還包括許多有用組件，如程序向?qū)ppWizard、類向?qū)lass Wizard等，通過這些組件的協(xié)同工作，可以在VisualC++6.0集成開發(fā)環(huán)境中輕松的完成創(chuàng)建源文件、編輯資源，以及對程序的編譯、連接和調(diào)試等各項(xiàng)工作[4] 。</p><p><b>　　1.2 需求分析</b></p><p>　　本系統(tǒng)是基于VC

14、++，自主創(chuàng)建一張地圖，可以隨機(jī)建圖，也可以手動創(chuàng)建頂點(diǎn)，并附加權(quán)值，之后將相關(guān)信息儲存在數(shù)組中，最后利用深度優(yōu)先算法、廣度優(yōu)先算法和A*算法，求解出已知兩個定點(diǎn)之間的遍歷過程和最短路徑大小，試編寫一個程序完成相應(yīng)操作。之后根據(jù)求解的過程，對算法的完全性、時間復(fù)雜度、空間復(fù)雜性和最佳解等方面進(jìn)行比較分析，歸納每種算法的特性以及優(yōu)缺點(diǎn)。</p><p>　　2 系統(tǒng)總體框架及算法設(shè)計(jì)</p><

15、p>　　2.1 系統(tǒng)總體框架</p><p>　　系統(tǒng)的主要功能是用深度優(yōu)先算法、寬度優(yōu)先算法和A*算法求解地圖中兩個定點(diǎn)的最短路徑。總框架如下：</p><p>　　圖2-1 系統(tǒng)總體框架</p><p><b>　　2.2 算法設(shè)計(jì)</b></p><p>　　2.2.1 廣度優(yōu)先算法</p>

16、<p>　　廣度優(yōu)先算法(Breadth-First-Search)，又稱作寬度優(yōu)先搜索，或橫向優(yōu)先搜索，是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型[5]。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。</p><p>　　廣度優(yōu)先搜索的核心思想是

17、：從初始結(jié)點(diǎn)開始，應(yīng)用算符生成第一層結(jié)點(diǎn)，檢查目標(biāo)結(jié)點(diǎn)是否在這些后繼結(jié)點(diǎn)中，若沒有，再用產(chǎn)生式規(guī)則將所有第一層的結(jié)點(diǎn)逐一擴(kuò)展，得到第二層結(jié)點(diǎn)，并逐一檢查第二層結(jié)點(diǎn)中是否包含目標(biāo)結(jié)點(diǎn)。若沒有，再用算符逐一擴(kuò)展第二層所有結(jié)點(diǎn)……，如此依次擴(kuò)展，直到發(fā)現(xiàn)目標(biāo)結(jié)點(diǎn)為止[6]。廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣會出現(xiàn)回退的現(xiàn)象。因此它不是個遞歸的過程。為了實(shí)現(xiàn)逐層訪問，算法中使用了一個隊(duì)列以記憶正

18、在訪問的這一層和上一層的頂點(diǎn)，以便于向下一層訪問。</p><p>　　廣度優(yōu)先算法的主要代碼如下：</p><p>　　template<class Type></p><p>　　void Graph <Type> ::</p><p>　　BFTraverse () </p><p>&l

19、t;b>　　{</b></p><p><b>　　int i;</b></p><p>　　int n = NumberOfVertexes() ; //取圖的頂點(diǎn)個數(shù)</p><p>　　int * visited = new int [n]; //定義訪問標(biāo)記數(shù)組 visited</p>&

20、lt;p>　　for ( i = 0; i < n; i++ ) </p><p>　　visited [i] = 0; //訪問標(biāo)記數(shù)組 visited 初始化</p><p>　　for ( i = 0; i < n; i++ ) { //對圖中的每一個頂點(diǎn)進(jìn)行判斷</p><p>　　if (!visited [i]

21、) {</p><p>　　BFS (i, visited );</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　delete[ ]visited; //釋放 visited </p><p>

22、<b>　　}</b></p><p>　　template<class Type></p><p>　　void Graph<Type>::</p><p>　　BFS(const int v,int visited[ ])</p><p>　　{int qu[MaxVertexes],f=0,

23、r=0,u;</p><p>　　cout<< VTable[v].data<<" "; //訪問頂點(diǎn) v</p><p>　　visited[v] =1; //頂點(diǎn)v 作訪問標(biāo)記</p><p>　　qu[0]=v; //v入隊(duì)</p><

24、p>　　while(f<=r) //對不空</p><p>　　{ u=qu[f++];//v出隊(duì)（誰出隊(duì)就查找誰的所有未被處理的鄰接點(diǎn)，并入隊(duì)）</p><p>　　int p = GetFirstNeighbor (u);</p><p>　　while(p!= -1)</p><p><b>　　{</b

25、></p><p>　　if(!visited[p])</p><p><b>　　{ </b></p><p>　　visited[p]=1;</p><p>　　cout<< VTable[p].data<<" ";</p><p>　　

26、qu[++r]=p;</p><p><b>　　};</b></p><p>　　p=GetNextNeighbor(u,p);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}&

27、lt;/b></p><p>　　2.2.2 深度優(yōu)先算法</p><p>　　深度優(yōu)先搜索算法（Depth-First-Search），是搜索算法的一種[7]。類似于樹的前序遍歷，是沿著樹的深度遍歷樹的節(jié)點(diǎn)，盡可能深的搜索樹的分支。當(dāng)節(jié)點(diǎn)v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，則

28、選擇其中一個作為源節(jié)點(diǎn)并重復(fù)以上過程，整個進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止。深度優(yōu)先搜索算法屬于盲目搜索[8]。</p><p>　　深度優(yōu)先算法的主要代碼如下：</p><p>　　template<class Type></p><p>　　void Graph <Type> ::</p><p>　　DFTr

29、averse () </p><p><b>　　{</b></p><p>　　int i, n = NumberOfVertexes() ; //取圖的頂點(diǎn)個數(shù)</p><p>　　int * visited = new int [n]; //定義訪問標(biāo)記數(shù)組 visited</p><p>　　for ( i

30、 = 0; i < n; i++ ) </p><p>　　visited [i] = 0; //訪問標(biāo)記數(shù)組 visited 初始化</p><p>　　for ( i = 0; i < n; i++ ) //對圖中的每一個頂點(diǎn)進(jìn)行判斷</p><p>　　if (!visited [i]) DFS (i, visited );<

31、;/p><p>　　delete[ ]visited; //釋放 visited </p><p><b>　　}</b></p><p>　　template<class Type></p><p>　　void Graph<Type>::</p><p&g

32、t;　　DFS(const int v,int visited[ ])</p><p><b>　　{</b></p><p>　　cout<< VTable[v].data<<" "; //訪問頂點(diǎn) v</p><p>　　visited[v] =1;

33、 //頂點(diǎn)v 作訪問標(biāo)記</p><p>　　int w = GetFirstNeighbor (v); </p><p>　　while (w != -1) </p><p>　　{ //若頂點(diǎn) w 存在</p><p>　　if (!visited[w]) DFS (w,

34、visited);</p><p>　　w = GetNextNeighbor(v,w);</p><p>　　} //重復(fù)檢測 v 的所有鄰接頂點(diǎn)</p><p><b>　　}</b></p><p>　　2.2.3 A*算法</p><p>

35、;　　A*算法屬于一種啟發(fā)式搜索算法，被廣泛應(yīng)用在最優(yōu)路徑求解和一些策略設(shè)計(jì)的問題中[9]。所謂啟發(fā)式搜索，與DFS和BFS這類盲目型搜索最大的不同，就在于當(dāng)前搜索結(jié)點(diǎn)往下選擇下一步結(jié)點(diǎn)時，可以通過一個啟發(fā)函數(shù)來進(jìn)行選擇，選擇代價最少的結(jié)點(diǎn)作為下一步搜索結(jié)點(diǎn)而跳轉(zhuǎn)其上（遇到有一個以上代價最少的結(jié)點(diǎn)，不妨選距離當(dāng)前搜索點(diǎn)最近一次展開的搜索點(diǎn)進(jìn)行下一步搜索）。一個經(jīng)過仔細(xì)設(shè)計(jì)的啟發(fā)函數(shù)，往往在很快的時間內(nèi)就可得到一個搜索問題的最優(yōu)解。 而A

36、*算法最為核心的部分，就在于它的一個估值函數(shù)的設(shè)計(jì)上：f(n)=g(n)+h(n)；</p><p>　　其中f(n)是每個可能試探點(diǎn)的估值，它有兩部分組成：一部分為g(n)，它表示從起始搜索點(diǎn)到當(dāng)前點(diǎn)的代價（通常用某結(jié)點(diǎn)在搜索樹中的深度來表示）。另一部分，即h(n)，它表示啟發(fā)式搜索中最為重要的一部分，即當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估值。</p><p>　　A*算法保證找到最短路徑（最優(yōu)解的）

37、條件，關(guān)鍵在于估價函數(shù) h(n)的選取：估價值h(n)<= n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。如果 估價值>實(shí)際值, 搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解[10]。估價值與實(shí)際值越接近，估價函數(shù)取得就越好。</p><p>　　A*算法的主要代碼如下：</p><p>　　void Astar(){

38、 </p><p>　　knight t,s;</p><p>　　while(!que.empty()){</p><p>　　t=que.top(),que.pop(),visited[t.x][t.y]=true;</p><p>　　if(t.x==x2 && t.y==y2){<

39、/p><p>　　ans=t.step;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　for(int i=0;i<8;i++){</p><p>　　s.x=t.x+dirs[i][0],s.y=t.y+di

40、rs[i][1];</p><p>　　if(in(s) && !visited[s.x][s.y]){</p><p>　　s.g = t.g + 23;</p><p>　　s.h = Heuristic(s);</p><p>　　s.f = s.g + s.h;</p><p>　　s.step

41、 = t.step + 1;</p><p>　　que.push(s);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b>

42、;</p><p>　　3 程序運(yùn)行結(jié)果與分析</p><p>　　3.1 圖中各種算法的運(yùn)行效果</p><p>　　3.1.1 廣度優(yōu)先算法運(yùn)行結(jié)果</p><p>　　圖3-1 廣度優(yōu)先搜索</p><p>　　圖3-1是關(guān)于7個節(jié)點(diǎn)進(jìn)行廣度優(yōu)先搜索的運(yùn)行結(jié)果，從A節(jié)點(diǎn)開始，遍歷與他相鄰的節(jié)點(diǎn)CFG,然后在

43、遍歷C、F、G節(jié)點(diǎn)的相鄰節(jié)點(diǎn)BDE。廣度優(yōu)先搜索算法中，解答圖上結(jié)點(diǎn)的擴(kuò)展是沿結(jié)點(diǎn)深度的“斷層”進(jìn)行，也就是說，結(jié)點(diǎn)的擴(kuò)展是按它們接近起始結(jié)點(diǎn)的程度依次進(jìn)行的。首先生成第一層結(jié)點(diǎn)，同時檢查目標(biāo)結(jié)點(diǎn)是否在所生成的結(jié)點(diǎn)中，如果不在，則將所有的第一層結(jié)點(diǎn)逐一擴(kuò)展，得到第二層結(jié)點(diǎn)，并檢查第二層結(jié)點(diǎn)是否包含目標(biāo)結(jié)點(diǎn)……對長度為n+1的任一結(jié)點(diǎn)進(jìn)行擴(kuò)展之前，必須先考慮長度為n的結(jié)點(diǎn)的每種可能的狀態(tài)。因此，對于同一層結(jié)點(diǎn)來說，求解問題的價值是相同的，

44、我們可以按任意順序來擴(kuò)展它們。這里采用的原則是先生成的結(jié)點(diǎn)先擴(kuò)展。</p><p>　　3.1.2 深度優(yōu)先算法運(yùn)行結(jié)果</p><p>　　圖3-2 深度優(yōu)先搜索</p><p>　　圖3-2是關(guān)于7個節(jié)點(diǎn)進(jìn)行深度優(yōu)先搜索的運(yùn)行結(jié)果，從A節(jié)點(diǎn)開始，訪問與他相鄰的節(jié)點(diǎn)C,然后再訪問與C節(jié)點(diǎn)相鄰的節(jié)點(diǎn)，重復(fù)此過程直到找到目標(biāo)節(jié)點(diǎn)為止。深度優(yōu)先搜索算法中，從起始結(jié)

45、v出發(fā)，訪問它的任一鄰接結(jié)點(diǎn)w1；再從w1出發(fā)，訪問與 w1鄰接但還沒有訪問過的頂點(diǎn)w2；然后再從w2出發(fā)，進(jìn)行類似的訪問……如此進(jìn)行下去，直至所有的鄰接結(jié)點(diǎn)都被訪問為止,如果此時還沒有找到目標(biāo)結(jié)點(diǎn)，則退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有，則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到找到目標(biāo)結(jié)點(diǎn)或圖中所有頂點(diǎn)都被訪問過為止。對于多個鄰

46、接結(jié)點(diǎn)，求解問題的價值是相同的，因此我們可以按任意順序來擴(kuò)展它們。而這里采用的原則是先生成的結(jié)點(diǎn)先擴(kuò)展。</p><p>　　3.13 A*算法運(yùn)行結(jié)果</p><p>　　圖3-3 A*算法</p><p>　　圖3-3是關(guān)于7個節(jié)點(diǎn)進(jìn)行A*算法的運(yùn)行結(jié)果。A*最為核心的過程，在于每次選擇下一個當(dāng)前搜索點(diǎn)時，是從所有已探知的但未搜索過點(diǎn)中(可能是不同層，亦可

47、不在同一條支路上)，選取f值最小的結(jié)點(diǎn)進(jìn)行展開。而所有“已探知的但未搜索過點(diǎn)”可以通過一個按f值升序的隊(duì)列(即優(yōu)先隊(duì)列)進(jìn)行排列。這樣，在整體的搜索過程中，只要按照類似廣度優(yōu)先的算法框架，從優(yōu)先隊(duì)列中彈出隊(duì)首元素（f值），對其可能子結(jié)點(diǎn)計(jì)算g、h和f值，直到優(yōu)先隊(duì)列為空(無解)或找到終止點(diǎn)為止。</p><p>　　3.2 算法的總體比較與分析</p><p>　　對于廣度優(yōu)先搜索算法，當(dāng)

48、結(jié)點(diǎn)到跟結(jié)點(diǎn)的費(fèi)用和結(jié)點(diǎn)的深度成正比時，特別是當(dāng)每一結(jié)點(diǎn)到根結(jié)點(diǎn)的費(fèi)用等于深度時，用廣度優(yōu)先法得到的解是最優(yōu)解，但如果不成正比，則得到的解不一定是最優(yōu)解，而一般情況下廣度優(yōu)先搜索算發(fā)都能找到最優(yōu)解，但必須遍歷搜的的分枝。廣度優(yōu)先搜索算法，一般需要存儲產(chǎn)生的所有結(jié)點(diǎn)，占的存儲空間要比深度優(yōu)先大得多，由于對空間的大量需求，因此廣度優(yōu)先算法并不適合解非常大的問題。</p><p>　　對于深度優(yōu)先搜索算法，一般來說時間

49、復(fù)雜度大但空間復(fù)雜度小，不保留全部結(jié)點(diǎn)的深度優(yōu)先搜索法，由于把擴(kuò)展望的結(jié)點(diǎn)從數(shù)據(jù)庫中彈出刪除，這樣，一般在數(shù)據(jù)庫中存儲的結(jié)點(diǎn)數(shù)就是深度值，因此它占用的空間較少，所以，當(dāng)搜索樹的結(jié)點(diǎn)較多，用其他方法易產(chǎn)生內(nèi)存溢出時，深度優(yōu)先搜索不失為一種有效的算法。從輸出結(jié)果方面看，深度優(yōu)先搜索算法一般只能找到滿意解，但能很快找到接近解，可能不必遍歷所有分枝。在更多的情況下，深度優(yōu)先搜索算法也是比較好的方案。</p><p>　　

50、深度搜索與廣度搜索的控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)很相似，唯一的區(qū)別在于對擴(kuò)展節(jié)點(diǎn)選取上。這兩種算法每次都擴(kuò)展一個節(jié)點(diǎn)的所有子節(jié)點(diǎn)，而不同的是，深度搜索下一次擴(kuò)展的是本次擴(kuò)展出來的子節(jié)點(diǎn)中的一個，而廣度搜索擴(kuò)展的則是本次擴(kuò)展的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。比較深度優(yōu)先和廣度優(yōu)先兩種搜索算法可以看出，廣度優(yōu)先搜索法一般無回溯操作，即入棧和出棧的操作，所以運(yùn)行速度比深度優(yōu)先搜索算法法要快些?？傊?，一般情況下，深度優(yōu)先搜索法占內(nèi)存少但速度較慢，廣度優(yōu)先搜索算法占內(nèi)存多

51、但速度較快，在距離和深度成正比的情況下能較快地求出最優(yōu)解。因此在選擇用哪種算法時，要綜合考慮，決定取舍。</p><p>　　廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法均屬于盲目型搜索，也就是說，它不會選擇哪個結(jié)點(diǎn)在下一次搜索中更優(yōu)，而去跳轉(zhuǎn)到該結(jié)點(diǎn)進(jìn)行下一步的搜索，因此他們的效率非常的低。在運(yùn)氣不好的情形中，均需要試探完整個解集空間, 顯然，只能適用于問題規(guī)模不大的搜索問題中。而A*算法與廣度優(yōu)先和深度優(yōu)先這類盲目型搜

52、索最大的不同，就在于當(dāng)前搜索結(jié)點(diǎn)往下選擇下一步結(jié)點(diǎn)時，可以通過一個啟發(fā)函數(shù)來進(jìn)行選擇，選擇代價最少的結(jié)點(diǎn)作為下一步搜索結(jié)點(diǎn)而跳轉(zhuǎn)其上。A*算法的控制結(jié)構(gòu)與廣度搜索的十分類似，只是每次擴(kuò)展的都是當(dāng)前待擴(kuò)展節(jié)點(diǎn)中f值最小的一個，如果擴(kuò)展出來的節(jié)點(diǎn)與已擴(kuò)展的節(jié)點(diǎn)重復(fù)，則刪去這個節(jié)點(diǎn)。如果與待擴(kuò)展節(jié)點(diǎn)重復(fù)或這個節(jié)點(diǎn)的估價函數(shù)值較小，則用其代替原待擴(kuò)展節(jié)點(diǎn)。</p><p>　　A *算法利用對問題的了解和對問題求解過程的

53、了解, 尋求某種有利于問題求解的啟發(fā)信息, 從而利用這些啟發(fā)信息去搜索最優(yōu)路徑.它不用遍歷整個地圖, 而是每一步搜索都根據(jù)啟發(fā)函數(shù)朝著某個方向搜索.當(dāng)?shù)貓D很大很復(fù)雜時, 它的計(jì)算復(fù)雜度大大優(yōu)于其他啟發(fā)式算法, 是一種搜索速度非?？?、效率非常高的算法.但是, 相應(yīng)的A*算法也有它的缺點(diǎn).啟發(fā)性信息是人為加入的, 有很大的主觀性, 直接取決于操作者的經(jīng)驗(yàn), 對于不同的情形要用不同的啟發(fā)信息和啟發(fā)函數(shù), 且他們的選取難度比較大。當(dāng)h(n)&l

54、t;=n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值時，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。如果估價值>實(shí)際值, 搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。因此寫出好的評估函數(shù)，時A*算法的關(guān)鍵。</p><p>　　A*算法與廣度優(yōu)先和深度優(yōu)先的聯(lián)系在于，當(dāng)g(n)=0時，該算法類似于DFS，當(dāng)h(n)=0時，該算法類似于BFS , 這一點(diǎn)，可以通過A*搜索樹的具體過程中將h(n)設(shè)為0

55、或?qū)(n)設(shè)為0而得到。</p><p><b>　　4 結(jié)論</b></p><p>　　本文描述了最短路徑算法的一些步驟和實(shí)際應(yīng)用，歸納了每個算法的適用情況和優(yōu)缺點(diǎn)，以及算法之間的一些關(guān)系。對于最短或最少問題應(yīng)該選用廣度優(yōu)先算法,遍歷和求所有問題的時候則應(yīng)該選用深度優(yōu)先算法，這兩種算法雖然好用，但是由于時間和空間的局限性，以至于它們只能解決規(guī)模不大的搜索問題，對

56、規(guī)模十分大的情況下，他們的效率非常的低，甚至不能完成，那么就要用到啟發(fā)式搜索算法A*算法，A*算法是一種最好優(yōu)先的算法，適合于小規(guī)模、大規(guī)模以及超大規(guī)模的問題，但啟發(fā)式搜索算法同時具有很大的主觀性，它的優(yōu)劣取決于編程者的經(jīng)驗(yàn)，以及選用的啟發(fā)式函數(shù)，所以用A*算法編寫一個優(yōu)秀的程序，難度相應(yīng)是比較大的。每種算法都有自己的應(yīng)用范圍，對于不同的問題則應(yīng)該選用不同的算法。</p><p><b>　　參考文獻(xiàn)：

57、</b></p><p>　　[1] 圣群,滕忠堅(jiān),洪親,陳清華.四種最短路徑算法實(shí)例分析[J].電腦知識與技術(shù)(學(xué)術(shù)交流),2007(16):1030-1032.</p><p>　　[2] 樹林,尹玉妹.圖的最短路徑算法及其在網(wǎng)絡(luò)中的應(yīng)用[J].軟件導(dǎo)刊,2011(07):51-53.</p><p>　　[3] 文海,徐榮聰.幾種最短路徑的算法及比

58、較[J].福建電腦，2008(02）:9-12.</p><p>　　[4] 春燕.兩種最短路徑算法的比較[J].電腦知識與技術(shù)，2008（12）：511-513.</p><p>　　[5] 蘇男,偉,文生.最短路徑算法的比較[J].系統(tǒng)工程與電子技術(shù),1994(05)：43-49.</p><p>　　[6] 鳳生,李天志.所有最短路徑的求解算法[J].計(jì)算機(jī)工

59、程與科學(xué),2006(12)：83-84.</p><p>　　[7] 臣波,劉潤濤.一種基于Dijkstra的最短路徑算法[J].哈爾濱理工大學(xué)學(xué)報,2008(03)：35-37.</p><p>　　[8] 鳳生.求最短路徑的新算法[J].計(jì)算機(jī)工程與科學(xué),2006(02).</p><p>　　[9] 楊長保,王開義,馬生忠.一種最短路徑分析優(yōu)化算法的實(shí)現(xiàn)[J]

60、. 吉林大學(xué)學(xué)報(信息科學(xué)版),2002(02)：70-74.</p><p>　　[10] 亞松.VC++實(shí)現(xiàn)基于Dijkstra算法的最短路徑[J].科技信息(科學(xué)教研),2008(18)：36-37.</p><p>　　[11] YanchunShen . An improved Graph-based Depth-First algorithm and Dijkstra algo

61、rithm program of police patrol [J] . 2010 International Conference on Electrical Engineering and Automatic Control , 2010(3) : 73-77.</p><p><b>　　謝 辭</b></p><p>　　光陰似箭、日月如梭，美好的大學(xué)生

62、活在這驕陽似火的季節(jié)即將畫上一個句號，而于我的人生卻只是一個逗號，我將面臨又一次新的征程的開始。同時經(jīng)過幾個月的學(xué)習(xí)與努力，我的畢業(yè)論文也即將完成。本次論文的撰寫，對即將畢業(yè)的我也是一次難得的鍛煉機(jī)會，讓我的學(xué)習(xí)能力和實(shí)際應(yīng)用能力都有很大的提高。在本次畢業(yè)設(shè)計(jì)中，曾遇到過很多問題，在老師和同學(xué)的幫助下，都得到了很好的解決。其中，導(dǎo)師淵博的專業(yè)知識，嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度，精益求精的工作作風(fēng)，誨人不倦的高尚師德，對我影響深遠(yuǎn)。不僅使我掌握了基本的

63、研究方法，還使我明白了許多待人接物與為人處世的道理。他對我進(jìn)行了無私的指導(dǎo)和幫助，不厭其煩的進(jìn)行論文的批注，傾注了導(dǎo)師大量的心血。在此，我衷心的感謝我的指導(dǎo)老師xx老師和學(xué)校給予的良好環(huán)境以及關(guān)心我的人，是你們的關(guān)心讓我從校園生活慢慢的走向社會，走向未來。</p><p>　　一個人的成長絕不是一件孤立的事，沒有別人的支持與幫助是絕對辦不到。我感謝有這樣一個機(jī)會，可以讓我對所有給予我關(guān)心、幫助的人說一聲“謝謝”！