《xxxx酒店市場營銷策略分析市場營銷專業(yè)》由會員分享，可在線閱讀，更多相關(guān)《xxxx酒店市場營銷策略分析市場營銷專業(yè)（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、廣度優(yōu)先搜索在圖論中的應(yīng)用 摘要：本文詳細的分析了廣度優(yōu)先搜索算法，重點研究了該算法在圖論中的應(yīng)用，尤其是在最短路徑問題中的應(yīng)用。通過與其它最短路搜索算法的比較分析，本文得到了這些最短路算法之間的關(guān)系。 關(guān)鍵詞：廣度優(yōu)先搜索，最短路徑，圖論。 Abstract：this paper gives a detailed analysis of the breadth-first search algorithm, and emphasis on the algorithm in the application of graph theory, especially in the sh

2、ortest path problem in the application. Through the comparative analysis with the other shortest path search algorithm, this paper obtains these relationships between these shortest path algorithms. Keywords: breadth first search, shortest path, graph theory.

3、 目錄 摘要 0 Abstract 0 一、引言 2 二、廣度優(yōu)先搜索算法 2 （一）基本思想 2 （二）算法結(jié)構(gòu) 3 （三）算法特性 4 （四）廣度優(yōu)先搜索算法在圖論中的應(yīng)用 5 三、廣度優(yōu)先搜索算法在圖論中應(yīng)用的具體分析 5 （一）尋找連接元件 5 （二）測試是否二分圖 5 （三）尋找非加權(quán)圖中任兩點的最短路徑 5 四、最短路中常用算法的比較 7 五、總結(jié) 7 參考文獻 8 附件 8 一、引言 使用計算機求解的問題中，有許多問題是無法用數(shù)學公式進行計算推導和采用模擬方法來找

4、出答案的。這樣的問題往往需要我們根據(jù)問題所給定的一些條件，在問題的所有可能解中用某種方式找出問題的解來，這就是所謂的搜索法或搜索技術(shù)。 常見的搜索算法有廣度優(yōu)先搜索法（簡稱為BFS）、深度優(yōu)先搜索法、雙向廣度優(yōu)先搜索法，A*算法、回溯法、枚舉法、分支定界法等。 圖論是數(shù)學的一個分支,以圖為研究對象。這種圖由若干給定的點和連接兩點的線構(gòu)成,借以描述某些事物之間的關(guān)系。用點代表事物,用連接兩點的線表示兩個事物之間具有特定關(guān)系。 圖論起源于18世紀,追朔到1736年瑞士數(shù)學家L.Euler出版第一本圖論著作,提出和解決著名Konigsberg七橋問題。從那時以來,圖論不僅在許多領(lǐng)域,如計算機科

5、學,運籌學,心理學等方面得到了廣泛的應(yīng)用,而且學科本身也獲得長足發(fā)展,形成了擬陣理論,超圖理論,代數(shù)圖論,拓撲圖論等新分支。 本文討論廣度優(yōu)先搜索在圖論中的應(yīng)用。 二、廣度優(yōu)先搜索算法 （一）基本思想 采用廣度優(yōu)先搜索算法解答問題時，需要構(gòu)造一個表明狀態(tài)特征和不同狀態(tài)之間關(guān)系的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)稱為結(jié)點。根據(jù)問題所給定的條件，從一個結(jié)點出發(fā)，可以生成一個或多個新的結(jié)點，這個過程通常稱為擴展。結(jié)點之間的關(guān)系一般可以表示成一棵樹，它被稱為解答樹。搜索算法的搜索過程實際上就是根據(jù)初始條件和擴展規(guī)則構(gòu)造一棵解答樹并尋找符合目標狀態(tài)的結(jié)點的過程。 廣度優(yōu)先搜索算法中，解答樹上結(jié)點的

