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

算法設(shè)計與分析引子分治（遞歸）算法: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…動態(tài)規(guī)劃特征底層運算：“表格操作”實現(xiàn)路線：“子問題劃分、自底向上求解”基本原則：“空間換時間”矩陣連乘問題矩陣連乘計算次序可以用加括號的方式來確定。特別的，完全加括號的矩陣連乘積可遞歸地定義為：單個矩陣是完全加括號的矩陣連乘積A是完全加括號的，則A可示為2個完全加括號的矩陣連乘積B和C的乘積并加括號，即A=（BC）16000，10500，36000，87500，34500

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

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

問題分析

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

證明（反證法）：

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

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

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

1515

55

1010

2020

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

A1A2A3A4A5A6303535

1515

55

1010

2020

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

inti,j,len,k;

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

for(len=2;len<=matrixNum;len++){//計算長度為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ù)定義的一個充分大數(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];}算法的計算時間上界為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實例：計算矩陣連乘積A1A2A3A4A5A6，維數(shù)為：算法實現(xiàn)//自底向上地計算最優(yōu)值，結(jié)果保存在全局變量memoTable和bestK中l(wèi)ongMatrixChain(intmatrixNum){

inti,j,len,k;

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

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

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

return0;}

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

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

if(ans<max){

min=ans;}}

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

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

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

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

return0;}

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

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

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

returnmax;}動態(tài)規(guī)劃基本步驟分析最優(yōu)解的性質(zhì)，并刻劃其最優(yōu)子結(jié)構(gòu)特征；確定狀態(tài)表示S(x1,x2,…)和狀態(tài)遞推方程，遞歸地定義最優(yōu)值；確定狀態(tài)轉(zhuǎn)移順序，以自底向上的方式計算出最優(yōu)值；根據(jù)計算最優(yōu)值時得到的信息，構(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)為是一個子問題，子圖的源是固定的，匯是變化的。15

23486710

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

123456789101112

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

97324221711118654356425？最優(yōu)值求解子問題的數(shù)目等于圖G中頂點的個數(shù)。采用自底向上的方法求最優(yōu)值，最開始求解源s到第2段頂點集中每一個頂點的最短路徑。這是最簡單的子問題，最優(yōu)值就等于邊長。然后求解s到第3段頂點集中的每一個頂點的最優(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));//初始化為一個充分大的數(shù)x3f

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

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

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

for(p=0;p<numPerStage[i+1];p++){//遍歷第i+1段頂點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的公共子序列。枚舉算法的時間復(fù)雜度為指數(shù)級時間復(fù)雜度。最優(yōu)子結(jié)構(gòu)性質(zhì)狀態(tài)表示

狀態(tài)遞推方程

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

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

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

i=1:

i>1:

計算最優(yōu)值

例：

n=5，C=10，w={2，2，6，5，4}，v={6，3，5，4，6}i\p012345678910123450066666666600669999999006699991111140066999101113140066991212151515算法實現(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];}

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

算法改進(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)跳躍點定義

p

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

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

跳躍點計算示例例：n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。初始時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)}。從跳躍點集p[1]與q[1]的并集p[1]

q[1]={(0,0),(2,3),(2,6),(4,9)}中看到跳躍點(2,3)受控于跳躍點(2,6)。將受控跳躍點(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