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

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

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

例如，對右圖中的有向圖，應用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下頁的表中。0141301050306011111s:distance:path:由源點1到頂點5的路徑為：1->4->3->5方法一：重復調(diào)用Dijkstra算法n次可輪流以每一個頂點為源點，重復調(diào)用狄克斯特拉算法函數(shù)Dijkstra()n次，即可求得所有頂點之間的最短路徑和最短距離。利用Dijkstra()函數(shù)求所有頂點之間的最短路徑算法如下。其中，distance[i][j]中存放著從頂點i到頂點j的最短距離，path[i][j]中存放著從頂點i到頂點j的最短路徑的前一頂點下標。voidShortPath(AdjMWGraph&G,int**distance,int**path){Intn=G.NumOfVertices();for(inti=0;i<n;i++)Dijkstra(G,i,distance［i］,path［i］);}由于狄克斯特拉算法的時間復雜度是O(n2)，所以n次調(diào)用狄克斯特拉算法的時間復雜度是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）到頂點j的距離。

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

di,jk=L[i][j](因為從i到j不允許經(jīng)過任何其他頂點）若1≤k≤n,

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

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

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

+

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

=di,jk-1

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

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

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

；（2）過頂點1：D0[3][1]+D0[1][2]=1+2=3

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

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

而在從Dk-1到Dk的計算過程中也只用到第k行和第k列，也就是說，在這一步的計算過程中用到的數(shù)據(jù)都不會被覆蓋。故在算法中僅使用一個矩陣D即可FLOYD算法FLOYD(int*L,intn){int*D=(int*)malloc((n+1)*(n+1)*sizeof(int));DL{將數(shù)組L復制到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，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?目標：使裝入背包中物品的總價值最大約束條件：裝入的物品總重不得超過C海盜盜寶問題海盜有一背包，最大容積為9，現(xiàn)有5件寶物：體積si分別是2、3、4、5和4公斤價值vi分別是3、7、5、9和8

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

若背包容量c=0、1，則無法裝入物品1，得到背包價值為0若背包容量c=2、3、4、5、6，7，8，9則可裝入物品1，得到背包價值為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考慮兩個物品的情況當n=2時，有兩個物品，s1=2,v1=3，s2=3,v2=7

若背包容量c=0、1，得到背包價值為0若背包容量c=2，可裝入物品1，得總價值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個物品中選取物品裝入容量為j的背包所得的最大價值。則要尋求的是m[n][c]。m[i][j]是以下兩個值的最大值

（1）m[i-1][j]:即不裝入物品i,背包價值與僅考慮前i-1個物品時情況相同；（2）v[i]+m[i-1][j-s[i]]:即裝入物品i,再從前i-1個物品中選取，使背包剩余容積j-s[i]價值最大化。構(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=8012345678900000000000100333333332003771010101010300377101012121540037710101216165018背包容量j從前i個物品中選取構(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)造價值數(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++)//計算前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];}}

//計算最后一行的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