6、擴展是沿結(jié)點深度的“斷層”進行，也就是說，結(jié)點的擴展是按它們接近起始結(jié)點的程度依次進行的。首先生成第一層結(jié)點，同時檢查目標結(jié)點是否在所生成的結(jié)點中，如果不在，則將所有的第一層結(jié)點逐一擴展，得到第二層結(jié)點，并檢查第二層結(jié)點是否包含目標結(jié)點，...對長度為n +1的任一結(jié)點進行擴展之前，必須先考慮長度為n的結(jié)點的每種可能的狀態(tài)。因此，對于同一層結(jié)點來說，求解問題的價值是相同的，我們可以按任意順序來擴展它們。這里采用的原則是先生成的結(jié)點先擴展。 廣度優(yōu)先搜索算法的搜索順序如下圖： A B C D

7、 E F G H I J K L M 廣度優(yōu)先搜索順序如下： A->B->C->D->E->F->G->H->I->J->K-L->M 廣度優(yōu)先搜索算法中，為了便于進行搜索，要設(shè)置一個表存儲所有的結(jié)點，為了滿足先生成的結(jié)點先擴展的原則，存儲結(jié)點的表一般設(shè)計成隊列的數(shù)據(jù)結(jié)構(gòu)。搜索過程中不斷地從隊列頭取出結(jié)點進行擴展。對生成的新結(jié)點，要檢查它是否已在隊列中存在，還要檢查它是否目標結(jié)點。如果新結(jié)點是目標結(jié)點，則搜索成功，程序結(jié)束；若新結(jié)點不是目標結(jié)點，并且未曾在隊列中出現(xiàn)過，則將它加入到隊列尾，否則將它丟棄，

8、再從隊列頭取出結(jié)點進行擴展......。最終可能產(chǎn)生兩種結(jié)果：找到目標結(jié)點，或擴展完所有結(jié)點而沒有找到目標結(jié)點。 如果目標結(jié)點存在于解答樹的有限層上，廣度優(yōu)先搜索算法一定能保證找到一條通向它的最佳路徑，因此廣度優(yōu)先搜索算法特別適用于只需求出最優(yōu)解的問題。當問題需要給出解的路徑，則要保存每個結(jié)點的來源，也就是它是從哪一個節(jié)點擴展來的。 對于不同的問題，用廣度優(yōu)先搜索法的算法基本上都是一樣的。但表示問題狀態(tài)的結(jié)點數(shù)據(jù)結(jié)構(gòu)、新結(jié)點是否目標結(jié)點和是否重復結(jié)點的判斷等方面則有所不同，對具體的問題需要進行具體分析。 （二）算法結(jié)構(gòu) 數(shù)據(jù)初始化；設(shè)隊列首指針CLOSED：=0；隊尾指針OPEN

9、：=1； 初始結(jié)點入隊； REPEAT CLOSED：=CLOSED+1； 取下一個CLOSED所指結(jié)點； FOR R：=1 TO MAXR DO {共有MAXR種操作方法,試第R種} BEGIN IF 子結(jié)點符合條件 THEN BEGIN OPEN：=OPEN+1；把新結(jié)點存入隊列； IF 新結(jié)點與原有結(jié)點重復 THEN OPEN：=OPEN-1{刪去刻結(jié)點} ELSE IF 新結(jié)點是目標結(jié)點 THEN BEGIN 輸出結(jié)果并退出； END； END；

10、END； UNTIL CLOSED>OPEN{隊列空} （三）算法特性 1、空間復雜度 因為所有節(jié)點都必須被儲存，因此廣度優(yōu)先搜索算法的空間復雜度為 O(|V| + |E|)，其中 |V| 是節(jié)點的數(shù)目，而 |E| 是圖中邊的數(shù)目。注：另一種說法稱廣度優(yōu)先搜索算法的空間復雜度為 O(BM)，其中 B 是最大分支系數(shù)，而 M 是樹的最長路徑長度。由于對空間的大量需求，因此廣度優(yōu)先搜索算法并不適合解非常大的問題。 2、時間復雜度 最差情形下，廣度優(yōu)先搜索算法必須尋找所有到可能節(jié)點的所有路徑，因此其時間復雜度為 O(|V| + |E|)，其中 |V| 是節(jié)點的數(shù)目，而 |E| 是圖

