多種方法求多段圖的最短路徑問題 算法設(shè)計與分析課程設(shè)計

1、武漢理工大學(xué)算法設(shè)計與分析課程設(shè)計學(xué) 號： 算法設(shè)計與分析b大 作 業(yè)題 目多種方法解決多段圖的最短路徑問題學(xué) 院計算機(jī)科學(xué)與技術(shù)學(xué)院專 業(yè)軟件工程班 級姓 名指導(dǎo)教師2014年12月26日多種方法解決多段圖的最短路徑問題摘 要多段圖的最短路徑問題是求從源點到終點的最小代價路徑。本文主要描述的是分別用動態(tài)規(guī)劃法、貪心法和分支限界法來解決多段圖最短路徑問題時的情況。文章首先闡述了各個方法的原理，主要的思路是通過輸入一組數(shù)據(jù)，比較三者的輸出結(jié)果的準(zhǔn)確性以及運行時間，以之為基礎(chǔ)來分析、討論三者的性能區(qū)別。文章最后講述了若這幾種方法運行到有向圖中的情況，幾種方法的對比和它們比較適應(yīng)的使用情況的討論，并

2、給出了自己的建議。關(guān)鍵字：多段圖最短路徑問題；動態(tài)規(guī)劃法；分支限界法；貪心法i目 錄摘 要ii1 引 言12 問題描述13 貪心法求解23.1 貪心法介紹23.2 問題分析34 動態(tài)規(guī)劃法求解34.1 動態(tài)規(guī)劃法介紹34.2 問題分析45 分支限界法求解55.1 分支限界法介紹55.2 問題分析56 程序清單66.1 源代碼66.2 結(jié)果截圖97 結(jié)果分析98 課程體會109 參考文獻(xiàn)10ii1 引 言當(dāng)前社會，關(guān)于最短路徑的問題屢屢出現(xiàn)。例如在開車自駕游的一個過程中，排除其它影響因素，從一個地點到另一點，這個時候必然是希望有一條距離最短的路程來盡量減少消耗的時間以及花費的（它們在模型中被稱為

3、代價），市場上對該問題的解決有很大的需求，因此，這里我將討論多段圖的最短路徑的問題。大二開設(shè)的數(shù)據(jù)結(jié)構(gòu)課程中就包括最短路徑這方面問題的討論。當(dāng)時老師介紹了分別面向單源（dijkstra算法）與非單源（floyd算法）兩種問題的算法這是我們最早的對最短路徑方面的理解，也是我們接觸的比較早的關(guān)于圖的問題。在這學(xué)期的算法設(shè)計與分析課程中，我們學(xué)習(xí)了很多基本的算法設(shè)計技術(shù)，蠻力法、分治法、減治法、動態(tài)規(guī)劃法、貪心法、回溯法、分支限界法等，它們把以前學(xué)習(xí)的諸多方法都命名并歸納分類起來，其中有多種算法都可以用來解決最短路徑問題，并且該問題作為一個圖的問題，對該問題的繼續(xù)探討優(yōu)化的需求很大、本文將就不同算法

4、在解決該最短路徑問題時的不同方法進(jìn)行對比并給出該問題在不同基礎(chǔ)上不同的最終解決方案。由于時間的限制，本文將重點分析動態(tài)規(guī)劃法下的情況，并會對圖的情況加以簡化、限制，最后會對其它的圖做一些拓展。2 問題描述設(shè)圖g=(v, e)是一個帶權(quán)有向連通圖，如果把頂點集合v劃分成k個互不相交的子集vi（2kn, 1ik），使得e中的任何一條邊(u, v)，必有uvi，vvi+m（1ik, 1i+mk），則稱圖g為多段圖，稱sv1為源點，tvk為終點。多段圖的最短路徑問題是求從源點到終點的最小代價路徑。多段圖的最短路徑問題是求從源點到終點的最小代價路徑。由于多段圖將頂點劃分為k個互不相交的子集，所以，可以將

