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

1、常用算法與程序設(shè)計,1,第 6 章,動 態(tài) 規(guī) 劃,,常用算法與程序設(shè)計,2,主要內(nèi)容,,常用算法與程序設(shè)計,3,6.1 一般方法與求解步驟,動態(tài)規(guī)劃簡介 動態(tài)規(guī)劃是運籌學的一個分支，是求解決策過程最優(yōu)化的數(shù)學方法。 20世紀50年代美國數(shù)學家貝爾曼（R.Bellman）等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)性原理，創(chuàng)立了解決多階段過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。 動態(tài)規(guī)劃問世以來，在經(jīng)濟管

2、理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應用。,常用算法與程序設(shè)計,4,6.1.1 一般方法 1. 幾個概念 多階段決策問題，是指這樣的一類特殊的活動過程，問題可以分解成若干相互聯(lián)系的階段，在每一個階段都要做出決策，形成一個決策序列，該決策序列也稱為一個策略。 對于每一個決策序列，可以在滿足問題的約束條件下用一個數(shù)值函數(shù)（即目標函數(shù)）衡量該策略的優(yōu)劣。多階段決策問題的最優(yōu)

3、化求解目標是獲取導致問題最優(yōu)值的最優(yōu)決策序列（最優(yōu)策略），即得到最優(yōu)解。,常用算法與程序設(shè)計,5,2. 舉例說明,,常用算法與程序設(shè)計,6,,常用算法與程序設(shè)計,7,3. 最優(yōu)性原理 最優(yōu)性原理：“作為整個過程的最優(yōu)策略具有這樣的性質(zhì)，無論過去的狀態(tài)和決策如何,對前面的決策所形成的狀態(tài)而言,余下的諸決策必須構(gòu)成最優(yōu)策略”。 也就是說,最優(yōu)決策序列中的任何子序列都是最優(yōu)的。 最優(yōu)性原理體現(xiàn)為問題的最優(yōu)子結(jié)構(gòu)特性

4、。當一個問題的最優(yōu)解中包含了子問題的最優(yōu)解時，則稱該問題具有最優(yōu)子結(jié)構(gòu)特性。 最優(yōu)子結(jié)構(gòu)特性是動態(tài)規(guī)劃求解問題的必要條件。,常用算法與程序設(shè)計,8,例如，求得在數(shù)字串847313926中插入5個乘號，使乘積最大的最優(yōu)解為： 8*4*731*3*92*6=38737152 該最優(yōu)解包含了在84731中插入2個乘號使乘積最大為8*4*731；在7313中插入1個乘號使乘積最大為731*3；在3926中插入2個乘

5、號使乘積最大為3*92*6等子問題的最優(yōu)解，這就是最優(yōu)子結(jié)構(gòu)特性。 最優(yōu)性原理是動態(tài)規(guī)劃的基礎(chǔ)。任何一個問題，如果失去了這個最優(yōu)性原理的支持，就不可能用動態(tài)規(guī)劃設(shè)計求解。,4. 最優(yōu)子結(jié)構(gòu)特性,常用算法與程序設(shè)計,9,（1） 把所求最優(yōu)化問題分成若干個階段，找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特性。（2） 將問題發(fā)展到各個階段時所處不同的狀態(tài)表示出來，確定各個階段狀態(tài)之間的遞推關(guān)系，并確定初始（邊界）條件。（3） 應用遞推求解最

