lecture-11-4動(dòng)態(tài)規(guī)劃所有點(diǎn)對的最短距離

第七章動(dòng)態(tài)規(guī)劃7.5所有點(diǎn)對的最短路徑問題對于一個(gè)各邊權(quán)值均大于0的有n個(gè)頂點(diǎn)的帶權(quán)有向圖G=(V,E)，求所有頂點(diǎn)之間的最短路徑和最短距離。圖的鄰接矩陣表示法123V=(b)(a)28196123L=

029061∞0復(fù)習(xí)Dijkstra算法其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。 初始時(shí)，S中僅含有源點(diǎn)。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源點(diǎn)到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組distance記錄當(dāng)前每個(gè)頂點(diǎn)所對應(yīng)的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點(diǎn)u，將u添加到S中，同時(shí)對數(shù)組distance作必要的修改。一旦S包含了所有V中頂點(diǎn)，distance就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長度。算法中，我們不斷更新以下三個(gè)數(shù)組：s數(shù)組:s[i]，當(dāng)頂點(diǎn)i加入S時(shí)，s[i]置1Distance數(shù)組:Distance[i]記錄原點(diǎn)到頂點(diǎn)i的最短特殊路徑長度。path數(shù)組：path[i]記錄頂點(diǎn)i在其最短特殊路徑上的前驅(qū)頂點(diǎn)。由該數(shù)組可求得原點(diǎn)到各點(diǎn)的最短路徑。如：設(shè)源點(diǎn)是頂點(diǎn)1,path數(shù)組如下

例如，對右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過程列在下頁的表中。0141301050306011111s:distance:path:由源點(diǎn)1到頂點(diǎn)5的路徑為：1->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)之間的最短路徑算法如下。其中，distance[i][j]中存放著從頂點(diǎn)i到頂點(diǎn)j的最短距離，path[i][j]中存放著從頂點(diǎn)i到頂點(diǎn)j的最短路徑的前一頂點(diǎn)下標(biāo)。voidShortPath(AdjMWGraph&G,int**distance,int**path){Intn=G.NumOfVertices();for(inti=0;i<n;i++)Dijkstra(G,i,distance［i］,path［i］);}由于狄克斯特拉算法的時(shí)間復(fù)雜度是O(n2)，所以n次調(diào)用狄克斯特拉算法的時(shí)間復(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)造原問題：每個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短距離最小的子問題D0：從頂點(diǎn)i（不得經(jīng)過任何其他頂點(diǎn)）到頂點(diǎn)j的距離；子問題D1：從頂點(diǎn)i（可以經(jīng)過頂點(diǎn)1，不得經(jīng)過其他任何其他頂點(diǎn)）到頂點(diǎn)j的距離。子問題Dk：從頂點(diǎn)i（可以經(jīng)過頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)k，不得經(jīng)過任何其他頂點(diǎn)）到頂點(diǎn)j的距離。子問題Dn：從頂點(diǎn)i（可以經(jīng)過頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)n）到頂點(diǎn)j的距離。

——即原問題遞推關(guān)系的建立由di,jk-1推出di,jk的過程如下若k=0,

di,jk=L[i][j](因?yàn)閺膇到j(luò)不允許經(jīng)過任何其他頂點(diǎn)）若1≤k≤n,

di,jk=min{di,jk-1,di,kk-1+dk,jk-1}子問題Dk-1：從頂點(diǎn)i（可以經(jīng)過頂點(diǎn)1、頂點(diǎn)2、……、頂點(diǎn)k-1）到頂點(diǎn)j的距離。

子問題Dk：從頂點(diǎn)i（可以經(jīng)過頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)k-1、頂點(diǎn)k）到頂點(diǎn)j的距離。從子問題Dk-1：到子問題Dk，僅僅多考慮了一個(gè)頂點(diǎn)k。我們需要重新考慮從i到j(luò)的距離：

頂點(diǎn)i到頂點(diǎn)j，是不是從k走會更近？如果從頂點(diǎn)i到頂點(diǎn)j從頂點(diǎn)k走更近，則i到j(luò)的距離di,jk=i到k的距離di,kk-1

+

