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

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

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

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

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

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

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

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

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

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

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

11、問題的算法如下：輸入：多段圖的代價(jià)矩陣輸出：最短路徑長度及路徑1. 循環(huán)變量j從1n-1重復(fù)下述操作，執(zhí)行填表工作： 1.1 考察頂點(diǎn)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;第一部分是依次計(jì)算各個(gè)頂點(diǎn)到終點(diǎn)的最短路徑，由兩層嵌套的循環(huán)組成，外層循環(huán)執(zhí)行n-1次，內(nèi)層循環(huán)對所有入邊進(jìn)行計(jì)算，并且在所有循環(huán)中，每條入邊只計(jì)算一次。假定

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

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

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

15、應(yīng)的最優(yōu)解； 5.3 否則，如果i= =k-1且表pt中的葉子結(jié)點(diǎn)的lb值不是最小，則 5.3.1 up=表pt中的葉子結(jié)點(diǎn)最小的lb值; 5.3.2 將表pt中目標(biāo)函數(shù)值超出up的結(jié)點(diǎn)刪除； 5.4 u=表pt中l(wèi)b最小的結(jié)點(diǎn)的v值； 5.5 i=表pt中l(wèi)b最小的結(jié)點(diǎn)的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輸入頂點(diǎn)的個(gè)數(shù)和邊的個(gè)數(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） 貪心法、動(dòng)態(tài)規(guī)劃法和分支限界法都可以用來解決多段最短路徑問題，然而在這種情況相比之下，貪心法的運(yùn)算效率比較高，因?yàn)樗幌窳硗鈨煞N方法一樣，需要涉及到許多的點(diǎn)?？梢钥吹?，動(dòng)態(tài)規(guī)劃法由于需要填表，并

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

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