11、中邊的數(shù)目。 3、完全性 廣度優(yōu)先搜索算法具有完全性。這里指無論圖形的種類如何，只要目標存在，則廣度優(yōu)先搜索算法一定會找到。然而，若目標不存在，且圖為無限大，則廣度優(yōu)先搜索算法將不收斂（不會結(jié)束）。 4、最佳解 若所有邊的長度相等，廣度優(yōu)先搜索算法是最佳解——亦即它找到的第一個解，距離根節(jié)點的邊數(shù)目一定最少；但對一般的圖來說，廣度優(yōu)先搜索算法并不一定回傳最佳解。這是因為當圖形為加權(quán)圖（亦即各邊長度不同）時，廣度優(yōu)先搜索算法仍然回傳從根節(jié)點開始，經(jīng)過邊數(shù)目最少的解；而這個解距離根節(jié)點的距離不一定最短。這個問題可以使用考慮各邊權(quán)值，廣度優(yōu)先搜索算法的改良算法成本一致搜尋法（en:unifo

12、rm-cost search）來解決。然而，若非加權(quán)圖形，則所有邊的長度相等，廣度優(yōu)先搜索算法就能找到最近的最佳解。 （四）廣度優(yōu)先搜索算法在圖論中的應(yīng)用 尋找圖中所有連接元件（Connected Component）。一個連接元件是圖中的最大相連子圖。 尋找連接元件中的所有節(jié)點。 尋找非加權(quán)圖中任兩點的最短路徑。 測試一圖是否為二分圖。 (Reverse) Cuthill–McKee算法。 三、廣度優(yōu)先搜索算法在圖論中應(yīng)用的具體分析 （一）尋找連接元件 由起點開始，執(zhí)行廣度優(yōu)先搜索算法后所經(jīng)過的所有節(jié)點，即為包含起點的一個連接元件。 （二）測試是否二分圖

13、 廣度優(yōu)先搜索算法可以用以測試二分圖。從任一節(jié)點開始搜尋，并在搜尋過程中給節(jié)點不同的標簽。例如，給開始點標簽 0，開始點的所有鄰居標簽 1，開始點所有鄰居的鄰居標簽二……以此類推。若在搜尋過程中，任一節(jié)點有跟其相同標簽的鄰居，則此圖就不是二分圖。若搜尋結(jié)束時這種情形未發(fā)生，則此圖為一二分圖。 （三）尋找非加權(quán)圖中任兩點的最短路徑 最短路問題是圖論中的核心問題之一，它是許多更深層算法的基礎(chǔ)。同時，該問題有著大量的生產(chǎn)實際的背景。不少問題從表面上看與最短路問題沒有什么關(guān)系，卻也可以歸結(jié)為最短路問題。 最短路的定義：在最短路問題中，給出的是一有向加權(quán)圖G=(V,E)，在其上定義的加權(quán)函數(shù)W:

14、E→R為從邊到實型權(quán)值的映射。路徑P=(, ,……, )的權(quán)是指其組成邊的所有權(quán)值之和： 定義u到v間最短路徑的權(quán)為： 從結(jié)點u到結(jié)點v的最短路徑定義為權(quán)的任何路徑。 廣度優(yōu)先搜索能夠在非加權(quán)圖G=(V,E)中快速地尋找從一個固定頂點s到其余頂點之間的最短距離。廣度優(yōu)先搜索是基于如下的簡單想法：從s點開始，訪問每一個被s支配的頂點x。設(shè)和（頂點s是x的前驅(qū)）。訪問哪些與s距離不為1且受x所支配的頂點y，則有。繼續(xù)這種過程，直至達到所有能達到的頂點。這些頂點是從s點可達的。由于搜索過程是一級一級展開的，因此能快速的找到s點到其能到達的頂點的最短路徑。對于那些不能從s點可達的