k到j(luò)的距離dk,jk-1如果頂點(diǎn)i到頂點(diǎn)j從頂點(diǎn)k走更遠(yuǎn)，甚至走不通，則保持原來的距離不變di,jk

=di,jk-1

。由di,jk-1推出di,jk的過程，主要考慮的是頂點(diǎn)k的加入會引起什么變化？由不允許路過頂點(diǎn)k到允許路過頂點(diǎn)k，有些點(diǎn)間的距離是否會變的更近。例：考慮下圖所示的帶權(quán)有向圖，求所有頂點(diǎn)之間的最短距離。V=(b)(a)12328196123L=

029061∞0計(jì)算過程12328196029061∞0D0=029806130D1=028806130D2=028706130D3=Di,jk：從頂點(diǎn)i（可以經(jīng)過頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)k）到頂點(diǎn)j的距離。在D1中，第1行和第一列是不變的，因?yàn)檎f從頂點(diǎn)1到頂點(diǎn)j或頂點(diǎn)j到頂點(diǎn)1：允許經(jīng)過頂點(diǎn)1是沒有意義的D1[2][3]:從頂點(diǎn)2到頂點(diǎn)3的距離（可以經(jīng)過頂點(diǎn)1）（1）不經(jīng)過頂點(diǎn)1：仍是D0[2][3]=6；（2）過頂點(diǎn)1：D0[2][1]+D0[1][3]=8+9=17

取最小值6D1[3][2]:從頂點(diǎn)3到頂點(diǎn)2的距離（可以經(jīng)過頂點(diǎn)1）（1）不經(jīng)過頂點(diǎn)1：仍是D0[3][2]=∞

；（2）過頂點(diǎn)1：D0[3][1]+D0[1][2]=1+2=3

取最小值3D2[1][3]:從頂點(diǎn)1到頂點(diǎn)3的距離（也可以經(jīng)過頂點(diǎn)2）（1）不經(jīng)過頂點(diǎn)2：仍是D1[1][3]=9；（2）過頂點(diǎn)2：D1[1][2]+D1[2][3]=2+6=8

取最小值8算法設(shè)計(jì)重要發(fā)現(xiàn)：在從Dk-1到Dk的計(jì)算過程中中，第k行和第k列是不變的。（因?yàn)檎f從頂點(diǎn)k到頂點(diǎn)j或頂點(diǎn)j到頂點(diǎn)k允許經(jīng)過頂點(diǎn)k是沒有意義的）

而在從Dk-1到Dk的計(jì)算過程中也只用到第k行和第k列，也就是說，在這一步的計(jì)算過程中用到的數(shù)據(jù)都不會被覆蓋。故在算法中僅使用一個(gè)矩陣D即可FLOYD算法FLOYD(int*L,intn){int*D=(int*)malloc((n+1)*(n+1)*sizeof(int));DL{將數(shù)組L復(fù)制到D};for(k=0;k<n;k++)

for(i=0;i<n;i++)

for(j=0;j<n;j++)

D[i*n+j]=min(D[i*n+j],D[i*n+k]+D[k*n+j]);}7.60-1背包問題給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?目標(biāo)：使裝入背包中物品的總價(jià)值最大約束條件：裝入的物品總重不得超過C海盜盜寶問題海盜有一背包，最大容積為9，現(xiàn)有5件寶物：體積si分別是2、3、4、5和4公斤價(jià)值vi分別是3、7、5、9和8

