第六章 動態(tài)規(guī)劃

1第六章動態(tài)規(guī)劃

6.1動態(tài)規(guī)劃的思想方法

6.2多段圖的最短路徑問題

6.3資源分配問題

6.4設(shè)備更新問題

6.5最長公共子序列問題

6.60/1背包問題

6.7RNA最大堿基對匹配問題26.1動態(tài)規(guī)劃的思想方法

一動態(tài)規(guī)劃的最優(yōu)決策原理

二動態(tài)規(guī)劃實例、貨郎擔(dān)問題

3一動態(tài)規(guī)劃的最優(yōu)決策原理

1.活動過程的分階段決策

2.最優(yōu)性原理

3.最優(yōu)決策的形成

41.活動過程的分階段決策把活動過程劃分為若干個階段，每一階段的決策，依賴于前一階段的狀態(tài)，由決策所采取的動作，使狀態(tài)發(fā)生轉(zhuǎn)移，成為下一階段的決策依據(jù)

52.最優(yōu)性原理無論過程的初始狀態(tài)和初始決策是什么，其余決策都必須相對于初始決策所產(chǎn)生的狀態(tài)，構(gòu)成一個最優(yōu)決策序列

63.最優(yōu)決策的形成令最優(yōu)狀態(tài)為s(2,22)，由此倒推s(2,22)p(2,22)s(1,2)p(1,2)s0

最優(yōu)決策序列：p(2,22)p(1,2)狀態(tài)轉(zhuǎn)移序列：s0s(1,2)s(2,2)7最優(yōu)決策的形成（續(xù)）1）最優(yōu)決策在最后階段形成，然后向前倒推，直到初始階段2）決策的具體結(jié)果及所產(chǎn)生的狀態(tài)轉(zhuǎn)移，由初始階段開始進行計算，然后向后遞歸或迭代，直到最終結(jié)果3）賴以決策的策略或目標，稱為動態(tài)規(guī)劃函數(shù)4）動態(tài)規(guī)劃函數(shù)可以遞歸地定義，也可以用遞推公式表達5）整個決策過程，可以遞歸地進行，或用循環(huán)迭代的方法進行8二動態(tài)規(guī)劃實例、貨郎擔(dān)問題

1.動態(tài)規(guī)劃解貨郎擔(dān)問題的過程

2.復(fù)雜性分析

91.動態(tài)規(guī)劃解貨郎擔(dān)問題的過程1）貨郎擔(dān)問題實例：

4城市的費用矩陣2）動態(tài)規(guī)劃函數(shù)：

d(i,V’)：從頂點i出發(fā)，經(jīng)V’中各頂點一次，最終回到初始出發(fā)點的最短路徑的長度

設(shè)初始出發(fā)點為i

103）工作過程由城市1出發(fā)，經(jīng)城市2,3,4然后返回1的最短路徑長度為：①②③

112.復(fù)雜性分析1）令是從頂點i出發(fā)，返回頂點i所需計算的形式為

d(k,V’–{k})的個數(shù)2）開始計算d(i,V’–{i})時，集合V’–i中有n–1個頂點3）在計算d(k,V’–{k})時，集合V’–{k}的頂點數(shù)目，在不同的決策階段，分別為n-2,┅,04）在整個計算中，需要計算大小為j的不同頂點集合的個數(shù)為，j=0,┅,n-1?？倐€數(shù)為：5）當集合V’–{k}中的城市個數(shù)為j時，為計算

d(k,V’–{k})，需j次加法，j-1次比較

12復(fù)雜性分析（續(xù)）6）從頂點i出發(fā)，經(jīng)其它城市再回到i，總的運算時間為：由二項式定理：令x=y=1,得：7）動態(tài)規(guī)劃方法求解貨郎擔(dān)問題，總花費T為：

136.2多段圖的最短路徑問題

一多段圖的決策過程

二多段圖動態(tài)規(guī)劃算法的實現(xiàn)

14一多段圖的決策過程1.多段圖的最短路徑問題

2.多段圖最短路徑的決策過程

3.例子

4.多段圖最短路徑問題實現(xiàn)步驟151.多段圖的最短路徑問題1）多段圖的定義：有向連通賦權(quán)圖G=<V,E,W>，頂點集合V劃分成

k個不相交的子集，1ik，k≥2，使得E中的任一邊(u,v)，必有u