6、優(yōu)值。（4） 根據(jù)計算最優(yōu)值時所得到的信息，構(gòu)造最優(yōu)解。 構(gòu)造最優(yōu)解就是具體求出最優(yōu)決策序列。通常在計算最優(yōu)值時，根據(jù)問題具體實際記錄更多的信息，根據(jù)所記錄的信息構(gòu)造出問題的最優(yōu)解。,6.1.2 動態(tài)規(guī)劃求解步驟,常用算法與程序設(shè)計,10,,,6.2 裝載問題,常用算法與程序設(shè)計,11,(2） 動態(tài)規(guī)劃設(shè)計,常用算法與程序設(shè)計,12,(3) 遞推計算最優(yōu)值,for(j=0;j=1;i--) /* 逆推計算m(i,j)

7、 */for(j=0;j=w[i] && m[i+1][j]<m[i+1][j-w[i]]+w[i]) m[i][j]=m[i+1][j-w[i]]+w[i]; else m[i][j]=m[i+1][j];printf(“%d”,m[1][c1]);,,,,,常用算法與程序設(shè)計,13,(3） 構(gòu)造最優(yōu)解,構(gòu)造最優(yōu)解即給出所得最優(yōu)值時的裝載方案。if(m[i][cw]>

8、m[i+1][cw]) （其中cw為當前的裝載量，i=1,2,,n-1） 裝載w[i];else 不裝載w[i];if(所載集裝箱重量≠m(1,c1)) 裝載w[n].,,,,,常用算法與程序設(shè)計,14,6.3 插入乘號問題,【例6.3】 在一個由n個數(shù)字組成的數(shù)字串中插入r個乘號(1≤r<n<10)，將它分成r+1個整數(shù)，找出一種乘號的插入方法，使得這r+1個整數(shù)的乘積最大。例如，對給定的

9、整數(shù)847313926，如何插入r=5個乘號，使其乘積最大? 如何插入r=4個乘號，使其乘積最大?,,,常用算法與程序設(shè)計,15,(1) 算法設(shè)計 設(shè)f(i,k)表示在前i位數(shù)中插入k個乘號所得乘積的最大值，a(i,j)表示從第i個數(shù)字到第j個數(shù)字所組成的j-i+1(i≤j)位整數(shù)值。 一般地，為了求取f(i,k)，考察數(shù)字串的前i個數(shù)字，設(shè)前j（k≤j<i）個數(shù)字中已插入k-1個乘號的基礎(chǔ)上，在第j個數(shù)字后插

10、入第k個乘號，顯然此時的最大乘積為f(j,k-1)*a(j+1,i)。于是可以得遞推關(guān)系式: f(i,k)=max(f(j,k-1)*a(j+1,i)) （k≤j<i） 前j個數(shù)字沒有插入乘號時的值顯然為前j個數(shù)字組成的整數(shù)，因而得邊界值為： f(j,0)=a(1,j) (1<=j<=i),例子,給定一個數(shù)字串：847313926，插入r=5個乘號目標：求最優(yōu)值f(9,5)設(shè)前8個數(shù)字中已插

11、入4個乘號，則最大乘積為f(8,4)*6設(shè)前7個數(shù)字中已插入4個乘號，則最大乘積為f(7,4)*26設(shè)前6個數(shù)字中已插入4個乘號，則最大乘積為f(6,4)*926設(shè)前5個數(shù)字中已插入4個乘號，則最大乘積為f(5,4)*3926比較以上4個數(shù)值的最大值即為f(9,5)以此類推，為了求f(8,4):設(shè)前7個數(shù)字中已插入3個乘號，則最大乘積為f(7,3)*2設(shè)前6個數(shù)字中已插入3個乘號，則最大乘積為f(6,3)*92設(shè)前5個數(shù)

12、字中已插入3個乘號，則最大乘積為f(5,3)*392設(shè)前4個數(shù)字中已插入3個乘號，則最大乘積為f(4,3)*1392比較以上4個數(shù)值的最大值即為f(8,4),,為了求取f(i,k)，考察數(shù)字串的前i個數(shù)字，設(shè)前j(k≤j＜i)個數(shù)字中已插入k-1個乘號的基礎(chǔ)上，在第j個數(shù)字后插入第k個乘號，顯然此時的最大乘積為f(j,k-1)*a(j+1,i)?？梢缘玫竭f推關(guān)系式：f(i,k)=max(f(j,k-1)*a(j+1,i))

13、 (k≤j＜i)前j個數(shù)字沒有插入乘號時的值顯然為前j個數(shù)字組成的整數(shù)，f(j,0)=a(1,j) (1≤j＜i),常用算法與程序設(shè)計,18,(2) 遞推計算最優(yōu)值,for(d=0,j=1;j<=n;j++) {d=d*10+b[j-1]-48; /* 把b數(shù)組的一個字符轉(zhuǎn)化為數(shù)值 */ a[1][j]=d; f[j][0]=a[1][j]; /* f(j,0)賦初始

14、值 */ } for(k=1;k<=r;k++) for(i=k+1;i<=n;i++) {for(amax=0,j=k;j<i;j++) {for(d=0,u=j+1;u<=i;u++) d=d*10+b[u-1]-48; a[j+1][i]=d; if(amax<f[j][k-1]*a[j+1][i]) /* 求f(j,k-1)*a(j+1,i)最大值

15、*/ amax=f[j][k-1]*a[j+1][i]; } f[i][k]=amax; /* 賦值給f(i,k) */ }printf(“最優(yōu)值為%ld”,f[n,r]);,,,常用算法與程序設(shè)計,19,(3) 遞推計算最優(yōu)值的改進,省略數(shù)組a(i,j)與amax也,以上遞推可簡化為：for(d=0,j=1;j<=n;j++) {d

16、=d*10+b[j-1]-48; /* 把b數(shù)組的一個字符轉(zhuǎn)化為數(shù)值 */ f[j][0]=d; } /* 計算初始值f[j][0] */ for(k=1;k<=r;k++) for(i=k+1;i<=n;i++) for(j=k;j<i;j++) {for(d=0,u=j+1;u<=i;u++) d=d*10+b[u-1]-48; /*

17、 計算d即為a(j+1,i) */ if(f[i][k]<f[j][k-1]*d) /* 遞推求取f[i][k] */ f[i][k]=f[j][k-1]*d; }printf(“最優(yōu)值為%ld”,f[n,r]);,,,常用算法與程序設(shè)計,20,為了能打印相應的插入乘號的乘積式,設(shè)置標注位置的數(shù)組t(k)與c(i,k)，其中c(i,k)為相應的f(i,k)的第k個乘號的位置，而t(k)標

18、明第k個乘號“*”的位置，例如，t(2)=3,表明第2個“*”號在在第3個數(shù)字后面。當給數(shù)組元素賦值f(i,k)=f(j,k-1)*d時, 作相應賦值c(i,k)=j，表明f(i,k)的第k個乘號的位置是j。在求得f(n,r)的第r個乘號位置t(r)=c(n,r)=j的基礎(chǔ)上，其他t(k)( 1≤k≤r-1)可應用下式逆推產(chǎn)生 t(k)=c(t(k+1)，k)根據(jù)t數(shù)組的值, 可直接按字符形式打印出所求得的插入乘號的乘積

19、式.在整數(shù)637829156中插入4個乘號，使乘積最大： 63*7*82*915*6=198529380,(4) 構(gòu)造最優(yōu)解,常用算法與程序設(shè)計,21,,6.4.1 0-1背包問題,6.4 0-1背包問題求解,常用算法與程序設(shè)計,22,,2. 動態(tài)規(guī)劃逆推設(shè)計,常用算法與程序設(shè)計,23,,常用算法與程序設(shè)計,24,② 逆推計算最優(yōu)值for(j=0;j=w[n] ) m[n][j]=p[n]; /*

20、 首先計算m(n,j) */else m[n][j]=0;for(i=n-1;i>=1;i--) /* 逆推計算m(i,j) */for(j=0;j=w[i] && m[i+1][j]<m[i+1][j-w[i]]+p[i]) m[i][j]= m[i+1][j-w[i]]+p[i]; else m[i][j]=m[i+1][j];pri

21、ntf(“最優(yōu)值為%d”,m(1,c));,常用算法與程序設(shè)計,25,③ 構(gòu)造最優(yōu)解若m(i,cw)>m(i+1,cw), i=1,2,…,n-1則 x[i]=1; 裝載w(i). 其中cw=c開始， cw=cw-x(i)*w(i).否則, x(i)=0,不裝載w(i) 。 最后，所裝載的物品效益之和與最優(yōu)值比較，決定w(n)是否裝載。,常用算法與程序設(shè)

22、計,26,,3. 動態(tài)規(guī)劃順推設(shè)計,常用算法與程序設(shè)計,27,② 　順推計算最優(yōu)值 for(j=0;j=w[1] ) g[1][j]=p[1]; /* 首先計算g(1,j) */else g[1][j]=0;for(i=2;i=w[i] && g[i-1][j]<g[i-1][j-w[i]]+p[i]) g[i][j]= g[i-1][j-w[i]]+p[i];else g[i][j

23、]=g[i-1][j];printf(“最優(yōu)值為%d”,g(n,c));,常用算法與程序設(shè)計,28,③ 構(gòu)造最優(yōu)解若g(i,cw)>g(i-1,cw), i=n,n-1,…，2則 x[i]=1; 裝載w(i).　　　　　　其中cw=c開始，cw=cw-x(i)*w(i).否則, x(i)=0,不裝載w(i) 。最后，所裝載的物品效益之和與最優(yōu)值比較，決定w(1)是否裝載。,常用算法與程序設(shè)計,29,6.4.2

24、二維0-1背包問題,,本例在上例基礎(chǔ)上增加了容積的約束條件。,常用算法與程序設(shè)計,30,【例6.6】 給定一個由n個正整數(shù)組成的序列，從該序列中刪除若干個整數(shù)，使剩下的整數(shù)組成非降子序列，求最長的非降子序列。(1） 建立遞推關(guān)系　　設(shè)置b數(shù)組，b(i)表示序列的第i個數(shù)（保留第i個數(shù)）到第n個數(shù)中的最長非降子序列的長度，i=1,2,…,n。對所有的j>i，比較當 a(j)≥a(i)時的b(j)的最大值，顯然b(i)為這一最大

25、值加1，表示加上a(i)本身這一項?！　∫蚨羞f推關(guān)系： b(i)=max(b(j))+1 (a(j)≥a(i),1≤i<j≤n)　　邊界條件： b(n)=1,6.5 最長子序列探索,6.5.1 最長非降子序列,常用算法與程序設(shè)計,31,(2） 逆推計算最優(yōu)值,b[n]=1;for(i=n-1;i>=1;i--) {max=0;for(j=i+1;jmax) max=b[j];

26、 b[i]=max+1;　　　　 /* 逆推得b[i] */ } 　　逆推依次求得b(n-1),…,b(1)，比較這n-1個值得其中的最大值lmax，即為所求的最長非降子序列的長度即最優(yōu)值。,常用算法與程序設(shè)計,32,,(3） 構(gòu)造最優(yōu)解　　從序列的第1項開始，依次輸出b(i)分別等于lmax,lmax-1,…,1的項a(i)，這就是所求的一個最長非降子序列。(4） 算法復雜度分析　　以上動態(tài)規(guī)劃算法的時間

27、復雜度為O(n^2)，空間復雜度為O(n)。,常用算法與程序設(shè)計,33,6.5.2 最長公共子序列,常用算法與程序設(shè)計,34,(1） 建立遞推關(guān)系,常用算法與程序設(shè)計,35,(2) 逆推計算最優(yōu)值,根據(jù)以上遞推關(guān)系, 逆推計算最優(yōu)值c(0,0)流程為:for(i=0;i=0;i--) /* 計算最優(yōu)值 */ for(j=n-1;j>=0;j--) if(x[i]==y[j])

28、 c[i][j]=c[i+1][j+1]+1; else if(c[i][j+1]>c[i+1][j]) c[i][j]=c[i][j+1]; else c[i][j]=c[i+1][j]; printf("最長公共子串的長度為：%d",c[0][0]);,常用算法與程序設(shè)計,36,(3) 構(gòu)造最優(yōu)解,為構(gòu)造最優(yōu)解，設(shè)置數(shù)組s(i,j)： 當x(i)

29、=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

30、(i,j)= c(0,0)-w時(w從0開始，每確定最長公共子序列的一項，w增1)，取x(i)最長公共子序列的第w項。構(gòu)造最長公共子序列描述：for(t=0,w=0,i=0;i<=m-1;i++)for(j=t;j<=n-1;j++) if(s[i][j]==1 && c[i][j]==c[0][0]-w) {printf("%c",x[i]); w

31、++;t=j+1;break; },常用算法與程序設(shè)計,37,6.6 最優(yōu)路徑搜索,【例6.8】 隨機產(chǎn)生一個n行的點數(shù)值三角形(即三角形的每一個點都帶有一個正整數(shù)),尋找從頂點開始每一步可沿左斜（L）或右斜（R）向下至底的一條路徑,使該路徑所經(jīng)過的點的數(shù)值和最大。例如，n=6時給出的點數(shù)值三角形如下圖所示。,6.6.1 點數(shù)值三角形的最優(yōu)路徑搜索,7 22 11 22 9 285 14 23

32、 33 11 23 1 16 613 8 14 32 28 3,常用算法與程序設(shè)計,38,(1） 建立遞推關(guān)系,設(shè)數(shù)組b(i,j)為點(i,j)到底的最大數(shù)值和，字符數(shù)組stm(i,j)指明點(i,j)向左或向右的路標。b(i,j)與stm(i,j)(i=n-1,…,2,1)的值由b數(shù)組的第i+1行的第j個元素與第j+1個元素值的大小比較決定，即有遞推關(guān)系： b(i,j)=a(i,j)+b(i+1,

33、j+1);stm(i,j)="R" （b(i+1,j+1)>b(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。 所

34、求的最大路徑數(shù)值和即問題的最優(yōu)值為b(1,1)。,常用算法與程序設(shè)計,39,(2) 逆推計算最優(yōu)值,for(j=1;j=1;i--) /* 逆推得b[i][j] */for(j=1;jb[i+1][j]) { b[i][j]=a[i][j]+b[i+1][j+1]; stm[i][j]='R';} else { b[i][j]=a[i][j]+

35、b[i+1][j]; stm[i][j]='L';}Printf(“%d”,b(1,1));,常用算法與程序設(shè)計,40,(3) 構(gòu)造最優(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)=&

36、quot;R" 則打印 "-R-";a(i,j+1);同時賦值j=j+1. 若 stm(i-1,j)="L" 則打印 "-L-";a(i,j);.依此打印出最大路徑，即所求的最優(yōu)解.,常用算法與程序設(shè)計,41,6.6.2 邊數(shù)值矩形的最優(yōu)路徑搜索,【例6.9】 已知n行m列的邊數(shù)值矩陣，每一個點可向右或向下兩個去向，試求左上角頂點到右下角頂點的所經(jīng)邊數(shù)值

37、和最小的路徑。例如給出一個4行5列的邊數(shù)值矩形如下圖所示。,常用算法與程序設(shè)計,42,(1） 建立遞推關(guān)系,從點(i,j)水平向右的邊長記為r(i,j)(j<m)，點(i,j)向下的邊長記為d(i,j)(i<n)。設(shè)a(i,j)為點（i,j）到右下角頂點的最短路程。st(i,j)為點(i,j)路標數(shù)組:{‘d’,’r’}。a(i,j) 的值由a(i+1,j)+d(i,j)與a(i,j+1)+r(i,j)比較，取其較小者

38、得到，即有遞推關(guān)系：a(i,j)=min(a(i+1,j)+d(i,j),a(i,j+1)+r(i,j))st(i,j)={‘d’,’r’} 其中 i=1,2,…，n-1；j=1,2,…，m-1.,常用算法與程序設(shè)計,43,(2） 逆推計算最優(yōu)值,for(i=n-1;i>=1;i--) {a[i][m]=a[i+1][m]+d[i][m];st[i][m]='d';}

39、 /* 右邊縱列初始化 */ for(j=m-1;j>=1;j--) {a[n][j]=a[n][j+1]+r[n][j];st[n][j]='r';} /* 下邊橫行初始化 */ for(i=n-1;i>=1;i--) /* 逆推求解a(i,j) */ for(j=m

40、-1;j>=1;j--) if(a[i+1][j]+d[i][j]<a[i][j+1]+r[i][j]) {a[i][j]=a[i+1][j]+d[i][j];st[i][j]='d';} else {a[i][j]=a[i][j+1]+r[i][j];st[i][j]='r';}所求左上角頂點到右下角頂點的最短路程即最優(yōu)值為a(

41、1,1)。,常用算法與程序設(shè)計,44,(3) 構(gòu)造最優(yōu)解,利用路標數(shù)組輸出最優(yōu)解，從點（1,1）即i=1,j=1開始判斷： if(st[i][j]=='d') {printf("-%d-",d[i][j]);i++;} else {printf("-%d-",r[i][j]);j++;}必要時可打印出點座標。(4） 算法的復

42、雜度分析以上動態(tài)規(guī)劃算法的時間復雜度為O(mn)。,常用算法與程序設(shè)計,45,6.7 動態(tài)規(guī)劃與其他算法的比較,6.7.1 動態(tài)規(guī)劃與遞推比較(1) 動態(tài)規(guī)劃是用來求解多階段最優(yōu)化問題的有效算法，而遞推一般是解決某些判定性問題或計數(shù)問題的方法，兩者求解對象有區(qū)別。(2) 動態(tài)規(guī)劃求解的多階段決策問題必須滿足最優(yōu)子結(jié)構(gòu)特性，而遞推所求解的計數(shù)問題無需滿足最優(yōu)子結(jié)構(gòu)特性。(3) 動態(tài)規(guī)劃在求得問題的最優(yōu)值后通常需構(gòu)造出最

43、優(yōu)值的最優(yōu)決策序列，即求出最優(yōu)解，而遞推在求出計數(shù)結(jié)果后沒有最優(yōu)解的構(gòu)造需求。(4) 從算法的時間復雜度而言，動態(tài)規(guī)劃通常設(shè)置二維以上數(shù)組，其時間復雜度與二重循環(huán)以上的遞推時間復雜度基本相同，一般都在O(n^2)以上。(5) 當動態(tài)規(guī)劃與遞推需設(shè)置三維數(shù)組時，其空間復雜度都比較高，限制了求解范圍。,常用算法與程序設(shè)計,46,,6.7.2 動態(tài)規(guī)劃與貪心算法比較(1) 動態(tài)規(guī)劃算法求解最優(yōu)化問題，通過建立每一階段狀態(tài)轉(zhuǎn)移之

44、間的遞推關(guān)系，并經(jīng)過遞推來求取最優(yōu)值。貪心算法在求解最優(yōu)化問題時，從初始階段開始，每一個階段總是作一個使局部最優(yōu)的貪心選擇，最后求得最優(yōu)化問題的解。(2) 動態(tài)規(guī)劃算法是求解最優(yōu)化問題的常用算法，其結(jié)果總是最優(yōu)的。貪心算法在求解最優(yōu)化問題時，對大多數(shù)優(yōu)化問題能得到最優(yōu)解，但有時并不能求得最優(yōu)解。(3) 動態(tài)規(guī)劃存在一個空間的問題，其效率與求解范圍受到限制。從求解效率來說，貪心算法比動態(tài)規(guī)劃更高。,常用算法與程序設(shè)計,47,,上機