5、多段圖劃分為k段，每一段包含頂點的一個子集。不失一般性，將多段圖的頂點按照段的順序進(jìn)行編號，同一段內(nèi)頂點的相互順序無關(guān)緊要。假設(shè)圖中的頂點個數(shù)為n，則源點s的編號為0，終點t的編號為n-1，并且，對圖中的任何一條邊(u, v)，頂點u的編號小于頂點v的編號。這里我們討論的多段圖是可以分段的，各段之間的關(guān)系最好是單向的，即對該有向圖來說，圖中是沒有環(huán)的存在的。3 貪心法求解3.1 貪心法介紹貪心法是一種簡單有效的方法。它在解決問題的策略上只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)

6、。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。本例中利用的貪心算法，是每當(dāng)要選擇下一個結(jié)點時，總是選擇與當(dāng)前結(jié)點間代價最小的點，這就叫做總是優(yōu)先局部最優(yōu)解，以此得到最終的解序列。這里舉一個貪心法的拓展例子dijkstra算法。dijkstra算法是一種最短路徑算法，用于計算一個節(jié)點到其它所有節(jié)點的最短路徑，動態(tài)路由協(xié)議ospf中就用到了dijkstra算法來為路由計算最短路徑。算法本身并不是按照我們的正常思維習(xí)慣，我們一般會從原點遍歷所有與之相連的節(jié)點，找到最短路徑，再從最短路徑上的那個點遍歷與之相連的所有其它點（原點除外），然后依次類推。這樣做雖然可以算出一個樹形，但是在

7、大多數(shù)情況下，這種算法會產(chǎn)生很多次優(yōu)路徑，也就是說非最短路徑。dijkstra算法的大概過程：假設(shè)有兩個集合或者說兩個表，表a和表b，表a表示生成路徑，表b表示最后確定的路徑（1） 從原點出發(fā)，遍歷檢查所有與之相連的節(jié)點，將原點和這些節(jié)點存放到表a中，并記錄下兩節(jié)點之間的代價；（2） 將代價最小的代價值和這兩節(jié)點移動到表b中（其中一個是原點）；（3） 把這個節(jié)點所連接的子節(jié)點找出，放入到表a中，算出子節(jié)點到原點的代價；（4） 重復(fù)第二步和第三步直到表a為空。然后根據(jù)表b中的數(shù)據(jù)算出最優(yōu)樹。維基百科中還有另一種說法，dijkstra算法的輸入包含了一個有權(quán)重的有向圖g，以及g中的一個來源頂點s。

8、我們以v表示g中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。我們以e所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù)w:e0,定義。因此，w(u,v)就是從頂點u到頂點v的非負(fù)花費值(cost)。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。已知有v中有頂點s及t，dijkstra算法可以找到s到t的最低花費路徑(i.e.最短路徑)。這個算法也可以在一個圖中，找到從一個頂點s到任何其它頂點的最短路徑。3.2 問題分析以起始點為中心向外層層擴(kuò)展，直到擴(kuò)展到終點為止。dijstra算法（邊的拓展）while

9、（!(每一個dv=最短路徑)）if（存在一條從u到v的邊） if(du+w(u,v)dv) dv= du+w(u,v);4 動態(tài)規(guī)劃法求解4.1 動態(tài)規(guī)劃法介紹動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），可以人為地引進(jìn)時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。動態(tài)規(guī)劃是考察問題的一種途徑，或是求解某類問題的一種方法。動態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比其它方法求解更為方便。動態(tài)規(guī)劃

10、法設(shè)計算法一般分成三個階段：(1) 劃分子問題：將原問題分解為若干個子問題， 每個子問題對應(yīng)一個決策階段，并且子問題之間具有重疊關(guān)系；(2) 確定動態(tài)規(guī)劃函數(shù)：根據(jù)子問題之間的重疊關(guān)系找到子問題滿足的遞推關(guān)系式(即動態(tài)規(guī)劃函數(shù))，這是動態(tài)規(guī)劃法的關(guān)鍵；(3) 填寫表格：設(shè)計表格，以自底向上的方式計算各個子問題的解并填表，實現(xiàn)動態(tài) 原問題的解 原問題 填 表子問題1子問題2子問題n規(guī)劃過程。4.2 問題分析設(shè)數(shù)組costn存儲最短路徑長度，costj表示從源點s到頂點j的最短路徑長度，數(shù)組pathn記錄狀態(tài)轉(zhuǎn)移，pathj表示從源點到頂點j的路徑上頂點的前一個頂點，動態(tài)規(guī)劃法求解多段圖的最短路徑