請給出裝載方案，使背包價(jià)值達(dá)到最大。S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8C=9一開始，見物品就裝，物品1、2、3全裝入，背包裝滿了，得到背包總價(jià)值為15，這是不是最大價(jià)值呢？S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8考慮只有前三個(gè)物品的情況物品4該不該裝？有兩個(gè)選擇：（1）不裝，背包價(jià)值不變，為15S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9（2）裝入，它占去的體積為5，得到價(jià)值為9，剩下容積4最多可以裝下多大價(jià)值？考慮只有前4個(gè)物品的情況這是一個(gè)n=3(從前三個(gè)物品中選擇），容量c=4的子問題。目前最優(yōu)：裝入物品2和物品4，總價(jià)值為16若已知這個(gè)子問題的解是：裝物品2，得價(jià)值為7。S1=2v1=3S3=4v3=5S4=5v4=9（2）裝入物品4，它占去的體積為5，得到價(jià)值為9，剩下容積4最多可以裝下多大價(jià)值？S2=3v2=7S1=2v1=3S3=4v3=5S4=5v4=9S5=4v5=8考慮5個(gè)物品的情況S2=3v2=7物品5該不該裝？(1)不裝，得到背包價(jià)值仍為16（2）若裝入物品5，占用體積為4，得價(jià)值為8，背包剩余容積為5。如何在前4個(gè)物品中選擇裝入，使背包價(jià)值最大化？這是n=4,c=5的一個(gè)子問題。若得到該子問題的解為：裝入物品1、2，得價(jià)值為10S1=2v1=3S3=4v3=5S5=4v5=8考慮5個(gè)物品的情況S2=3v2=7目前最優(yōu)：裝入物品5和1、2，總價(jià)值為18>16S4=5v4=9子問題的構(gòu)造當(dāng)n=1時(shí):只有一個(gè)物品，s1=2,v1=3

若背包容量c=0、1，則無法裝入物品1，得到背包價(jià)值為0若背包容量c=2、3、4、5、6，7，8，9則可裝入物品1，得到背包價(jià)值為3。C[1][0]=0C[1][1]=0C[1][2]=3C[1][3]=3C[1][4]=3C[1][5]=3C[1][6]=3C[1][7]=3C[1][8]=3C[1][9]=3考慮兩個(gè)物品的情況當(dāng)n=2時(shí)，有兩個(gè)物品，s1=2,v1=3，s2=3,v2=7

若背包容量c=0、1，得到背包價(jià)值為0若背包容量c=2，可裝入物品1，得總價(jià)值m[2][2]=3若背包容量c=3，m[2][3]=7若背包容量c=4,m[2][4]=7若背包容量c=5,m[2][5]=10若不裝物品2，m[2][3]=m[1][3]=3若裝入物品2，m[2][3]=v[2]+m[1][3-3]=7+0=7m[2][6]=10m[2][7]=10m[2][8]=10m[2][9]=10若不裝物品2，m[2][5]=m[1][5]=3若裝入物品2，m[2][5]=v[2]+m[1][5-3]=7+3=7遞推關(guān)系的建立用m[i][j]來表示從前i個(gè)物品中選取物品裝入容量為j的背包所得的最大價(jià)值。則要尋求的是m[n][c]。m[i][j]是以下兩個(gè)值的最大值

（1）m[i-1][j]:即不裝入物品i,背包價(jià)值與僅考慮前i-1個(gè)物品時(shí)情況相同；（2）v[i]+m[i-1][j-s[i]]:即裝入物品i,再從前i-1個(gè)物品中選取，使背包剩余容積j-s[i]價(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=8012345678900000000000100333333332003771010101010300377101012121540037710101216165018背包容量j從前i個(gè)物品中選取構(gòu)造最優(yōu)解012345678900000000000100333333332003771010101010300377101012121540037710101216165003781011151618因m[5][9]>m[4][9],物品5被裝入，剩余c=9-s5=5因m[4][5]>m[3][5],物品4被裝入，剩余c=9-s4=0voidKnapsack(inttv[],int

w[],int

c,int

n,float

m[][N]){//構(gòu)造價(jià)值數(shù)組m

inti,j;for(i=0;i<=n;i++)m[i][0]=0;for(j=0;j<=c;j++)m[0][j]=0;for(i=1;<n;i++)//計(jì)算前n-1行

{for(j=1;j<w[i];j++)m[i][j]=m[i-1][j];

for(j=w[i];j<=c;j++){t=v[i]+m[i-1][j-w[i]];if(t>m[i-1][j])

m[i][j]=t;elsem[i][j]=m[i-1][j];}}

//計(jì)算最后一行的m[n][c]t=v[n]+m[n-1][c-w[n]];If(t>m[n-1][c])

m[n][c]=telsem[n][c]=m[n-1][c];}voidTrackback(int

m[][N],intw[],intc,intn,intx[]){int

i,j;for(i=n;i>0;i--)

if(m[i][c]==m[i-1][c])x[i]=0else