lecture_11_4動(dòng)態(tài)規(guī)劃所有點(diǎn)對(duì)的最短距離

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

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

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

4、-4-3-5方法一：重復(fù)調(diào)用Dijkstra算法n次 可輪流以每一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)調(diào)用狄克斯特拉算法函數(shù)Dijkstra() n次，即可求得所有頂點(diǎn)之間的最短路徑和最短距離。 利用Dijkstra()函數(shù)求所有頂點(diǎn)之間的最短路徑算法如下。其中，distanceij中存放著從頂點(diǎn)i到頂點(diǎn)j的最短距離，pathij中存放著從頂點(diǎn)i到頂點(diǎn)j的最短路徑的前一頂點(diǎn)下標(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); 由于狄克斯特拉算法的時(shí)間復(fù)雜度是O(n2)，所以n次調(diào)用狄克斯特拉算法的時(shí)間復(fù)雜度是O(n3)。該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 例如上圖中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。子問(wèn)題的構(gòu)造 原問(wèn)題：每個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短距離 最小的子問(wèn)題D0：從頂點(diǎn)i （不得經(jīng)過(guò)任何其他頂點(diǎn)）到頂點(diǎn)j的距離； 子問(wèn)題D1：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1，不得經(jīng)過(guò)其他任何其他頂點(diǎn)）到頂點(diǎn)j的距離。 子問(wèn)題Dk：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、頂點(diǎn)k，不得經(jīng)過(guò)任何其他頂點(diǎn)）到頂點(diǎn)j的距離。 子問(wèn)題Dn：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、頂點(diǎn)n

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

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

8、主要考慮的是頂點(diǎn)k的加入會(huì)引起什么變化？由不允許路過(guò)頂點(diǎn)的加入會(huì)引起什么變化？由不允許路過(guò)頂點(diǎn)k到允許路過(guò)頂點(diǎn)到允許路過(guò)頂點(diǎn)k，有些點(diǎn)間的距離是否會(huì)，有些點(diǎn)間的距離是否會(huì)變的更近。變的更近。 例：考慮下圖所示的帶權(quán)有向圖，求所有頂點(diǎn)之間的最短距離。V =( b )( a )12328196123L= 0 2 9 0 68 1 0計(jì)算過(guò)程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：從頂點(diǎn)：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)、頂點(diǎn)2、頂點(diǎn)頂點(diǎn)k）到頂點(diǎn)）到

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

10、要發(fā)現(xiàn)：在從Dk-1到到Dk的計(jì)算過(guò)程中中，的計(jì)算過(guò)程中中，第第k行和第行和第k列是不變的。（列是不變的。（因?yàn)檎f(shuō)從因?yàn)檎f(shuō)從頂點(diǎn)頂點(diǎn)k到頂點(diǎn)到頂點(diǎn)j或頂點(diǎn)或頂點(diǎn)j到頂點(diǎn)到頂點(diǎn)k允許經(jīng)過(guò)頂點(diǎn)允許經(jīng)過(guò)頂點(diǎn)k是沒(méi)有意義的）是沒(méi)有意義的） 而在從而在從Dk-1到到Dk的計(jì)算過(guò)程中也只用的計(jì)算過(guò)程中也只用到第到第k行和第行和第k列，也就是說(shuō)，在這一步列，也就是說(shuō)，在這一步的計(jì)算過(guò)程中用到的數(shù)據(jù)都不會(huì)被覆蓋。的計(jì)算過(guò)程中用到的數(shù)據(jù)都不會(huì)被覆蓋。故在算法中僅使用一個(gè)矩陣故在算法中僅使用一個(gè)矩陣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子問(wèn)題的構(gòu)造 當(dāng)n=1時(shí):只有一個(gè)物品， s1=2,v1=3 若背包容量c=0、1，則無(wú)法裝入物品1，得到背包價(jià)值為0若背包容量c=2、3、4、5、6，7，8，9則可裝入物品1，得到背包價(jià)值為3。 C10=0 C11=0 C12=3 C13=3 C14=3 C15=3 C16=3 C17=3 C18=3 C19=3考慮兩個(gè)物品的情況 當(dāng)n=2時(shí)，有兩個(gè)物品， s1=2,v1=3，s2=3,v2=7 若背包容量c=0、1，得到背包價(jià)

12、值為0若背包容量c=2，可裝入物品1，得總價(jià)值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來(lái)表示從前i個(gè)物品中選取物品裝入容量為j的背包所得的最大價(jià)值。則要尋求的是mnc。 mij是以下兩個(gè)值的最大值（1） mi-1j: 即不裝入物品i,背包價(jià)值與僅考慮前i-1個(gè)物品時(shí)情況相同； （2）vi+mi-

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

14、01216165018背包容量j從前i個(gè)物品中選取構(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)造價(jià)值數(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+) /計(jì)算前計(jì)算前n-1行行 for(j=1; jwi; j+) mij= mi-1j; for(j= wi; j mi-1j) mij=t; else mij=mi-1j; /計(jì)算最后一行的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; 上機(jī)作業(yè) 編程求解0-1背包問(wèn)題P140的練習(xí) 7.4 A=“xz

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