，v，m≥1，稱G為多段圖。令，稱為源點，為收點2）多段圖的最短路徑問題：求從源點到達收點的最小花費的通路162.多段圖最短路徑的決策過程1）頂點編號：①根據(jù)多段圖的k個不相交的子集，把多段圖劃分為k段，每一段包含頂點的一個子集②頂點集合V中的所有頂點，按照段的順序編號⑴子集中的頂點互不鄰接，它們之間的相互順序無關(guān)緊要⑵頂點個數(shù)為n，源點s的編號為0，收點t的編號為n–1⑶對E中的任何一條邊(u,v)，頂點u的編號小于頂點v的編號

172）決策過程①第一階段，確定第k–1段的所有頂點到達收點t的花費最小的通路，及通路上該頂點的前方頂點編號②第二階段，用第一階段的信息，確定第k–2段的所有頂點到達收點t的花費最小的通路，及通路上該頂點的前方頂點編號③如此依次進行，直到最后確定源點s到達收點t的花費最小的通路，及通路上該頂點的前方頂點編號④最后，從源點的信息的前方頂點編號，遞推地確定整條路徑上的所有頂點編號183）動態(tài)規(guī)劃函數(shù)⑴工作單元描述：

cost[i]：頂點i到達收點t的最小花費

path[i]：頂點i到達收點t的前方頂點編號

route[n]：源點i到達收點t的最短通路上的頂點編號⑵動態(tài)規(guī)劃函數(shù)：

(1)(2)193.例子：求解圖所示的最短路徑問題

i=8：

path[8]=9i=7：

path[7]=9i=6：

path[6]=820例子（續(xù)1）i=5：

path[5]=8i=4：

path[4]=8i=3：

path[3]=521例子（續(xù)2）i=2：

path[2]=3i=1：

path[1]=5i=0：

path[0]=222例子（續(xù)3）path[0]=2path[1]=5path[2]=3path[3]=5path[4]=8path[5]=8path[6]=8path[7]=9

path[8]=9route[0]=0cost[0]=15route[1]=path[route[0]]=path[0]=2route[2]=path[route[1]]=path[0]=3route[3]=path[route[2]]=path[3]=5route[4]=path[route[3]]=path[5]=8route[5]=path[route[4]]=path[8]=9234.多段圖最短路徑問題實現(xiàn)步驟①

對所有的i，0i<n，置cost[i]=

，path[i]=-1cost[n–1]=0②令i=n-2③據(jù)(1),(2)式計算cost[i],path[i]④i=i-1，若i>0，轉(zhuǎn)③；否則，轉(zhuǎn)⑤⑤令i=0，route[0]=0⑥如果riute[i]=n–1，算法結(jié)束；否則，轉(zhuǎn)⑦⑦i=i+1，route[i]=path[route[i–1]]；轉(zhuǎn)⑥24二多段圖動態(tài)規(guī)劃算法的實現(xiàn)

1.數(shù)據(jù)結(jié)構(gòu)

2.算法描述251.數(shù)據(jù)結(jié)構(gòu)structNODE{ //鄰接表結(jié)點的數(shù)據(jù)結(jié)構(gòu)

int v_num; //鄰接頂點的編號

Typelen; //鄰接頂點與該頂點的費用structNODE*next; //下一個鄰接頂點};structNODEnode[n]; //多段圖鄰接表頭結(jié)點Type cost[n]; int route[n]; int path[n]; 262.算法描述（步驟①）4.Typefgraph(structNODEnode[],introute[],intn)5.{inti;7.structNODE*pnode;8.int*path=newint[n];9.Typemin_cost,*cost=newType[n];10.for(i=0;i<n;i++){O(n)11.cost[i]=MAX_TYPE;path[i]=-1;rouet[i]=0;12.}13.cost[n-1]=ZERO_TYPE;

27算法描述（步驟

②③④）14.for(i=n-2;i>=0;i--){O(n+m)15.pnode=node[i]->next;16.while(pnode!=NULL){17.if(pnode->len+cost[pnode->v_num]<cost[i]){18.cost[i]=pnode->len+cost[pnode->v_num];19.path[i]=pnode->v_num;20.}21.pnode=pnode->next;22.}23.}nextlenv_numnextlenv_numnext28算法描述（步驟

⑤⑥⑦）24.i=0;O(k)25.while((route[i]!=n-1)&&(path[i]!=-1)){26.i++;27.route[i]=path[route[i-1]];28.}29.min_cost=cost[0];30.deletepath;deleyecost;31.returnmin_cost;32.}296.3資源分配問題

一資源分配問題的決策過程

二資源分配算法的實現(xiàn)

30一資源分配問題的決策過程

1.資源分配問題

