第3講 動態(tài)規(guī)劃

1、1233.1 一般方法與求解步驟一般方法與求解步驟43.1.11.幾個概念幾個概念52. 舉例說明舉例說明67 3. 最優(yōu)性原理最優(yōu)性原理 8 4. 最優(yōu)子結構特性最優(yōu)子結構特性9 3.1.2 動態(tài)規(guī)劃求解步驟動態(tài)規(guī)劃求解步驟10 3.2 裝載問題裝載問題11(2） 動態(tài)規(guī)劃設計1213 141516 nn17 18(4) 構造最優(yōu)解構造最優(yōu)解19 3.4.1 0-1背包問題背包問題 3.4 0-1背包問題求解背包問題求解20 2. 動態(tài)規(guī)劃逆推設計動態(tài)規(guī)劃逆推設計2122 23若m(i,cw)m(i+1,cw), i=1,2,n-1則 xi=1; 裝載w(i). 其中cw=c開始， cw=c

2、w-x(i)*w(i).否則, x(i)=0,不裝載w(i) 。 最后，所裝載的物品效益之和與最優(yōu)值比較，最后，所裝載的物品效益之和與最優(yōu)值比較，決定決定w(n)是否裝載是否裝載。 24 3. 動態(tài)規(guī)劃順推設計動態(tài)規(guī)劃順推設計25 順推計算最優(yōu)值順推計算最優(yōu)值 for(j=0;j=w1 ) g1j=p1; /* 首先計算g(1,j) */else g1j=0;for(i=2;i=n;i+) /* 順推計算g(i,j) */for(j=0;j=wi & gi-1ji，比較當 a(j)a(i)時的b(j)的最大值，顯然b(i)為這一最大值加1，表示加上a(i)本身這一項。因而有遞推關系：

3、b(i)=max(b(j)+1 (a(j)a(i),1i=1;i-) max=0;for(j=i+1;j=n;j+) if(aimax) max=bj; bi=max+1; /* 逆推得bi */ 逆推依次求得逆推依次求得b(n-1),b(1)b(n-1),b(1)，比較這，比較這n-1n-1個值得其個值得其中的最大值中的最大值lmaxlmax，即為所求的最長非降子序列的長度即最，即為所求的最長非降子序列的長度即最優(yōu)值優(yōu)值。 30(3） 構造最優(yōu)解從序列的第1項開始，依次輸出b(i)分別等于lmax,lmax-1,1的項a(i)，這就是所求的一個最長非降子序列。(4） 算法復雜度分析以上動態(tài)規(guī)

4、劃算法的時間復雜度為以上動態(tài)規(guī)劃算法的時間復雜度為O(n2)O(n2)，空間復雜度為空間復雜度為O(nO(n) )。 313.5.2 最長公共子序列32(1） 建立遞推關系33(2) 逆推計算最優(yōu)值根據(jù)以上遞推關系, 逆推計算最優(yōu)值c(0,0)流程為:for(i=0;i=m;i+) cin=0; /* 賦初始值 */ for(j=0;j=0;i-) /* 計算最優(yōu)值 */ for(j=n-1;j=0;j-) if(xi=yj) cij=ci+1j+1+1; else if(cij+1ci+1j) cij=cij+1; else cij=ci+1j; printf printf(最長公共子串的長

5、度為：最長公共子串的長度為：%d,c00);%d,c00); 34(3) 構造最優(yōu)解為構造最優(yōu)解，設置數(shù)組s(i,j)： 當x(i)=y(j)時s(i,j)=1；當x(i)y(j)時s(i,j)=0。實施x(i)與 y(j)比較，其中i=0,1,m-1;j=t,1,n-1； 變量t從0開始取值，當確定最長公共子序列一項時，t=j+1。若s(i,j)=1且c(i,j)=c(0,0)時，取x(i)為最長公共子序列的第1項;若s(i,j)=1且c(i,j)=c(0,0)-1時，取x(i)最長公共子序列的第2項;一般地，若s(i,j)=1且c(i,j)= c(0,0)-w時(w從0開始，每確定最長公共

6、子序列的一項，w增1)，取x(i)最長公共子序列的第w項。構造最長公共子序列描述：構造最長公共子序列描述：for(t=0,w=0,i=0;i=m-1;i+)for(j=t;jb(i+1,j)） b(i,j)=a(i,j)+b(i+1,j);stm(i,j)=L （b(i+1,j+1)b(i+1,j)） 其中i=n-1,2,1 邊界條件：b(n,j)=a(n,j), j=1,2,n。 所求的最大路徑數(shù)值和即問題的最優(yōu)值為所求的最大路徑數(shù)值和即問題的最優(yōu)值為b(1,1)b(1,1)。 37(2) 逆推計算最優(yōu)值for(j=1;j=1;i-) /* 逆推得bij */for(j=1;jbi+1j)

7、bij=aij+bi+1j+1; stmij=R; else bij=aij+bi+1j; stmij=L;Printf(“%d”,b(1,1);38(3) 構造最優(yōu)解為了確定與并輸出最大路徑,利用stm數(shù)組從上而下查找:先打印a(1,1),若stm(1,1)= R ，則下一個打印a(2,2),否則打印a(2,1)。一般地,在輸出i循環(huán)（i=2,3,n）中： 若 stm(i-1,j)=R 則打印 -R-;a(i,j+1);同時賦值j=j+1. 若 stm(i-1,j)=L 則打印 -L-;a(i,j);.依此打印出最大路徑，即所求的最優(yōu)解依此打印出最大路徑，即所求的最優(yōu)解. 393.6.2 邊

8、數(shù)值矩形的最優(yōu)路徑搜索【例3.9】 已知n行m列的邊數(shù)值矩陣，每一個點可向右或向下兩個去向，試求左上角頂點到右下角頂點的所經(jīng)邊數(shù)值和最小的路徑。例如給出一個例如給出一個4 4行行5 5列的邊數(shù)值矩形如下圖所示。列的邊數(shù)值矩形如下圖所示。 40(1(1） 建立遞推關系建立遞推關系 從點(i,j)水平向右的邊長記為r(i,j)(jm)，點(i,j)向下的邊長記為d(i,j)(i=1;i-) aim=ai+1m+dim;stim=d; /* 右邊縱列初始化 */ for(j=m-1;j=1;j-) anj=anj+1+rnj;stnj=r; /* 下邊橫行初始化 */ for(i=n-1;i=1;i

9、-) /* 逆推求解a(i,j) */ for(j=m-1;j=1;j-) if(ai+1j+dijaij+1+rij) aij=ai+1j+dij;stij=d; else aij=aij+1+rij;stij=r;所求左上角頂點到右下角頂點的最短路程即最優(yōu)值為所求左上角頂點到右下角頂點的最短路程即最優(yōu)值為a(1,1)a(1,1)。 42(3) 構造最優(yōu)解利用路標數(shù)組輸出最優(yōu)解，從點（1,1）即i=1,j=1開始判斷： if(stij=d) printf(-%d-,dij);i+; else printf(-%d-,rij);j+;必要時可打印出點座標。(4） 算法的復雜度分析以上動態(tài)規(guī)劃算

10、法的時間復雜度為以上動態(tài)規(guī)劃算法的時間復雜度為O(mnO(mn) )。 433.7 動態(tài)規(guī)劃與其他算法的比較3.7.1 動態(tài)規(guī)劃與遞推比較(1) 動態(tài)規(guī)劃是用來求解多階段最優(yōu)化問題的有效算法，而遞推一般是解決某些判定性問題或計數(shù)問題的方法，兩者求解對象有區(qū)別。(2) 動態(tài)規(guī)劃求解的多階段決策問題必須滿足最優(yōu)子結構特性，而遞推所求解的計數(shù)問題無需滿足最優(yōu)子結構特性。(3) 動態(tài)規(guī)劃在求得問題的最優(yōu)值后通常需構造出最優(yōu)值的最優(yōu)決策序列，即求出最優(yōu)解，而遞推在求出計數(shù)結果后沒有最優(yōu)解的構造需求。(4) 從算法的時間復雜度而言，動態(tài)規(guī)劃通常設置二維以上數(shù)組，其時間復雜度與二重循環(huán)以上的遞推時間復雜度基本相同，一般都在O(n2)以上。(5) 當動態(tài)規(guī)劃與遞推需設置三維數(shù)組時，其空間復雜度都比較高，限制了求解范圍。 443.7.2 動態(tài)規(guī)劃與貪心算法比較(1) 動態(tài)規(guī)劃算法求解最優(yōu)化問題，通過建立每一階段狀態(tài)轉移之間的遞推關系，并經(jīng)過遞推來求取最優(yōu)值。貪心算法在求解最優(yōu)化問題時，從初始階段開始，每一個階段總是作一個使局部最優(yōu)的貪心選擇，最后求得最優(yōu)化問題的解。(2) 動態(tài)規(guī)劃算法是求解最優(yōu)化問題的常用算法，其結果總是最優(yōu)的