15、剩余頂點z，令。廣度優(yōu)先搜索較為正式的表述是算法的結(jié)尾處，意味著或者v從s是不可達的。（附件中有用matlab語言實現(xiàn)最短路徑搜索算法的程序） 實作方法 1、首先將根節(jié)點放入隊列中。 2、從隊列中取出第一個節(jié)點，并檢驗它是否為目標。 l 如果找到目標，則結(jié)束搜尋并回傳結(jié)果。 l 否則將它所有尚未檢驗過的直接子節(jié)點加入隊列中。 3、若隊列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結(jié)束搜尋并回傳“找不到目標”。 4、重復步驟2。 四、最短路中常用算法的比較 其它最短路算法與廣度優(yōu)先搜索算法的比較列表 算法 時間復雜度 空間復雜度 編程復雜度 適

16、用范圍 BFS O(E+V) O(E+V) 簡單 非加權(quán)圖（窄） Dijkstra O()或O((E+V)logV) O()或 O（E+V） 簡單或相對復雜 不含負權(quán)的圖（窄） Floyd O（） O（） 簡單 實數(shù)圖（廣） Bellman-Ford O（VE） O(E+V) 簡單 實數(shù)圖（廣） SPFA O(E) O(E+V) 簡單 實數(shù)圖（廣） 通過比較分析分析，可知： l 對于非加權(quán)圖，可用簡便而又快捷的廣度優(yōu)先搜索算法找出最短路徑。 l Dijkstra算法的效率高，但是也有局限性，就是對于含負權(quán)的圖無能為力。 l Flo

17、yd算法簡單、易于實現(xiàn)，且適用范圍廣，但時間和空間復雜度過高。 l Bellman-Ford算法對于所有最短路長存在的圖都適用而且簡單，但是時間復雜度高，效率常常不盡人意。 l SPFA算法可以說是綜合了上述算法的優(yōu)點。它的效率同樣很不錯，而且對于最短路中存在的所有圖都適用，無論是否存在負權(quán)。它的編程復雜度也很低，是高性價比的算法。 五、總結(jié) 廣度優(yōu)先搜索算法是一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位址，徹底地搜索整張圖，直到找到結(jié)果為止。廣度優(yōu)先搜索算法并不使用經(jīng)驗法則算法。對于非加權(quán)圖，廣度優(yōu)先搜索算法可以快速的找出

18、最短路徑（假設(shè)存在最短路徑），但其在最短路問題中的適用范圍較窄。當最短路問題中出現(xiàn)賦權(quán)邊或負權(quán)時，可以根據(jù)情況選擇Dijkstra、Floyd、Bellman-Ford和SPFA等算法搜索最短路。對于尋找圖中所有連接元件，廣度優(yōu)先搜索是一種快速簡便的方法。另外，廣度優(yōu)先搜索算法還可以用于測試二分圖。因此廣度搜索算法在圖論中有廣泛的應(yīng)用。對廣度優(yōu)先算法加以改進，可以得到特性更好的算法，如，雙向廣度優(yōu)先搜索算法和算法等。 參考文獻 [1] 卜月華 圖論及其應(yīng)用 南京：東南大學出版社，2000。 [2] J.邦詹森 G.古廷 有向圖的理論、算法及其應(yīng)用 科學出版社 2009。

19、 [3] http://zh.wikipedia.org/zh-cn/BFS#C_.E7.9A.84.E5.AF.A6.E4.BD.9C。 [4] 殷劍宏 吳開亞.圖論及其算法M. 中國科學技術(shù)出版社。 附件 Matlab程序： function [R,T]=bfs(A,s,d) %A：鄰接矩陣(連通點間的距離為1，不連通的點間距離為inf,同點間距離為0）% %s：源頂點，d：目標頂點% %R：搜索過的節(jié)點% %T：搜索過的邊% k=s; R(1)=s; Q(1)=s; T=[]; qq=[]; kk=0; while size(Q) %從Q中

20、選一點% %選最先插入Q的點% [p,q]=find(A(k,:)==1) qq=[qq,q]; for i=1:size(q) if sum(find(R==q(i))) a=find(Q==q(i)); Q(a)=[]; else Q=[Q,q(i)]; R=[R,q(i)]; T=[T;[k,q(i)]]; end if i==d break; end end if i==d break; end k=qq(kk+1); end if sum(size(Q))==0 disp(找不到目標。); end 有什么問題可以聯(lián)系我。 姓名：劉明浩 電話：13582379254 QQ：416588500 9