2.目標函數(shù)和約束方程

3.決策過程

4.實現(xiàn)步驟

5.例子

311.資源分配問題資源總數(shù)為r，工程個數(shù)為n。給每項工程投入的資源不同，所獲得的利潤也不同。要求把總數(shù)為r的資源分配給n個工程，以獲得最大利潤的分配方案

322.目標函數(shù)和約束方程把資源r劃分為m個相等的部分，m為整數(shù)利潤函數(shù)：

x份資源分配給第i個工程所得到的利潤分配m份資源給所有工程，所得到的利潤總額為：

使最大的分配方案：

333.決策過程1）定義兩組變量：把x份資源分配給前面i個工程所得到的最大利潤：使最大時，分配給第i個工程的資源份額2）階段劃分

n個工程劃分為n個階段第一階段把x(x=1,,m)份資源分配給第一個工程第i階段把x(x=1,,m)份資源分配給前面i個工程

i=2,,n343）分配份額為x(x=1,,m)

時，第i階段的最大利潤

及第i工程的最優(yōu)分配份額(i=1,,n)第一階段，只把x份資源分配給第一個工程

f1(x)=G1(x)0xmd1(x)=x在第二階段，把x份資源分配給前面兩個工程

f2(x)=max{G2(z)+f1(x–z)}0xm,0zx

d2(x)=使f2(x)達最大的z在第i階段，把x份資源分配給前面i個工程

fi(x)=max{Gi(z)+fi-1(x–z)}0xm,0zx

d2(x)=使fi(x)達最大的z354）分配份額為m時，第i階段的最大利潤gi

及前面i個工程

的最優(yōu)分配份額qi(i=1,,n)5）全局最大利潤optg及所分配工程項目的最大數(shù)目k

6）全局最大利潤下k個工程的最優(yōu)份額optx7）全局最大利潤下分配給第i個工程的最優(yōu)份額

368）分配給其余個工程的剩余的最優(yōu)份額

9）回溯，得到分配給前面各個工程的最優(yōu)份額的遞推關(guān)系式

i=k–1,

,1374.實現(xiàn)步驟1）對各個階段，各個不同份額的資源，計算及2）計算各個階段的最大利潤，及獲得此最大利潤的分配份額3）計算全局的最大利潤optg，總的最優(yōu)分配份額optq

及最大的工程項目說數(shù)目k4）遞推計算各個工程的最優(yōu)分配份額385.例子8個份額的資源，分配給3個工程，其利潤函數(shù)如下第一階段，直接給出

X012345678G10426404550515253G20515406070737475G306154080909598100X012345678F10426404550515253D101234567839例子第二階段

X012345678G20515406070737475G306154080909598100X012345678f10426404550515253d1012345678X=10,11,0f2d2f24551X=20,21,12,0f226915260X=30,31,22,13,0f240312040400X=40,41,32,23,14,0f2454541446060440例子第二階段

X012345678G20515406070737475G306154080909598100X012345678f10426404550515253d1012345678X=50,51,42,33,24,15,0f2d2f2505055666470705X=60,61,52,43,34,25,16,0f251556080867473864X=70,71,62,53,44,35,26,17,0f2525665851009677741004X=80,81,72,63,54,45,36,27,18,0f253576690105110997875110541例子第optg=max(53,110,140)=140q3=8k=3optx=8X012345678gf1042640455051525353d1012345678f2052640607086100110110d2010045445f30526408090106120140140d301004544442二資源分配算法的實現(xiàn)1.數(shù)據(jù)結(jié)構(gòu)

2.算法描述

431.數(shù)據(jù)結(jié)構(gòu)int m; //可分配的資源份額int n; //工程項目個數(shù)Type G[n][m+1]; //工程的利潤表Type optg; //最優(yōu)的總利潤int optq[n]; //工程最優(yōu)分配份額Type f[n][m+1]; //各階段不同資源份額的最大利潤int d[n][m+1]; //f[i][x]最大時,第i項工程的分配份額Type g[n]; //階段的最大利潤int q[n]; //第i階段第i工程最優(yōu)分配份額int optx; //最優(yōu)分配時的資源最優(yōu)分配份額int k; //最優(yōu)分配時的工程項目數(shù)442.算法描述（步驟①）2.Typeallot_res(intn,intm,TypeG[][],intoptq[])3.{4.intoptx,k,i,j,x;5.int*q=newint[n]; //分配工作單元

