算法設(shè)計(jì)與分析：動(dòng)態(tài)規(guī)劃

算法設(shè)計(jì)與分析引子分治（遞歸）算法:intF(intn){if

n=0orn=1thenreturn1;

else

returnF(n-1)+F(n-2);}引子重復(fù)子問題??！引子算法復(fù)雜度是

O(n)longfibonacci(intn){long*fib=newlong[n+1];fib[0]=1;fib[1]=1;for(inti=2;i<=n;i++)fib[i]=fib[i-1]+fib[i-2];returnfib[n];}F(0)F(1)F(2)F(3)F(4)F(5)…fib112358…動(dòng)態(tài)規(guī)劃特征底層運(yùn)算：“表格操作”實(shí)現(xiàn)路線：“子問題劃分、自底向上求解”基本原則：“空間換時(shí)間”矩陣連乘問題矩陣連乘計(jì)算次序可以用加括號(hào)的方式來確定。特別的，完全加括號(hào)的矩陣連乘積可遞歸地定義為：單個(gè)矩陣是完全加括號(hào)的矩陣連乘積A是完全加括號(hào)的，則A可示為2個(gè)完全加括號(hào)的矩陣連乘積B和C的乘積并加括號(hào)，即A=（BC）16000，10500，36000，87500，34500

完全加括號(hào)問題分析窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。

1）自底向上：2）自頂向下：

問題分析

最優(yōu)子結(jié)構(gòu)性質(zhì)構(gòu)建原問題最優(yōu)解與子問題最優(yōu)解之間的關(guān)系

證明（反證法）：

狀態(tài)表示和遞推方程

K怎么確定?子問題個(gè)數(shù)和求解順序

自底向上的順序進(jìn)行求解，或者說從易至難的順序：先計(jì)算規(guī)模比較小或者說比較容易求解的子問題，并且把子問題的答案保存在狀態(tài)數(shù)組中，規(guī)模比較大的或者說比較困難的子問題的答案則由已求解子問題的答案構(gòu)造得到。計(jì)算最優(yōu)值示例A1A2A3A4A5A6303535

1515

55

1010

2020

25實(shí)例：計(jì)算矩陣連乘積A1A2A3A4A5A6，維數(shù)為：

A1A2A3A4A5A6303535

1515

55

1010

2020

25實(shí)例：計(jì)算矩陣連乘積A1A2A3A4A5A6，維數(shù)為：500035001000537525007501050071254375262515125118759375787515750060504030201654321i\j計(jì)算最優(yōu)值順序算法實(shí)現(xiàn)//自底向上地計(jì)算最優(yōu)值，結(jié)果保存在全局變量memoTable和bestK中l(wèi)ongMatrixChain(intmatrixNum){

inti,j,len,k;

for(i=1;i<=matrixNum;i++)//單個(gè)矩陣的情形，定義數(shù)乘次數(shù)為0memoTable[i][i]=0;

