xxxx酒店市場(chǎng)營銷策略分析市場(chǎng)營銷專業(yè)

廣度優(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 shortest 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.目錄摘要0Abstract0一、引言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ī)求解的問題中，有許多問題是無法用數(shù)學(xué)公式進(jìn)行計(jì)算推導(dǎo)和采用模擬方法來找出答案的。這樣的問題往往需要我們根據(jù)問題所給定的一些條件，在問題的所有可能解中用某種方式找出問題的解來，這就是所謂的搜索法或搜索技術(shù)。常見的搜索算法有廣度優(yōu)先搜索法（簡(jiǎn)稱為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七橋問題。從那時(shí)以來,圖論不僅在許多領(lǐng)域,如計(jì)算機(jī)科學(xué),運(yùn)籌學(xué),心理學(xué)等方面得到了廣泛的應(yīng)用,而且學(xué)科本身也獲得長(zhǎng)足發(fā)展,形成了擬陣?yán)碚?超圖理論,代數(shù)圖論,拓?fù)鋱D論等新分支。本文討論廣度優(yōu)先搜索在圖論中的應(yīng)用。二、廣度優(yōu)先搜索算法（一）基本思想采用廣度優(yōu)先搜索算法解答問題時(shí)，需要構(gòu)造一個(gè)表明狀態(tài)特征和不同狀態(tài)之間關(guān)系的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)稱為結(jié)點(diǎn)。根據(jù)問題所給定的條件，從一個(gè)結(jié)點(diǎn)出發(fā)，可以生成一個(gè)或多個(gè)新的結(jié)點(diǎn)，這個(gè)過程通常稱為擴(kuò)展。結(jié)點(diǎn)之間的關(guān)系一般可以表示成一棵樹，它被稱為解答樹。搜索算法的搜索過程實(shí)際上就是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的結(jié)點(diǎn)的過程。廣度優(yōu)先搜索算法中，解答樹上結(jié)點(diǎn)的擴(kuò)展是沿結(jié)點(diǎn)深度的“斷層”進(jìn)行，也就是說，結(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)來說，求解問題的價(jià)值是相同的，我們可以按任意順序來擴(kuò)展它們。這里采用的原則是先生成的結(jié)點(diǎn)先擴(kuò)展。廣度優(yōu)先搜索算法的搜索順序如下圖：A B C D E F GH 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)。搜索過程中不斷地從隊(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)過，則將它加入到隊(duì)列尾，否則將它丟棄，再從隊(duì)列頭取出結(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)問題需要給出解的路徑，則要保存每個(gè)結(jié)點(diǎn)的來源，也就是它是從哪一個(gè)節(jié)點(diǎn)擴(kuò)展來的。對(duì)于不同的問題，用廣度優(yōu)先搜索法的算法基本上都是一樣的。但表示問題狀態(tài)的結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)、新結(jié)點(diǎn)是否目標(biāo)結(jié)點(diǎn)和是否重復(fù)結(jié)點(diǎn)的判斷等方面則有所不同，對(duì)具體的問題需要進(jìn)行具體分析。 （二）算法結(jié)構(gòu)數(shù)據(jù)初始化；設(shè)隊(duì)列首指針CLOSED：=0；隊(duì)尾指針OPEN：=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； 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ù)目。注：另一種說法稱廣度優(yōu)先搜索算法的空間復(fù)雜度為 O(BM)，其中 B 是最大分支系數(shù)，而 M 是樹的最長(zhǎng)路徑長(zhǎng)度。由于對(duì)空間的大量需求，因此廣度優(yōu)先搜索算法并不適合解非常大的問題。2、時(shí)間復(fù)雜度最差情形下，廣度優(yōu)先搜索算法必須尋找所有到可能節(jié)點(diǎn)的所有路徑，因此其時(shí)間復(fù)雜度為 O(|V| + |E|)，其中 |V| 是節(jié)點(diǎn)的數(shù)目，而 |E| 是圖中邊的數(shù)目。3、完全性廣度優(yōu)先搜索算法具有完全性。這里指無論圖形的種類如何，只要目標(biāo)存在，則廣度優(yōu)先搜索算法一定會(huì)找到。然而，若目標(biāo)不存在，且圖為無限大，則廣度優(yōu)先搜索算法將不收斂（不會(huì)結(jié)束）。4、最佳解若所有邊的長(zhǎng)度相等，廣度優(yōu)先搜索算法是最佳解亦即它找到的第一個(gè)解，距離根節(jié)點(diǎn)的邊數(shù)目一定最少；但對(duì)一般的圖來說，廣度優(yōu)先搜索算法并不一定回傳最佳解。這是因?yàn)楫?dāng)圖形為加權(quán)圖（亦即各邊長(zhǎng)度不同）時(shí)，廣度優(yōu)先搜索算法仍然回傳從根節(jié)點(diǎn)開始，經(jīng)過邊數(shù)目最少的解；而這個(gè)解距離根節(jié)點(diǎn)的距離不一定最短。這個(gè)問題可以使用考慮各邊權(quán)值，廣度優(yōu)先搜索算法的改良算法成本一致搜尋法（en:uniform-cost search）來解決。然而，若非加權(quán)圖形，則所有邊的長(zhǎng)度相等，廣度優(yōu)先搜索算法就能找到最近的最佳解。（四）廣度優(yōu)先搜索算法在圖論中的應(yīng)用 尋找圖中所有連接元件（Connected Component）。一個(gè)連接元件是圖中的最大相連子圖。 尋找連接元件中的所有節(jié)點(diǎn)。 尋找非加權(quán)圖中任兩點(diǎn)的最短路徑。 測(cè)試一圖是否為二分圖。 (Reverse) CuthillMcKee算法。三、廣度優(yōu)先搜索算法在圖論中應(yīng)用的具體分析（一）尋找連接元件由起點(diǎn)開始，執(zhí)行廣度優(yōu)先搜索算法后所經(jīng)過的所有節(jié)點(diǎn)，即為包含起點(diǎn)的一個(gè)連接元件。（二）測(cè)試是否二分圖廣度優(yōu)先搜索算法可以用以測(cè)試二分圖。從任一節(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é)束時(shí)這種情形未發(fā)生，則此圖為一二分圖。（三）尋找非加權(quán)圖中任兩點(diǎn)的最短路徑最短路問題是圖論中的核心問題之一，它是許多更深層算法的基礎(chǔ)。同時(shí)，該問題有著大量的生產(chǎn)實(shí)際的背景。不少問題從表面上看與最短路問題沒有什么關(guān)系，卻也可以歸結(jié)為最短路問題。最短路的定義：在最短路問題中，給出的是一有向加權(quán)圖G=(V,E)，在其上定義的加權(quán)函數(shù)W:ER為從邊到實(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)開始，訪問每一個(gè)被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á)的。由于搜索過程是一級(jí)一級(jí)展開的，因此能快速的找到s點(diǎn)到其能到達(dá)的頂點(diǎn)的最短路徑。對(duì)于那些不能從s點(diǎn)可達(dá)的剩余頂點(diǎn)z，令。廣度優(yōu)先搜索較為正式的表述是算法的結(jié)尾處，意味著或者v從s是不可達(dá)的。（附件中有用matlab語言實(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)過的直接子節(jié)點(diǎn)加入隊(duì)列中。3、若隊(duì)列為空，表示整張圖都檢查過了亦即圖中沒有欲搜尋的目標(biāo)。結(jié)束搜尋并回傳“找不到目標(biāo)”。4、重復(fù)步驟2。四、最短路中常用算法的比較其它最短路算法與廣度優(yōu)先搜索算法的比較列表算法時(shí)間復(fù)雜度空間復(fù)雜度編程復(fù)雜度適用范圍BFSO(E+V)O(E+V)簡(jiǎn)單非加權(quán)圖（窄）DijkstraO()或O(E+V)logV)O()或O（E+V）簡(jiǎn)單或相對(duì)復(fù)雜不含負(fù)權(quán)的圖（窄）FloydO（）O（）簡(jiǎn)單實(shí)數(shù)圖（廣）Bellman-FordO（VE）O(E+V)簡(jiǎn)單實(shí)數(shù)圖（廣）SPFAO(E)O(E+V)簡(jiǎn)單實(shí)數(shù)圖（廣）通過比較分析分析，可知：l 對(duì)于非加權(quán)圖，可用簡(jiǎn)便而又快捷的廣度優(yōu)先搜索算法找出最短路徑。l Dijkstra算法的效率高，但是也有局限性，就是對(duì)于含負(fù)權(quán)的圖無能為力。l Floyd算法簡(jiǎn)單、易于實(shí)現(xiàn)，且適用范圍廣，但時(shí)間和空間復(fù)雜度過高。l Bellman-Ford算法對(duì)于所有最短路長(zhǎng)存在的圖都適用而且簡(jiǎn)單，但是時(shí)間復(fù)雜度高，效率常常不盡人意。l SPFA算法可以說是綜合了上述算法的優(yōu)點(diǎn)。它的效率同樣很不錯(cuò)，而且對(duì)于最短路中存在的所有圖都適用，無論是否存在負(fù)權(quán)。它的編程復(fù)雜度也很低，是高性價(jià)比的算法。五、總結(jié)廣度優(yōu)先搜索算法是一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位址，徹底地搜索整張圖，直到找到結(jié)果為止。廣度優(yōu)先搜索算法并不使用經(jīng)驗(yàn)法則算法。對(duì)于非加權(quán)圖，廣度優(yōu)先搜索算法可以快速的找出最短路徑（假設(shè)存在最短路徑），但其在最短路問題中的適用范圍較窄。當(dāng)最短路問題中出現(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。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中選一點(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);endif sum(size(Q)=0 disp(找不到目標(biāo)。);end有什么問題可以聯(lián)系我。姓名：劉明浩電話：13582379254 QQ：4165885009