11、問題的算法如下：輸入：多段圖的代價矩陣輸出：最短路徑長度及路徑1. 循環(huán)變量j從1n-1重復(fù)下述操作，執(zhí)行填表工作： 1.1 考察頂點j的所有入邊，對于邊(i, j)e： 1.1.1 costj=mincosti+cij; 1.1.2 pathj=使costi+cij最小的i; 1.2 j+;2. 輸出最短路徑長度costn-1;3. 循環(huán)變量i=pathn-1，循環(huán)直到pathi=0： 3.1 輸出pathi; 3.2 i=pathi;第一部分是依次計算各個頂點到終點的最短路徑，由兩層嵌套的循環(huán)組成，外層循環(huán)執(zhí)行n-1次，內(nèi)層循環(huán)對所有入邊進(jìn)行計算，并且在所有循環(huán)中，每條入邊只計算一次。假定

12、圖的邊數(shù)為m，則這部分的時間性能是o(m)；第二部分是輸出最短路徑經(jīng)過的頂點，設(shè)多段圖劃分為k段，其時間性能是o(k)。所以，該算法的時間復(fù)雜性為o(n+k)。 5 分支限界法求解5.1 分支限界法介紹分支限界法按廣度優(yōu)先策略搜索問題的解空間樹，在搜索過程中，對待處理的結(jié)點根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的可能取值，從中選取使目標(biāo)函數(shù)取得極值（極大或極?。┑慕Y(jié)點優(yōu)先進(jìn)行廣度優(yōu)先搜索，從而不斷調(diào)整搜索方向，盡快找到問題的解。5.2 問題分析討論當(dāng)用分支限界法用來解決多段圖路徑問題的過程：首先對該多段圖應(yīng)用貪心法求得近似解，并算出其代價路徑。將其作為多段圖最短路徑問題的上界。而把每一段最小的代價相加，可以

13、得到一個非常簡單的下界。于是，就可以得到了目標(biāo)函數(shù)的一個大致的范圍。由于多段圖將頂點劃分為k個互不相交的子集，所以，多段圖劃分為k段，一旦某條路徑的一些段被確定后，就可以并入這些信息并計算部分解的目標(biāo)函數(shù)值的下界。一般情況下，對于一個正在生成的路徑，假設(shè)已經(jīng)確定了i段（1ik），其路徑為(r1, r2, , ri, ri+1)，此時，該部分解的目標(biāo)函數(shù)值的計算方法即限界函數(shù)如下：應(yīng)用分支限界法同樣求解多段圖的最短路徑問題，具體的搜索過程是這樣進(jìn)行的，首先考慮根節(jié)點，根據(jù)限界函數(shù)算出目標(biāo)函數(shù)的值，這里每種情況下的目標(biāo)函數(shù)值下界都要算出來并且加以比較，下界的計算方法為除了加上選定點與初始點之間的距

14、離外，以后的第一個點選擇一選定點為初始點到下段最小代價的路徑，以后的段與段之間的代價都按它們之間最小的代價來計算。這樣再加上根節(jié)點與初始階段之間的最小代價，就得到這種情況下的解了。在得到的代價中，找出最小的代價，并以之為初始結(jié)點循環(huán)往下做，直到到達(dá)目標(biāo)結(jié)點。算法如下：1根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的下界down；采用貪心法得到上界up；2將待處理結(jié)點表pt初始化為空；3for (i=1; i=1) 5.1 對頂點u的所有鄰接點v 5.1.1 計算目標(biāo)函數(shù)值lb; 5.1.2 若lb=up，則將i,lb存儲在表pt中； 5.2 如果i= =k-1且葉子結(jié)點的lb值在表pt中最小， 則輸出該葉子結(jié)點對

15、應(yīng)的最優(yōu)解； 5.3 否則，如果i= =k-1且表pt中的葉子結(jié)點的lb值不是最小，則 5.3.1 up=表pt中的葉子結(jié)點最小的lb值; 5.3.2 將表pt中目標(biāo)函數(shù)值超出up的結(jié)點刪除； 5.4 u=表pt中l(wèi)b最小的結(jié)點的v值； 5.5 i=表pt中l(wèi)b最小的結(jié)點的i值；i+;6 程序清單6.1 源代碼#includeconst int n = 20;const int max = 1000;int arcnn; int backpath(int n);int creatgraph();int creatgraph()int i, j, k;int weight;int vnum, a

