《xxxx酒店市場(chǎng)營(yíng)銷(xiāo)策略分析市場(chǎng)營(yíng)銷(xiāo)專(zhuān)業(yè)》由會(huì)員分享，可在線閱讀，更多相關(guān)《xxxx酒店市場(chǎng)營(yíng)銷(xiāo)策略分析市場(chǎng)營(yíng)銷(xiāo)專(zhuān)業(yè)（10頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、廣度優(yōu)先搜索在圖論中的應(yīng)用 摘要：本文詳細(xì)的分析了廣度優(yōu)先搜索算法，重點(diǎn)研究了該算法在圖論中的應(yīng)用，尤其是在最短路徑問(wèn)題中的應(yīng)用。通過(guò)與其它最短路搜索算法的比較分析，本文得到了這些最短路算法之間的關(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 （二）測(cè)試是否二分圖 5 （三）尋找非加權(quán)圖中任兩點(diǎn)的最短路徑 5 四、最短路中常用算法的比較 7 五、總結(jié) 7 參考文獻(xiàn) 8 附件 8 一、引言 使用計(jì)算機(jī)求解的問(wèn)題中，有許多問(wèn)題是無(wú)法用數(shù)學(xué)公式進(jìn)行計(jì)算推導(dǎo)和采用模擬方法來(lái)找

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

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

6、擴(kuò)展是沿結(jié)點(diǎn)深度的“斷層”進(jìn)行，也就是說(shuō)，結(jié)點(diǎn)的擴(kuò)展是按它們接近起始結(jié)點(diǎn)的程度依次進(jìn)行的。首先生成第一層結(jié)點(diǎn)，同時(shí)檢查目標(biāo)結(jié)點(diǎn)是否在所生成的結(jié)點(diǎn)中，如果不在，則將所有的第一層結(jié)點(diǎn)逐一擴(kuò)展，得到第二層結(jié)點(diǎn)，并檢查第二層結(jié)點(diǎn)是否包含目標(biāo)結(jié)點(diǎn)，...對(duì)長(zhǎng)度為n +1的任一結(jié)點(diǎn)進(jìn)行擴(kuò)展之前，必須先考慮長(zhǎng)度為n的結(jié)點(diǎn)的每種可能的狀態(tài)。因此，對(duì)于同一層結(jié)點(diǎn)來(lái)說(shuō)，求解問(wèn)題的價(jià)值是相同的，我們可以按任意順序來(lái)擴(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è)置一個(gè)表存儲(chǔ)所有的結(jié)點(diǎn)，為了滿足先生成的結(jié)點(diǎn)先擴(kuò)展的原則，存儲(chǔ)結(jié)點(diǎn)的表一般設(shè)計(jì)成隊(duì)列的數(shù)據(jù)結(jié)構(gòu)。搜索過(guò)程中不斷地從隊(duì)列頭取出結(jié)點(diǎn)進(jìn)行擴(kuò)展。對(duì)生成的新結(jié)點(diǎn)，要檢查它是否已在隊(duì)列中存在，還要檢查它是否目標(biāo)結(jié)點(diǎn)。如果新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)，則搜索成功，程序結(jié)束；若新結(jié)點(diǎn)不是目標(biāo)結(jié)點(diǎn)，并且未曾在隊(duì)列中出現(xiàn)過(guò)，則將它加入到隊(duì)列尾，否則將它丟棄，

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

