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

1、廣度優(yōu)先搜索在圖論中的應(yīng)用 摘要：本文詳細(xì)的分析了廣度優(yōu)先搜索算法，重點(diǎn)研究了該算法在圖論中的應(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)圖中任兩點(diǎn)的最短路徑 5 四、最短路中常用算法的比較 7 五、總結(jié) 7 參考文獻(xiàn) 8 附件 8 一、引言 使用計算機(jī)求解的問題中，有許多問題是無法用數(shù)學(xué)公式進(jìn)行計算推導(dǎo)和采用模擬方法來找

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

5、學(xué),運(yùn)籌學(xué),心理學(xué)等方面得到了廣泛的應(yīng)用,而且學(xué)科本身也獲得長足發(fā)展,形成了擬陣?yán)碚?超圖理論,代數(shù)圖論,拓?fù)鋱D論等新分支。 本文討論廣度優(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é)點(diǎn)。根據(jù)問題所給定的條件，從一個結(jié)點(diǎn)出發(fā)，可以生成一個或多個新的結(jié)點(diǎn)，這個過程通常稱為擴(kuò)展。結(jié)點(diǎn)之間的關(guān)系一般可以表示成一棵樹，它被稱為解答樹。搜索算法的搜索過程實(shí)際上就是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的結(jié)點(diǎn)的過程。 廣度優(yōu)先搜索算法中，解答樹上結(jié)點(diǎn)的

6、擴(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)來說，求解問題的價值是相同的，我們可以按任意順序來擴(kuò)展它們。這里采用的原則是先生成的結(jié)點(diǎn)先擴(kuò)展。 廣度優(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)先搜索算法中，為了便于進(jìn)行搜索，要設(shè)置一個表存儲所有的結(jié)點(diǎn)，為了滿足先生成的結(jié)點(diǎn)先擴(kuò)展的原則，存儲結(jié)點(diǎn)的表一般設(shè)計成隊列的數(shù)據(jù)結(jié)構(gòu)。搜索過程中不斷地從隊列頭取出結(jié)點(diǎn)進(jìn)行擴(kuò)展。對生成的新結(jié)點(diǎn)，要檢查它是否已在隊列中存在，還要檢查它是否目標(biāo)結(jié)點(diǎn)。如果新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)，則搜索成功，程序結(jié)束；若新結(jié)點(diǎn)不是目標(biāo)結(jié)點(diǎn)，并且未曾在隊列中出現(xiàn)過，則將它加入到隊列尾，否則將它丟棄，

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

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

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

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

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

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

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

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

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

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

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

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

20、選一點(diǎn)% %選最先插入Q的點(diǎn)% [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(找不到目標(biāo)。); end 有什么問題可以聯(lián)系我。 姓名：劉明浩 電話：13582379254 QQ：416588500 9