16、rcnum;cout輸入頂點的個數(shù)和邊的個數(shù)：vnumarcnum;for (i = 0; i vnum; i+)for (j = 0; j vnum; j+)arcij = max;for (k = 0; k arcnum; k+)coutijweight;arcij = weight;return vnum;int backpath(int n)int i, j, temp;int costn;int pathn;for(i = 0; i n; i+)costi = max;pathi = -1;cost0 = 0;for(j = 1; j = 0; i-)if (arcij + cost

17、i costj)costj = arcij + costi;pathj = i;cout= 0)cout-pathi;i = pathi;coutendl;return costn-1;int main()int n = creatgraph( );int pathlen = backpath(n);cout最短路徑的長度是：pathlenendl;return 0;6.2 結(jié)果截圖7 結(jié)果分析（1） 貪心法、動態(tài)規(guī)劃法和分支限界法都可以用來解決多段最短路徑問題，然而在這種情況相比之下，貪心法的運算效率比較高，因為它不像另外兩種方法一樣，需要涉及到許多的點。可以看到，動態(tài)規(guī)劃法由于需要填表，并

18、有一個相關(guān)的迭代問題，它幾乎涉及了所有的點；而分支限界法，它通過貪心法設(shè)置的上下限，并以它們?yōu)橐罁?jù)進(jìn)行剪枝，減少了許多的運算量。而貪心法，訪問了最少的點。（2） 就結(jié)果準(zhǔn)確性來看，就本題例子來看，貪心法結(jié)果為0 2 4 7 9，路徑的代價為20；動態(tài)分配法采取的路徑為：0 3 5 8 9，路徑的代價為16；而分支限界法，結(jié)果為0 3 5 8 9，路徑的代價為16?？梢钥闯?，在這個方面，動態(tài)分配法和分支限界法都達(dá)到了預(yù)期的結(jié)果，相比直線，貪心法的誤差就比較大了。由以上的討論，我們可以看出分支限界法的綜合性能比較好，它和動態(tài)規(guī)劃法在解決多段最短路徑問題時都可以得到正確解，而貪心法雖然可以省時間與空

19、間，但結(jié)果不準(zhǔn)確是它的缺點。各方法都是有利有弊的。因此在選擇方法時，還應(yīng)當(dāng)根據(jù)實際情況。當(dāng)只需要大概的一個解時，當(dāng)然是要用省時省力的貪心法；如果對結(jié)果又比較高的要求的話，就要采取動態(tài)規(guī)劃法或分支限界法。dijkstra算法的明顯優(yōu)點就是它的多用性，它可以求任意一點到其它某一點的距離，但是它訪問的數(shù)據(jù)量很大，幾乎要訪問所有的邊（相對于貪心法而言），因此這里來說，在單純的解決多段最短路徑問題時，它們的功能都差不多，而在解決其它較復(fù)雜的圖時，dijkstra算法有明顯的優(yōu)越性，但當(dāng)然，作為貪心法的一種，它的結(jié)果的準(zhǔn)確性不是那么的高。dijkstra算法在本質(zhì)上為貪心算法,每一步的選擇為當(dāng)前步的最優(yōu),復(fù)雜度為o(n*n)。動態(tài)規(guī)劃法是可以看作是對分支限界法的改進(jìn)。其實，它們各有各的優(yōu)缺點，可以嘗試將它們混合起來用，揚(yáng)長避短，設(shè)置范圍，并且過程中對肯定不會是最后結(jié)果的數(shù)據(jù)“剪枝”。這樣就可以提高運行速率了。8 課程體會算法分析與設(shè)計是一門非常重要的課程。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有“程序=算法+數(shù)據(jù)結(jié)構(gòu)”這個公式。算法的學(xué)習(xí)對于培養(yǎng)一個人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。作為it行業(yè)學(xué)生，學(xué)習(xí)算法無疑會增強(qiáng)自己的競爭力，修煉自己的