9、：=1； 初始結(jié)點(diǎn)入隊(duì)； REPEAT CLOSED：=CLOSED+1； 取下一個(gè)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)存入隊(duì)列； 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{隊(duì)列空} （三）算法特性 1、空間復(fù)雜度 因?yàn)樗泄?jié)點(diǎn)都必須被儲(chǔ)存，因此廣度優(yōu)先搜索算法的空間復(fù)雜度為 O(|V| + |E|)，其中 |V| 是節(jié)點(diǎn)的數(shù)目，而 |E| 是圖中邊的數(shù)目。注：另一種說(shuō)法稱(chēng)廣度優(yōu)先搜索算法的空間復(fù)雜度為 O(BM)，其中 B 是最大分支系數(shù)，而 M 是樹(shù)的最長(zhǎng)路徑長(zhǎng)度。由于對(duì)空間的大量需求，因此廣度優(yōu)先搜索算法并不適合解非常大的問(wèn)題。 2、時(shí)間復(fù)雜度 最差情形下，廣度優(yōu)先搜索算法必須尋找所有到可能節(jié)點(diǎn)的所有路徑，因此其時(shí)間復(fù)雜度為 O(|V| + |E|)，其中 |V| 是節(jié)點(diǎn)的數(shù)目，而 |E| 是圖

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

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

13、 廣度優(yōu)先搜索算法可以用以測(cè)試二分圖。從任一節(jié)點(diǎn)開(kāi)始搜尋，并在搜尋過(guò)程中給節(jié)點(diǎn)不同的標(biāo)簽。例如，給開(kāi)始點(diǎn)標(biāo)簽 0，開(kāi)始點(diǎn)的所有鄰居標(biāo)簽 1，開(kāi)始點(diǎn)所有鄰居的鄰居標(biāo)簽二……以此類(lèi)推。若在搜尋過(guò)程中，任一節(jié)點(diǎn)有跟其相同標(biāo)簽的鄰居，則此圖就不是二分圖。若搜尋結(jié)束時(shí)這種情形未發(fā)生，則此圖為一二分圖。 （三）尋找非加權(quán)圖中任兩點(diǎn)的最短路徑 最短路問(wèn)題是圖論中的核心問(wèn)題之一，它是許多更深層算法的基礎(chǔ)。同時(shí)，該問(wèn)題有著大量的生產(chǎn)實(shí)際的背景。不少問(wèn)題從表面上看與最短路問(wèn)題沒(méi)有什么關(guān)系，卻也可以歸結(jié)為最短路問(wèn)題。 最短路的定義：在最短路問(wèn)題中，給出的是一有向加權(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)中快速地尋找從一個(gè)固定頂點(diǎn)s到其余頂點(diǎn)之間的最短距離。廣度優(yōu)先搜索是基于如下的簡(jiǎn)單想法：從s點(diǎn)開(kāi)始，訪問(wèn)每一個(gè)被s支配的頂點(diǎn)x。設(shè)和（頂點(diǎn)s是x的前驅(qū)）。訪問(wèn)哪些與s距離不為1且受x所支配的頂點(diǎn)y，則有。繼續(xù)這種過(guò)程，直至達(dá)到所有能達(dá)到的頂點(diǎn)。這些頂點(diǎn)是從s點(diǎn)可達(dá)的。由于搜索過(guò)程是一級(jí)一級(jí)展開(kāi)的，因此能快速的找到s點(diǎn)到其能到達(dá)的頂點(diǎn)的最短路徑。對(duì)于那些不能從s點(diǎn)可達(dá)的

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

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

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

18、最短路徑（假設(shè)存在最短路徑），但其在最短路問(wèn)題中的適用范圍較窄。當(dāng)最短路問(wèn)題中出現(xiàn)賦權(quán)邊或負(fù)權(quán)時(shí)，可以根據(jù)情況選擇Dijkstra、Floyd、Bellman-Ford和SPFA等算法搜索最短路。對(duì)于尋找圖中所有連接元件，廣度優(yōu)先搜索是一種快速簡(jiǎn)便的方法。另外，廣度優(yōu)先搜索算法還可以用于測(cè)試二分圖。因此廣度搜索算法在圖論中有廣泛的應(yīng)用。對(duì)廣度優(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] 殷劍宏 吳開(kāi)亞.圖論及其算法M. 中國(guó)科學(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：搜索過(guò)的節(jié)點(diǎn)% %T：搜索過(guò)的邊% 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 有什么問(wèn)題可以聯(lián)系我。 姓名：劉明浩 電話：13582379254 QQ：416588500 9