lecture_11_4動態(tài)規(guī)劃所有點對的最短距離

1、第七章動態(tài)規(guī)劃第七章動態(tài)規(guī)劃7.5所有點對的最短路徑問題 對于一個各邊權(quán)值均大于0的有n個頂點的帶權(quán)有向圖G=(V,E)，求所有頂點之間的最短路徑和最短距離。圖的鄰接矩陣表示法123V =( b )( a )28196123L= 0 2 9 0 68 1 0復(fù)習(xí)Dijkstra算法 其其基本思想基本思想是，設(shè)置頂點集合是，設(shè)置頂點集合S S并不斷地作并不斷地作貪心選擇貪心選擇來擴充這個集合。一個頂點屬于集合來擴充這個集合。一個頂點屬于集合S S當(dāng)且僅當(dāng)從源到該頂點的最短路徑長度已知。當(dāng)且僅當(dāng)從源到該頂點的最短路徑長度已知。初始時，初始時，S S中僅含有源點。設(shè)中僅含有源點。設(shè)u u是是G G的

2、某一個的某一個頂點，把從源點到頂點，把從源點到u u且中間只經(jīng)過且中間只經(jīng)過S S中頂點的路中頂點的路稱為從源到稱為從源到u u的特殊路徑，并用數(shù)組的特殊路徑，并用數(shù)組distdistance記記錄當(dāng)前每個頂點所對應(yīng)的最短特殊路徑長度。錄當(dāng)前每個頂點所對應(yīng)的最短特殊路徑長度。DijkstraDijkstra算法每次從算法每次從V-SV-S中取出具有最短特殊路中取出具有最短特殊路長度的頂點長度的頂點u u，將，將u u添加到添加到S S中，同時對數(shù)組中，同時對數(shù)組distdistance作必要的修改。一旦作必要的修改。一旦S S包含了所有包含了所有V V中頂中頂點，點，distdistance就

3、記錄了從源到所有其它頂點之間就記錄了從源到所有其它頂點之間的最短路徑長度。的最短路徑長度。 算法中，我們不斷更新以下三個數(shù)組： s數(shù)組: si，當(dāng)頂點i加入S時，si置1 Distance數(shù)組: Distancei記錄原點到 頂點i的最短特殊路徑長度。 path數(shù)組： pathi記錄頂點i在其最短特殊路徑上的前驅(qū)頂點。由該數(shù)組可求得原點到各點的最短路徑。如：設(shè)源點是頂點1, path數(shù)組如下例如例如，對右圖中的有向圖，應(yīng)用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下頁的表中。0141301050306011111s:distance:path:由源點1到頂點5的路徑為：1

4、-4-3-5方法一：重復(fù)調(diào)用Dijkstra算法n次 可輪流以每一個頂點為源點，重復(fù)調(diào)用狄克斯特拉算法函數(shù)Dijkstra() n次，即可求得所有頂點之間的最短路徑和最短距離。 利用Dijkstra()函數(shù)求所有頂點之間的最短路徑算法如下。其中，distanceij中存放著從頂點i到頂點j的最短距離，pathij中存放著從頂點i到頂點j的最短路徑的前一頂點下標(biāo)。 voidShortPath(AdjMWGraph &G, int *distance, int *path) Int n=G.NumOfVertices(); for(inti=0;in;i+) Dijkstra(G,i,di

5、stancei,pathi); 由于狄克斯特拉算法的時間復(fù)雜度是O(n2)，所以n次調(diào)用狄克斯特拉算法的時間復(fù)雜度是O(n3)。該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 例如上圖中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。子問題的構(gòu)造 原問題：每個頂點到其他所有頂點的最短距離 最小的子問題D0：從頂點i （不得經(jīng)過任何其他頂點）到頂點j的距離； 子問題D1：從頂點i（可以經(jīng)過頂點1，不得經(jīng)過其他任何其他頂點）到頂點j的距離。 子問題Dk：從頂點i（可以經(jīng)過頂點1、頂點2、頂點k，不得經(jīng)過任何其他頂點）到頂點j的距離。 子問題Dn：從頂點i（可以經(jīng)過頂點1、頂點2、頂點n