6.int(*d)[m+1]=newint[n][m+1];7.Type(*f)[m+1]=newType[n][m+1];8.Type*g=newType[n];9.for(j=0;j<=m;j++){ //第一個工程的份額利潤表10.f[0][j]=G[0][j];d[0][j]=j;11.}45算法描述（步驟①）12.for(i=1;i<n;i++){ 13.f[i][0]=G[i][0]+f[i-1][0];d[i][0]=0;15.for(j=1;j<=m;j++){16.f[i][j]=f[i][0];d[i][j]=0;17.for(x=0;x<=j;x++){18.if(f[i][j]<G[i][x]+f[i-1][j-x]){19.f[i][j]=G[i][x]+f[i-1][j-x];20.d[i][j]=x;21.}22.}23.}24.}46算法描述（步驟②③）25.for(i=0;i<n;i++){ 24.g[i]=f[i][0];q[i]=0;25.for(j=1;j<=m;j++)26.if(g[i]<f[i][j])27.{g[i]=f[i][j];q[i]=j;}30.}31.optg=g[0];optx=q[0];k=0;32.for(i=1;i<n;i++){ 33.if(optg<g[i]) 34.{optg=g[i];optx=q[i];k=i;}36.}47算法描述（步驟④）37.if(k<n-1){ //最大編號之后的38.for(i=k+1;i<n;i++) //工程不分配份額39.optq[i]=0;40.for(i=k;i>=0;i--){ //最大編號之前的41.optq[i]=d[i][optx]; //工程分配份額42.optx=optx–optq[i];43.}44.deleteq;deleted;45.deletef;deleteg;46.returnoptg; 47.}

486.4設(shè)備更新問題

一設(shè)備更新問題的決策過程二設(shè)備更新算法的實現(xiàn)

49一設(shè)備更新問題的決策過程1.設(shè)備更新問題：

設(shè)備的性能隨使用年限的增加而變壞，導(dǎo)致收入減少

維修費增加，利潤下降。而設(shè)備的更新，需付出一筆

經(jīng)費，但可增加利潤收入。設(shè)備的更新問題是確定設(shè)

備的最優(yōu)更新策略，使得在一個確定期限里，為公司

創(chuàng)造最大的利潤。50一設(shè)備更新問題的決策過程2.設(shè)備更新的有關(guān)數(shù)據(jù)：I=0一列，表明現(xiàn)有設(shè)備的有關(guān)數(shù)據(jù)；I=1一列，表示第一年購買的設(shè)備的有關(guān)數(shù)據(jù)；其余類推。使用年限中的第0列，表示當年的有關(guān)數(shù)據(jù)，第1列表示使用一年后的有關(guān)數(shù)據(jù)，其余類推；利潤、維修費用、更新費用等行分別表示：在第

i年購買的設(shè)備使用了

j年后，可以創(chuàng)造的利潤、必須付出的維修費用以及進行更新時需要付出的費用。

購買時間I=0I=1I=2I=3I=45使用年限23456012340123012010利潤131211109161514131217161514181716191820維修費用23445112231122112111更新費用252627282920222425262022242520222421222151一設(shè)備更新問題的決策過程52一設(shè)備更新問題的決策過程53一設(shè)備更新問題的決策過程4.利潤函數(shù)：

1）使用了t年的設(shè)備，第i年決定更新，利潤函數(shù)如下

(6.4.1)2）第年決定保留繼續(xù)使用，則有利潤函數(shù)如下

(6.4.2)

54一設(shè)備更新問題的決策過程5.規(guī)劃函數(shù)：

1）(6.4.1)2）

(6.4.2)

55一設(shè)備更新問題的決策過程

56一設(shè)備更新問題的決策過程

57一設(shè)備更新問題的決策過程

58二設(shè)備更新算法的實現(xiàn)1.數(shù)據(jù)結(jié)構(gòu)：

int n; /*決策年限*/int D; /*設(shè)備當前的使用年限*/Typer[n][n+D]; /*使用t年后的設(shè)備,在第i年所創(chuàng)造的利潤*/Typem[n][n+D];/*使用t年后的設(shè)備,在第i年的維修費用*/Typeu[n][n+D]; /*使用t年后的設(shè)備,在第i年的更新費用*/Typef[n][n]; /*使用t年后的設(shè)備,在第i年及其以后所創(chuàng)造的利潤*/BOOLx[n][n]; /*使用t年后的設(shè)備,在第i年的更新決策*/BOOLp[n]; /*每年的最優(yōu)決策*/59二設(shè)備更新算法的實現(xiàn)2.算法描述：

2.Typeupdate_dev(intn,intD,Typer[][],Typem[][],Typeu[][],BOOLp[])3.{4.inti,j,k; /*分配工作空間*/5.Typeoptg,rem;6.Type(*f)[n+1]=newType[n+2][n+1];7.BOOL(*x)[n+1]=newBOOL[n+1][n+1];8.for(i=1;i<=n;i++) /*第n+1年的利潤初始化為0*/9.f[n+1][i]=0;60二設(shè)備更新算法的實現(xiàn)10.for(i=n;i>0;i--){ /*第1年~第n年各種設(shè)備使用年限的利潤*/11.for(j=1;j<=i;j++){12.if(i>j) /*買,可得到的利潤*/13.f[i][j]=r[i][0]–m[i][0]–u[i-j][j]+f[i+1][1];14.else 15.f[i][j]=r[i][0]–m[i][0]–u[0][j-1+D]+f[i+1][1];16.x[i][j]=TRUE; 17.if(i>j) /*留,可得到的利潤*/18.rem=r[i-j][j]–m[i-j][j]+f[i+1][j+1];19.else20.rem=r[0][j-1+D]–m[0][j-1+D]+f[i+1][j+1];21.if(f[i][j]<rem){ /*決策,取二者中只最大者*/22.f[i][j]=rem;x[i][j]=FALSE;23.}24.}25.}61二設(shè)備更新算法的實現(xiàn)26.j=1; /*全局的更新決策*/27.for(i=1;i<=n;i++){28.p[i]=x[i][j]; /*從第一年的決策開始*/29.if(p[i]) /*當年的決策：更新*/30.j=1 /*下一年決策時,設(shè)備年限為1年*/31.else 32.j=j+1; /*否則,下一年決策時,設(shè)備年限增1*/33.}34.optg=f[1][1];35.deletef;deletex; /*釋放工作空間*/36.returnoptg; /*返回最優(yōu)更新時可得到的利潤*/37.}626.5最長公共子序列問題

一最長公共子序列的搜索過程

二最長公共子序列算法的實現(xiàn)

63一最長公共子序列的搜索過程1.最長公共子序列問題

2.最長公共子序列的性質(zhì)

3.最長公共子序列的搜索過程641.最長公共子序列問題1）字符子序列：

上的字符序列，及,若對所有的k,k=1,2,,j，有，其中，1ikn，是

A的下標遞增序列，稱S是A的子序列。例：

={x,y,z}

，A=xyzyxzxzxxx是長度為3的子序列

xzyzx是長度為5的子序列例：A=xyzyxzxz，B=xzyxxyzxxxx 是長度為3的公共子序列

xzyz 是長度為4的公共子序列

xzyxxz 是長度為6的最長公共子序列

652）最長公共子序列問題給定序列和，尋找A和B的一個公共子序列，使得它是A和B的最長公共子序列

662.最長公共子序列的性質(zhì)令，記為序列A中最前面連續(xù)k個字符的子序列記為序列B中最前面連續(xù)k個字符的子序列1）若，是A和B的長度為k的最長公共子序列。則序列是A和B的長度為

k–1的最長公共子序列2）若,，則是和B的長度為k的最長公共子序列3）若,，則是A和的長度為k的最長公共子序列

673.最長公共子序列的搜索過程1）最長公共子序列長度的遞推關(guān)系式：記為和

的最長公共子序列長度，則aiai-1bjbj-1682）階段的劃分和最長公共子序列長度的獲取第一階段：計算和的最長公共子序列的長度第二階段：計算和的最長公共子序列的長度第n階段：計算和的最長公共子序列的長度第n階段的便是序列和的最長公共子序列的長度

693）最長公共子序列的獲?、僭O(shè)置二維狀態(tài)字數(shù)組

：70②

最長公共子序列的搜索設(shè)，是和的長度為k的最長公共子序列。搜索過程如下：

：下一個搜索方向是

：下一個搜索方向是

：下一個搜索方向是遞推關(guān)系：若則：，i=i–1,j=j–1,k=k–1

若則：i=i–1

若則：j=j–1714.例

1xzyzxyzxyzxy012345678910111200000000000000X10111313131113131113131113Y20121221232321232321232321X30111222223133333133333133Z40122122313232414343414343Y50122231323241424251535351X60112232324142425152526163Y70122231324251535261636271Z80122132414252616362717372Z90122132414252616262717272y100122231424251626271727281724.例

1xzyzxyzxyzxy012345678910111200000000000000X10111313131113131113131113Y20121221232321232321232321X30111222223133333133333133Z40122122313232414343414343