for(len=2;len<=matrixNum;len++){//計(jì)算長度為len的矩陣鏈最優(yōu)值

for(i=1;i<=matrixNum-len+1;i++){//矩陣鏈的開始矩陣下標(biāo)j=i+len-1;//矩陣鏈的結(jié)束矩陣下標(biāo)memoTable[i][j]=100000000;//預(yù)定義的一個(gè)充分大數(shù)

for(k=i;k<j;k++){//枚舉劃分位置

longans=memoTable[i][k]+memoTable[k+1][j]+dim[i-1]*dim[k]*dim[j];

if(ans<memoTable[i][j]){//更新最優(yōu)信息bestK[i][j]=k;memoTable[i][j]=ans;}}//endoffork}//endoffori}//endofforlen

returnmemoTable[1][matrixNum];}算法的計(jì)算時(shí)間上界為O(n3);算法所占用的空間顯然為O(n2)。構(gòu)造最優(yōu)解

5000K=53500K=51000K=45375K=32500K=3750K=310500K=37125K=34375K=32625K=215125K=311875K=39375K=37875K=115750K=1060504030201654321i\j最優(yōu)解為：(A1(A2A3))((A4A5)A6)A1A2A3A4A5A6303535

1515

55

1010

2020

25實(shí)例：計(jì)算矩陣連乘積A1A2A3A4A5A6，維數(shù)為：算法實(shí)現(xiàn)//自底向上地計(jì)算最優(yōu)值，結(jié)果保存在全局變量memoTable和bestK中l(wèi)ongMatrixChain(intmatrixNum){

inti,j,len,k;

for(i=1;i<=matrixNum;i++)//單個(gè)矩陣的情形，定義數(shù)乘次數(shù)為0memoTable[i][i]=0;

for(len=2;len<=matrixNum;len++){//計(jì)算長度為len的矩陣鏈最優(yōu)值

for(i=1;i<=matrixNum-len+1;i++){//矩陣鏈的開始矩陣下標(biāo)j=i+len-1;//矩陣鏈的結(jié)束矩陣下標(biāo)memoTable[i][j]=100000000;//預(yù)定義的一個(gè)充分大數(shù)

for(k=i;k<j;k++){//枚舉劃分位置

longans=memoTable[i][k]+memoTable[k+1][j]+dim[i-1]*dim[k]*dim[j];

if(ans<memoTable[i][j]){//更新最優(yōu)信息bestK[i][j]=k;memoTable[i][j]=ans;}}//endoffork}//endoffori}//endofforlen

returnmemoTable[1][matrixNum];}基本要素─最優(yōu)子結(jié)構(gòu)注意：同一個(gè)問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)，通俗地講就是問題的最優(yōu)解包含其子問題的最優(yōu)解。也就是說，如果把問題的最優(yōu)解分解（比如劃分為兩個(gè)或者多個(gè)部分，或者刪除第一個(gè)或者最后一個(gè)分量），得到一個(gè)子解，那么這個(gè)子解是其相應(yīng)子問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)性質(zhì)隱含了問題最優(yōu)解和子問題最優(yōu)解之間的一種遞推關(guān)系。它是動(dòng)態(tài)規(guī)劃的基礎(chǔ)，遞推方程是最優(yōu)子結(jié)構(gòu)性質(zhì)的體現(xiàn)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，人們一般采用反證法：首先假設(shè)由問題最優(yōu)解S導(dǎo)出的子問題的解不是最優(yōu)的，然后再推導(dǎo)在這個(gè)假設(shè)下可構(gòu)造出比S更好的解S’，從而得到矛盾。基本要素─重疊子問題遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對每一個(gè)子問題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問題時(shí)，只是簡單地用常數(shù)時(shí)間查看一下結(jié)果。通常不同的子問題個(gè)數(shù)隨問題的大小呈多項(xiàng)式增長。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。遞歸方法longMatrixChain(inti,intj){

if(i==j){//單個(gè)矩陣的情形memoTable[i][j]=0;

return0;}

longans,min=100000000;//預(yù)定義的一個(gè)充分大數(shù)

for(intk=i;k<j;k++){ans=MatrixChain(i,k)+MatrixChain(k+1,j)+dim[i-1]*dim[k]*dim[j];//遞歸計(jì)算

if(ans<max){

min=ans;}}

returnmin;}指數(shù)級(jí)別時(shí)間復(fù)雜度！備忘錄方法備忘錄方法用表格保存已解決的子問題的答案，在下次需要解決此問題時(shí)，只要從表格中提取答案即可，而不需要重新計(jì)算；如果沒有求解，則遞歸調(diào)用求解過程進(jìn)行計(jì)算。備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，自頂向下的處理，程序簡單；區(qū)別在于備忘錄方法為每個(gè)求解過的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。備忘錄方法//調(diào)用前用memset(memoTable,-1,sizeof(memoTable))初始化備忘錄表為-1longMatrixChainMemo(inti,intj){

if(memoTable[i][j]!=-1)

returnmemoTable[i][j];//備忘錄表中有答案

if(i==j){//單個(gè)矩陣的情形memoTable[i][j]=0;

return0;}

longans,max=100000000;//預(yù)定義的一個(gè)充分大數(shù)

for(intk=i;k<j;k++){ans=MatrixChainMemo(i,k)+MatrixChainMemo(k+1,j)+dim[i-1]*dim[k]*dim[j];//遞歸計(jì)算

if(ans<max){bestK[i][j]=k;max=ans;}}memoTable[i][j]=max;

returnmax;}動(dòng)態(tài)規(guī)劃基本步驟分析最優(yōu)解的性質(zhì)，并刻劃其最優(yōu)子結(jié)構(gòu)特征；確定狀態(tài)表示S(x1,x2,…)和狀態(tài)遞推方程，遞歸地定義最優(yōu)值；確定狀態(tài)轉(zhuǎn)移順序，以自底向上的方式計(jì)算出最優(yōu)值；根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。多段圖最短路徑123456789101112

97324221711118654356425最優(yōu)子結(jié)構(gòu)性質(zhì)

證明（反證法）：

最優(yōu)子結(jié)構(gòu)性質(zhì)

1234567810

12

9732422171111896543511642512710129232狀態(tài)表示包含源s的子圖都可以認(rèn)為是一個(gè)子問題，子圖的源是固定的，匯是變化的。15

23486710

91112原/子問題狀態(tài)表示包含源s的子圖對應(yīng)一個(gè)子問題，子圖的源是固定的，匯是變化的。因此，確定了匯的位置，則能確定一個(gè)子圖。匯的位置包括兩個(gè)參數(shù)：段的序號(hào)和該段頂點(diǎn)集合中匯頂點(diǎn)的序號(hào)。

123456789101112

97324221711118654356425狀態(tài)遞推方程151416123456789101112

97324221711118654356425？最優(yōu)值求解子問題的數(shù)目等于圖G中頂點(diǎn)的個(gè)數(shù)。采用自底向上的方法求最優(yōu)值，最開始求解源s到第2段頂點(diǎn)集中每一個(gè)頂點(diǎn)的最短路徑。這是最簡單的子問題，最優(yōu)值就等于邊長。然后求解s到第3段頂點(diǎn)集中的每一個(gè)頂點(diǎn)的最優(yōu)值，依此循環(huán)，直至求解s到t的最短路徑值。151416123456789101112

9732422171111865435642516237991110#include<math.h>#include<stdio.h>#include<memory.h>#defineMaxStage100intminRoad[MaxStage][MaxStage];intMultiStageGraph(int,int*);intmain(){

intni[MaxStage],k,i;

while(scanf("%d",&k),k!=-1){

for(i=0;i<k;i++)scanf("%d",&ni[i]);printf("%d\n",MultiStageGraph(k,ni));}

return0;}int

MultiStageGraph(intstageNum,int*numPerStage){

inti,q,p,weight,temp;memset(minRoad,0x3f,sizeof(minRoad));//初始化為一個(gè)充分大的數(shù)x3f

for(p=0;p<numPerStage[0];p++)//初始化源頂點(diǎn)層minRoad[0][p]=0;

for(i=0;i<stageNum-1;i++)//按段計(jì)算，終止于匯頂點(diǎn)的前一段

for(q=0;q<numPerStage[i];q++)//遍歷第i段頂點(diǎn)

for(p=0;p<numPerStage[i+1];p++){//遍歷第i+1段頂點(diǎn)scanf("%d",&weight);//讀取邊(q,p)的權(quán)重w(q,p)

if(weight!=-1){//存在邊(q,p)temp=minRoad[i][q]+weight;

if(temp<minRoad[i+1][p])//發(fā)現(xiàn)s到p的更短路徑minRoad[i+1][p]=temp;}}//endfor(p

returnminRoad[stageNum-1][0];}最長公共子序列列舉X的所有子序列，然后檢查它是否也是Y的子序列，從而確定它是否是X和Y的公共子序列。枚舉算法的時(shí)間復(fù)雜度為指數(shù)級(jí)時(shí)間復(fù)雜度。最優(yōu)子結(jié)構(gòu)性質(zhì)狀態(tài)表示

狀態(tài)遞推方程

計(jì)算最優(yōu)值

怎么獲取最長公共子序列？

對b遞歸推導(dǎo)得解：BCBA例：X=ABCBDAB，Y=BDCABA為便于觀察，將b=1標(biāo)為斜箭頭，2標(biāo)為上箭頭，3標(biāo)為左箭頭i\j01(B)2(D)3(C)4(A)5(B)6(A)000000001(A)02(B)03(C)04(B)05(D)06(A)07(B)00↑0↑0↑1↖1←1↖1↖1←1←1↑2↖2←1↑1↑2↖2←2↑2↑1↖1↑2↑2↑3↖3←1↑2↖2↑2↑3↑3↑1↑2↑2↑3↖3↑4↖1↖2↑2↑3↑4↖4↑ABCB#defineMAX1000001intlcsLength(char*strX,char*strY){

intC[MAX][MAX],B[MAX][MAX],i,j;

intm=strlen(strX)+1;

intn=strlen(strY)+1;

for(i=0;i<m;i++)C[i][0]=0;//初始化第一行

for(j=0;j<n;j++)C[0][j]=0;//初始化第一列

for(i=1;i<m;i++){

for(j=1;j<n;j++){

if(strX[i-1]==strY[j-1]){C[i][j]=C[i-1][j-1]+1;B[i][j]=1;}else

if(C[i-1][j]>=C[i][j-1]){C[i][j]=C[i-1][j];B[i][j]=2;}else{C[i][j]=C[i][j-1];B[i][j]=3;}}//endfor(j}//endfor(i

returnC[m-1][n-1];}lcsLength的時(shí)間復(fù)雜性為O(nm)，空間復(fù)雜性也為O(nm)，需要兩個(gè)二維數(shù)組來存儲(chǔ)最優(yōu)值和最優(yōu)方案改進(jìn)方案一：在C[i-1][j-1]中存儲(chǔ)B[i][j]的值，省略B的存儲(chǔ)空間改進(jìn)方案二：如果只需要求最長公共子序列的長度，則存儲(chǔ)空間可以縮小到2n0-1背包問題最優(yōu)子結(jié)構(gòu)性質(zhì)

狀態(tài)表示和遞推方程

狀態(tài)表示和遞推方程

i=1:

i>1:

計(jì)算最優(yōu)值

例：

n=5，C=10，w={2，2，6，5，4}，v={6，3，5，4，6}i\p012345678910123450066666666600669999999006699991111140066999101113140066991212151515算法實(shí)現(xiàn)double

binaryKnapsack(intnumItems,int*w,double*v,intcapacity){

int

i,j;

doubleVal[MaxN][MaxC];

memset(Val,0,sizeof(Val));

for(i=1;i<numItems;i++)

for(j=0;j<=capacity;j++){Val[i][j]=Val[i-1][j];

if(j>=w[i]&&Val[i-1][j]<Val[i-1][j-w[i]]+v[i])

Val[i][j]=Val[i][j-w[i]]+v[i];}

returnVal[numItems-1][capacity];}

實(shí)現(xiàn)代碼兩個(gè)缺點(diǎn)：算法要求所給物品的重量是整數(shù)當(dāng)背包容量C很大時(shí)，算法需要的時(shí)間和空間都比較大

算法改進(jìn)例：

n=5，C=10，w={2，2，6，5，4}，

v={6，3，5，4，6}i\p012345678910123450066666666600669999999006699991111140066999101113140066991212151515pVal(1,p)pVal(2,p)pVal(5,p)跳躍點(diǎn)定義

p

跳躍點(diǎn)示例例：n=3，c=6，w={4，3，2}，v={5，2，1}。

pVal(0,p)pVal(1,p)pVal(2,p)pVal(3,p)跳躍點(diǎn)的遞歸求解

跳躍點(diǎn)計(jì)算示例例：n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。初始時(shí)p[0]={(0,0)}，(w1,v1)=(2,6)。因此，q[0]=p[0]

(w1,v1)={(2,6)}。p[1]={(0,0);(2,6)}。q[1]=p[1]

(w2,v2)={(2,3),(4,9)}。從跳躍點(diǎn)集p[1]與q[1]的并集p[1]

q[1]={(0,0),(2,3),(2,6),(4,9)}中看到跳躍點(diǎn)(2,3)受控于跳躍點(diǎn)(2,6)。將受控跳躍點(diǎn)(2,6)清除后，得到p[2]={(0,0),(2,6),(4,9)}q[2]=p[2]

(6,5)={(6,5);(8,11);(10,14)}p[3]={(0,0);(2,6);(4,9);(8,11);(10,14)}q[3]=p[3]

(5,4)={(5,

4);(7,10);(9,13)}p[4