6、 ）到頂點j的距離。 即原問題遞推關(guān)系的建立 由由di,jk-1推出推出di,jk的過程如下的過程如下若若k=0, di,jk=Lij (因為從因為從i到到j(luò)不允許經(jīng)過任何其他頂點）不允許經(jīng)過任何其他頂點）若若1k n, di,jk=mindi,jk-1 , di,kk-1 +dk,jk-1 子問題子問題Dk-1：從頂點從頂點i（可以經(jīng)過頂點（可以經(jīng)過頂點1、頂點、頂點2、頂點、頂點k-1）到頂點）到頂點j的距離。的距離。 子問題子問題Dk：從頂點從頂點i（可以經(jīng)過頂點（可以經(jīng)過頂點1、頂點、頂點2、頂點頂點k-1、頂點頂點k）到頂點）到頂點j的距離。的距離。從子問題從子問題Dk-1：到子問題

7、：到子問題Dk，僅僅多考慮了，僅僅多考慮了一個一個頂點頂點k。我們需要重新考慮從我們需要重新考慮從i到到j(luò)的距離：的距離： 頂點頂點i到頂點到頂點j，是不是從，是不是從k走會更近？走會更近？ 如果從頂點如果從頂點i到頂點到頂點j從頂點從頂點k走更近，則走更近，則i到到j(luò)的距離的距離di,jk =i到到k的距離的距離di,kk-1 + k到到j(luò)的距離的距離dk,jk-1 如果頂點如果頂點i到頂點到頂點j從頂點從頂點k走更遠(yuǎn)，甚至走不通，走更遠(yuǎn)，甚至走不通，則保持原來的距離不變則保持原來的距離不變 di,jk =di,jk-1 。由由di,jk-1推出推出di,jk的過程，主要考慮的是頂點的過程，

8、主要考慮的是頂點k的加入會引起什么變化？由不允許路過頂點的加入會引起什么變化？由不允許路過頂點k到允許路過頂點到允許路過頂點k，有些點間的距離是否會，有些點間的距離是否會變的更近。變的更近。 例：考慮下圖所示的帶權(quán)有向圖，求所有頂點之間的最短距離。V =( b )( a )12328196123L= 0 2 9 0 68 1 0計算過程123281960 2 9 0 68 1 0D0 =0 2 98 0 61 3 0D1 =0 2 88 0 61 3 0D2 =0 2 87 0 61 3 0D3 =Di,jk：從頂點：從頂點i（可以經(jīng)過頂點（可以經(jīng)過頂點1、頂點、頂點2、頂點頂點k）到頂點）到

9、頂點j的距離。的距離。在D1中，第1行和第一列是不變的，因為說從頂點1到頂點j或頂點j到頂點1：允許經(jīng)過頂點1是沒有意義的D123:從頂點2到頂點3的距離（可以經(jīng)過頂點1）（1）不經(jīng)過頂點1： 仍是D023=6；（2）過頂點1： D021+D013=8+9=17 取最小值6D132:從頂點3到頂點2的距離（可以經(jīng)過頂點1）（1）不經(jīng)過頂點1： 仍是D032= ；（2）過頂點1： D031+D012=1+2=3 取最小值3D213:從頂點1到頂點3的距離（也可以經(jīng)過頂點2）（1）不經(jīng)過頂點2： 仍是D113=9；（2）過頂點2： D112+D123=2+6=8 取最小值8算法設(shè)計重要發(fā)現(xiàn)：在從重

10、要發(fā)現(xiàn)：在從Dk-1到到Dk的計算過程中中，的計算過程中中，第第k行和第行和第k列是不變的。（列是不變的。（因為說從因為說從頂點頂點k到頂點到頂點j或頂點或頂點j到頂點到頂點k允許經(jīng)過頂點允許經(jīng)過頂點k是沒有意義的）是沒有意義的） 而在從而在從Dk-1到到Dk的計算過程中也只用的計算過程中也只用到第到第k行和第行和第k列，也就是說，在這一步列，也就是說，在這一步的計算過程中用到的數(shù)據(jù)都不會被覆蓋。的計算過程中用到的數(shù)據(jù)都不會被覆蓋。故在算法中僅使用一個矩陣故在算法中僅使用一個矩陣D即可即可FLOYD算法 FLOYD(int *L,int n) int *D=(int *)malloc(n+1)

11、*(n+1)*sizeof(int); D L 將數(shù)組L復(fù)制到D; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;j16S4=5v4=9子問題的構(gòu)造 當(dāng)n=1時:只有一個物品， s1=2,v1=3 若背包容量c=0、1，則無法裝入物品1，得到背包價值為0若背包容量c=2、3、4、5、6，7，8，9則可裝入物品1，得到背包價值為3。 C10=0 C11=0 C12=3 C13=3 C14=3 C15=3 C16=3 C17=3 C18=3 C19=3考慮兩個物品的情況 當(dāng)n=2時，有兩個物品， s1=2,v1=3，s2=3,v2=7 若背包容量c=0、1，得到背包價

12、值為0若背包容量c=2，可裝入物品1，得總價值m22=3若背包容量c=3，m23=7若背包容量c=4, m24=7若背包容量c=5, m25=10若不裝物品2，m23=m13=3若裝入物品2，m23=v2+m13-3=7+0=7m26=10 m27=10 m28=10 m29=10 若不裝物品2，m25=m15=3若裝入物品2，m25=v2+m15-3=7+3=7遞推關(guān)系的建立 用mij來表示從前i個物品中選取物品裝入容量為j的背包所得的最大價值。則要尋求的是mnc。 mij是以下兩個值的最大值（1） mi-1j: 即不裝入物品i,背包價值與僅考慮前i-1個物品時情況相同； （2）vi+mi-

13、1j-si:即裝入物品i,再從前i-1個物品中選取，使背包剩余容積j-si價值最大化。構(gòu)造價值數(shù)組S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8012345678900000000000100333333332003771010101010300377101012121240037710101216165018背包容量j從前i個物品中選取S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=80123456789000000000001003333333320037710101010103003771010121215400377101

14、01216165018背包容量j從前i個物品中選取構(gòu)造最優(yōu)解012345678900000000000100333333332003771010101010300377101012121540037710101216165003781011151618因m59m49, 物品5被裝入，剩余c=9-s5=5因m45m35, 物品4被裝入，剩余c=9-s4=0 void Knapsack(int t v,int w,int c,int n,float mN)/構(gòu)造價值數(shù)組m int i, j;for(i=0; i=n; i+)mi0=0;for(j=0; j=c; j+)m0j=0;for(i=1;

15、 n; i+) /計算前計算前n-1行行 for(j=1; jwi; j+) mij= mi-1j; for(j= wi; j mi-1j) mij=t; else mij=mi-1j; /計算最后一行的mnct= vn+ mn-1c-wn;If ( t mn-1c ) mnc=telse mnc=mn-1c; void Trackback(int mN, int w, int c, int n, int x)int i,j;for(i=n;i0;i-) if(mic=mi-1c) xi=0 else xi=1;c=c-wi; 上機作業(yè) 編程求解0-1背包問題P140的練習(xí) 7.4 A=“xz

16、yzzyx”, B=“zxyyzxz”,求A和B 的最長公共子序列 7.9 7.21 練習(xí) 有四種面值的硬幣：1分 5 分 7分 11分，要找錢15分，最少要找多少個硬幣？ 用動態(tài)規(guī)劃來解決選做題1、設(shè)A和B是兩個字符串。我們要用最少的字符操作將字符串A轉(zhuǎn)換為字符串B。這里所說的字符串操作包括：（1） 刪除一個字符；（2） 插入一個字符；（3） 將一個字符改為另一個字符；將字符串A變換為字符串B所用的最少字符操作成為字符串A到字符串B的編輯距離，記為d(A,B)。試設(shè)計一個有效算法，對任給的兩個字符串A和B，求他們的編輯距離d(A,B)A=“abcde”,B=“acdefa” 攔截導(dǎo)彈攔截導(dǎo)彈 某國為了防御敵