算法設計與分析多段圖最短路徑問題.doc

關于多段圖最短路徑問題的探討摘要：本文主要描述的是分別用動態(tài)規(guī)劃法、貪心法和分支限界法來解決多段圖最短路徑問題時的情況，并在附錄中附有實際問題的程序來輔助闡述觀點。文章首先闡述了各個方法的原理，主要的思路是通過輸入一組數(shù)據(jù)，比較三者的輸出結果的準確性以及運行時間，以之為基礎來分析、討論三者的性能區(qū)別。另外，眾所周知，多段圖是有向圖的一個簡單的模型，它在有向圖的基礎上忽略了兩點之間的線的雙向性的問題，并且對點與點之間的線有很多的要求，從而把圖簡化為可分為幾段的模式，文章最后講述了若這幾種方法運行到有向圖中的情況，幾種方法的對比和它們比較適應的使用情況的討論，并給出了自己的建議。關鍵字：多段圖最短路徑問題 動態(tài)規(guī)劃法 分支限界法 多段圖與有向圖的關系 有向圖最短路徑算法引言：當前社會，關于最短路徑的問題屢屢出現(xiàn)。例如在開車自駕游的一個過程中，排除其他影響因素，從一個地點到另一點，這個時候必然是希望有一條距離最短的路程來盡量減少消耗的時間以及花費的（它們在模型中被稱為代價），市場上對該問題的解決有很大的需求，因此，這里我將討論多段圖的最短路徑的問題。在早些時間的課程中，我們學習過數(shù)據(jù)結構這門課程，其中就包括最短路徑這方面的討論。當時老師給我們介紹了分別面向單源（Dijkstra算法）與非單源（Floyd算法）兩種問題的算法法-，這是我們最早的對最短路徑方面的理解，也是我們接觸的比較早的關于圖的問題。在這學期的算法課程中，我們學習了許多了方法，包括貪心法、動態(tài)規(guī)劃法等算法，它們把以前學習的許多方法都命名并歸納分類起來，其中有許多算法都是可以用來解決這個最短路徑的問題的，并且該問題作為一個圖的問題，對該問題的繼續(xù)探討優(yōu)化的需求很大，本文將就不同算法在解決該最短路徑問題時的不同方法進行對比并給出該問題在不同基礎上不同的最終解決方案。由于時間的限制，本文將重點分析動態(tài)規(guī)劃法下的情況，并會對圖的情況加以簡化、限制，最后會對其他的圖做一些拓展。首先，對多段圖最短路徑問題進行介紹，設圖G=(V, E)是一個帶權有向連通圖，如果把頂點集合V劃分成k個互不相交的子集Vi（2kn, 1ik），使得E中的任何一條邊(u, v)，必有uVi，vVi+m（1ik, 1i+mk），則稱圖G為多段圖，稱sV1為源點，tVk為終點。多段圖的最短路徑問題是求從源點到終點的最小代價路徑。由于多段圖將頂點劃分為k個互不相交的子集，所以，多段圖劃分為k段，每一段包含頂點的一個子集。不失一般性，將多段圖的頂點按照段的順序進行編號，同一段內(nèi)頂點的相互順序無關緊要。假設圖中的頂點個數(shù)為n，則源點s的編號為0，終點t的編號為n-1，并且，對圖中的任何一條邊(u, v)，頂點u的編號小于頂點v的編號。這里我們討論的多段圖是可以分段的，各段之間的關系最好是單向的，即對該有向圖來說，圖中是沒有環(huán)的存在的。1.貪心法貪心法在解決問題的策略上目光短淺，只根據(jù)當前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結果，這個選擇都不會改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。本例中利用的貪心算法，是每當要選擇下一個結點時，總是選擇與當前結點間代價最小的點，這就叫做總是優(yōu)先局部最優(yōu)解。以此得到最終的解序列。這里舉一個貪心法的拓展例子Dijkstra算法。Dijkstra算法是一種最短路徑算法，用于計算一個節(jié)點到其它所有節(jié)點的最短路徑，動態(tài)路由協(xié)議OSPF中就用到了Dijkstra算法來為路由計算最短路徑。算法本身并不是按照我們的正常思維習慣，我們一般會，從原點遍歷所有與之相連的節(jié)點，找到最短路徑，再從最短路徑上的那個點遍歷與之相連的所有其它點（原點除外），然后依次類推。這樣做雖然可以算出一個樹形，但是在大多數(shù)情況下，這種算法會產(chǎn)生很多次優(yōu)路徑，也就是說非最短路徑。Dijkstra算法的大概過程：假設有兩個集合或者說兩個表，表A和表B表A表示生成路徑，表B表示最后確定的路徑1.從原點出發(fā)，遍歷檢查所有與之相連的節(jié)點，將原點和這些節(jié)點存放到表A中，并記錄下兩節(jié)點之間的代價。2.將代價最小的代價值和這兩節(jié)點移動到表B中（其中一個是原點）。3.把這個節(jié)點所連接的子節(jié)點找出，放入到表A中，算出子節(jié)點到原點的代價4.重復第二步和第三步直到表A為空。然后根據(jù)表B中的數(shù)據(jù)算出最優(yōu)樹。維基百科中還有另一種說法，Dijkstra算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。我們以E所有邊的集合，而邊的權重則由權重函數(shù)w:E0,定義。因此，w(u,v)就是從頂點u到頂點v的非負花費值(cost)。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。已知有V中有頂點s及t，Dijkstra算法可以找到s到t的最低花費路徑(i.e.最短路徑)。這個算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。具體算法見附錄。2.動態(tài)規(guī)劃法這里先討論用動態(tài)規(guī)劃法的解法?？紤]多段圖的最短路徑問題的填表形式。用一個數(shù)組costn作為存儲子問題解的表格，costi表示從頂點i到終點n-1的最短路徑，數(shù)組pathn存儲狀態(tài)，pathi表示從頂點i到終點n-1的路徑上頂點i的下一個頂點。則： costi=mincij+costj (ijn且頂點j是頂點i的鄰接點) （式6.7）pathi=j (使cij+costj最小的j) （式6.8）對多段圖的邊(u, v)，用cuv表示邊上的權值，將從源點s到終點t的最短路徑記為d(s, t)，則從源點0到終點9的最短路徑d(0, 9)由下式確定：d(0, 9)=minc01+d(1, 9), c02+d(2, 9), c03+d(3, 9)，這是最后一個階段的決策，它依賴于d(1, 9)、d(2, 9)和d(3, 9)的計算結果，而由此模式推知，d(1, 9)=minc14+d(4, 9), c15+d(5, 9)，d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9)，d(3, 9)=minc35+d(5, 9), c36+d(6, 9)，每一個d（i，n-1）都是通過mincik+d(k,n-1)得到的ki&kn-1;再往后推的過程和以上的過程類似，將這些產(chǎn)生式得到以后，會發(fā)現(xiàn)他們的求解除了兩點之間的代價外，在例子中，他們都依賴于d(7, 9)=c79和d(8, 9)=c89，而他們都是可以從圖上直接得到的。這樣再從末尾一層一層往上推就可以得到最終的答案了。算法主要由三部分組成：第一部分是初始化部分，其時間性能為O(n)；第二部分是依次計算各個頂點到終點的最短路徑，由兩層嵌套的循環(huán)組成，外層循環(huán)執(zhí)行n-1次，內(nèi)層循環(huán)對所有出邊進行計算，并且在所有循環(huán)中，每條出邊只計算一次。假定圖的邊數(shù)為m，則這部分的時間性能是O(m)；第三部分是輸出最短路徑經(jīng)過的頂點，其時間性能是O(n)。所以，算法的時間復雜性為O(n+m)。為了實現(xiàn)時間的分析，在程序后添加了輸出運行時間的函數(shù)，以便于對比分析。具體算法、具體代碼及實驗結果見附錄1。3.分支限界法再討論當用分支限界法用來解決多段圖路徑問題的過程：首先對該多段圖應用貪心法求得近似解，并算出其代價路徑。將其作為多段圖最短路徑問題的上界。而把每一段最小的代價相加，可以得到一個非常簡單的下界。于是，就可以得到了目標函數(shù)的一個大致的范圍。由于多段圖將頂點劃分為k個互不相交的子集，所以，多段圖劃分為k段，一旦某條路徑的一些段被確定后，就可以并入這些信息并計算部分解的目標函數(shù)值的下界。一般情況下，對于一個正在生成的路徑，假設已經(jīng)確定了i段（1ik），其路徑為(r1, r2, , ri, ri+1)，此時，該部分解的目標函數(shù)值的計算方法即限界函數(shù)如下：應用分支限界法同樣求解附錄中圖所示多段圖的最短路徑問題，具體的搜索過程是這樣進行的，首先考慮根節(jié)點，根據(jù)限界函數(shù)算出目標函數(shù)的值，然后下一個結點的選擇在本例中有三種情況， 這里每種情況下的目標函數(shù)值下界都要算出來并且加以比較，下界的計算方法為除了加上選定點與初始點之間的距離外，以后的第一個點選擇一選定點為初始點到下段最小代價的路徑，以后的段與段之間的代價都按他們之間最小的代價來計算。這樣再加上根節(jié)點與初始階段之間的最小代價，就得到這種情況下的解了。在得到的代價中，找出最小的代價，并以之為初始結點循環(huán)往下做，直到到達目標結點。結論： 程序的運行截圖如附錄所示。分析各個方法的整個過程得到以下思考：1.貪心法、動態(tài)規(guī)劃法和分支限界法都可以用來解決多段最短路徑問題，然而在這種情況相比之下，貪心法的運算效率比較高，因為它不像另外兩種方法一樣，需要涉及到許多的點。由于這里并沒有找到函數(shù)有效地給程序計時（time函數(shù)很不精確，而對于小程序來說，就沒有什么參考性）。因此這里我們就以本題的數(shù)據(jù)為例，用一個笨方法，看各個方法訪問了多少數(shù)據(jù)，可以看到，動態(tài)規(guī)劃法由于需要填表，并有一個相關的迭代問題，它幾乎涉及了所有的點；而分支限界法，它通過貪心法設置的上下限，并以他們?yōu)橐罁?jù)進行剪枝，減少了許多的運算量。而貪心法，訪問了最少的點。2.就結果準確性來看，就本題例子來看，貪心法結果為0 2 4 7 9，路徑的代價為20；動態(tài)分配法采取的路徑為：0 3 5 8 9，路徑的代價為16；而分支限界法，結果為0 3 5 8 9，路徑的代價為16?？梢钥闯?，在這個方面，動態(tài)分配法和分支限界法都達到了預期的結果，相比直線，貪心法的誤差就比較大了。由以上的討論，我們可以看出分支限界法的綜合性能比較好，他和動態(tài)規(guī)劃法在解決多段最短路徑問題時都可以得到正確解，而貪心法雖然可以省時間與空間，但結果不準確是它的缺點。各方法都是有利有弊的。因此在選擇方法時，還應當根據(jù)實際情況。當只需要大概的一個解時，當然是要用省時省力的貪心法；如果對結果又比較高的要求的話，那么就要采取動態(tài)規(guī)劃法或分支限界法。那么dijkstra算法呢，他的明顯優(yōu)點就是它的多用性，他可以求任意一點到其他某一點的距離，但是他訪問的數(shù)據(jù)量很大，幾乎要訪問所有的邊（相對于貪心法而言），因此這里來說，在單純的解決多段最短路徑問題時，他們的功能都差不多，而在解決其他較復雜的圖時，Dijkstra算法有明顯的優(yōu)越性，但當然，作為貪心法的一種，他的結果的準確性不是那么的高。Dijkstra算法在本質(zhì)上為貪心算法,每一步的選擇為當前步的最優(yōu),復雜度為O(n*n)。動態(tài)規(guī)劃法是可以看作是對分支限界法的改進。分支限界算法,每一步的擴散為當前耗散度的最優(yōu),復雜度為(沒算)其實，他們各有各的優(yōu)缺點，可以嘗試將他們混合起來用，揚長避短，像動態(tài)規(guī)劃法和分支限界法，我們是不是可以試著在動態(tài)規(guī)劃法的過程中像分支限界法里一樣，設置范圍，并且過程中對肯定不會是最后結果的數(shù)據(jù)“剪枝”。這樣就可以提高運行速率了。結論（必須精確、有條理、清晰與簡要）：建議（直接從結論中得出）：附錄Dijstra算法（邊的拓展）While（!(每一個dv=最短路徑)）If（存在一條從u到v的邊） If(du+w(u,v)=0; i-)2.1 對頂點i的每一個鄰接點j，根據(jù)式6.7計算costi;2.2 根據(jù)式6.8計算pathi;3輸出最短路徑長度cost0;4. 輸出最短路徑經(jīng)過的頂點：4.1 i=04.2 循環(huán)直到pathi=n-1 4.2.1 輸出pathi;4.2.2 i=pathi;用分支限界法求解多段圖的最短路徑問題的算法：1根據(jù)限界函數(shù)計算目標函數(shù)的下界down；采用貪心法得到上界up； 2將待處理結點表PT初始化為空； 3for (i=1; i=1) 5.1 對頂點u的所有鄰接點v 5.1.1 根據(jù)式9.3計算目標函數(shù)值lb; 5.1.2 若lb=up，則將i,lb存儲在表PT中； 5.2 如果i= =k-1且葉子結點的lb值在表PT中最小， 則輸出該葉子結點對應的最優(yōu)解； 5.3 否則，如果i= =k-1且表PT中的葉子結點的lb值不是最小，則 5.3.1 up=表PT中的葉子結點最小的lb值; 5.3.2 將表PT中目標函數(shù)值超出up的結點刪除； 5.4 u=表PT中l(wèi)b最小的結點的v值； 5.5 i=表PT中l(wèi)b最小的結點的i值；i+;動態(tài)規(guī)劃法解決多段圖最短路徑問題：/*多段圖最短路徑問題總結:costi表示從頂點i到終點n-1的最短路徑，pathi表示從頂點i到終點n-1的路徑上頂點i的下一個頂點；下面的公式重點：costi=minc(ij)+costjpathi=使c(ij)+costj最小的j; c(ij)表示i和j頂點之間的距離*/具體代碼如下：#include#include#define INFINITY 32767#define MAX 20_int64 start,end;int min6,Part;typedef structchar vexsMAX; /頂點信息int vexnum,arcnum; int arcsMAXMAX; /保存兩個頂點之間的邊長Graph; /圖的結構體struct nodeint part,node1,node2,lb,previous;struct node *next;void CreateGraph(Graph &G)/初始化多段圖int i,j;start=clock();printf(請輸入頂點數(shù)和邊數(shù)：);/scanf(%d %d,&G.vexnum,&G.arcnum);G.vexnum=10; /頂點數(shù)G.arcnum=18; /邊的數(shù) for(i=0;iG.vexnum;i+)G.vexsi=i;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)G.arcsij=INFINITY;printf(請按以下格式輸入邊的代價（頂點1 頂點2 兩點之間邊的代價，頂點標號從0開始）：n);for(k=0;kG.arcnum;k+)scanf(%d %d %d,i,j,G.arcsij);int getDown(Graph G)/分支限界法求下界int j,k,i,n,n0,down=0,initial620;/initial數(shù)組用來存儲第i段有哪些結點min0=INFINITY;for(i=0;i6;i+)for(j=0;j20;j+)initialij=0;j=0;for(i=0;iG.vexnum;i+)if(G.arcs0iINFINITY)initial0j+=i;if(G.arcs0imin0)min0=G.arcs0i;Part=1;down+=mini;i=0;while(initiali+0!=G.vexnum-1)n=0;j=0;mini=INFINITY;while(initiali-1j+!=0)k=0;n0=n;while(k+)G.vexnum)if(G.arcsinitiali-1j-1k-1INFINITY)initialin+=k-1;if(G.arcsinitiali-1j-1k-1mini)mini=G.arcsinitiali-1j-1k-1;if(miniINFINITY)down+=mini;Part+;return down;int Greedy(Graph G,int flag,int up)/貪心法int min=INFINITY,m=flag;printf(%d,flag);for(int i=0;iG.vexnum;i+)if(G.arcsmimin)min=G.arcsmi;flag=i;if(flag);up=Greedy(G,flag,up);else printf(-%dn,flag);return up+min;void path(Graph G,int up)/分支限界法int down,i,j,k,u,lb,flag=1,previous=0;struct node *p,*end,*PT,*q,*ST,*End,*mins;down=getDown(G);printf(n若用分支限界法，該題的結果取值范圍為%d,%d。n,down,up);PT=NULL;end=NULL;ST=NULL,End=NULL;/PT用來存儲合格的點，ST表用來存儲由于拓展被刪除的點i=1;u=0; /求解第i段,u表示頂點，u是那個已確定的頂點while(flag)/ 5.1對頂點u的所有鄰接點v/5.1.1 根據(jù)式9.3計算目標函數(shù)值lb;/5.1.2 若lb=up，則將i,lb存儲在表PT中；for(j=0;jG.arcsuj)for(k=0;kG.vexnum;k+)/確定了結點以后找到由他出發(fā)最小的代價if(G.arcsjkmini)mini=G.arcsjk;lb=G.arcsuj+mini;for(int l=i+1;l0)/計算lblb+=G.arcsPreviousU;while(Previous!=0)p=PT;while(p!=NULL)if(p-node1=Previous&p-node2=U)lb+=G.arcsPreviousU;U=Previous;Previous=p-previous;break;if(lbpart=i+1;p-node1=u;p-node2=j;p-lb=lb;p-next=NULL;p-previous=previous;printf(%d-%d,代價%d,上一個結點為%dn,p-node1,p-node2,p-lb,p-previous);if(PT=NULL) PT=p;else end-next=p;end=p;end-next=NULL;q=PT;lb=INFINITY;while(q!=NULL)if(q-lblb;q=q-next;printf(%d %d lb=%d,mins-node1,mins-node2,lb);if(p=q & G.arcsend-node2G.vexnum-1node2;arrayPart-2=p-node1;i=Part-3;while(i=0)arrayi=p-previous;i-;q=PT;while(q-node2!=arrayp-previous)q+;if(i0)arrayi-1=q-node1;p=q;printf(最短路徑為：);for(i=0;i,arrayi);if(inode1=mins-node1&p-node2=mins-node2)/刪除PT鏈表中已被拓展的結點并把他添加到ST鏈表中if(ST=NULL)ST=p-next;elseEnd-next=p-next;End=p-next;End-next=NULL;PT=PT-next;/printf(刪除的結點是：%d %dn,p-next-node1,p-next-node2);/*elseprintf(刪除的結點是：%d %dn,p-next-node1,p-next-node2);while(p-next!=NULL)if(p-next-node1=mins-node1&p-next-node2=mins-node2)if(ST=NULL)ST=p-next;elseEnd-next=p-next;End=p-next;End-next=NULL;