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

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

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

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

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

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

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

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

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

10、入第k個(gè)乘號(hào)，顯然此時(shí)的最大乘積為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個(gè)數(shù)字沒有插入乘號(hào)時(shí)的值顯然為前j個(gè)數(shù)字組成的整數(shù)，因而得邊界值為： f(j,0)=a(1,j) (1<=j<=i),例子,給定一個(gè)數(shù)字串：847313926，插入r=5個(gè)乘號(hào)目標(biāo)：求最優(yōu)值f(9,5)設(shè)前8個(gè)數(shù)字中已插

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

12、字中已插入3個(gè)乘號(hào)，則最大乘積為f(5,3)*392設(shè)前4個(gè)數(shù)字中已插入3個(gè)乘號(hào)，則最大乘積為f(4,3)*1392比較以上4個(gè)數(shù)值的最大值即為f(8,4),,為了求取f(i,k)，考察數(shù)字串的前i個(gè)數(shù)字，設(shè)前j(k≤j＜i)個(gè)數(shù)字中已插入k-1個(gè)乘號(hào)的基礎(chǔ)上，在第j個(gè)數(shù)字后插入第k個(gè)乘號(hào)，顯然此時(shí)的最大乘積為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個(gè)數(shù)字沒有插入乘號(hào)時(shí)的值顯然為前j個(gè)數(shù)字組成的整數(shù)，f(j,0)=a(1,j) (1≤j＜i),常用算法與程序設(shè)計(jì),18,(2) 遞推計(jì)算最優(yōu)值,for(d=0,j=1;j<=n;j++) {d=d*10+b[j-1]-48; /* 把b數(shù)組的一個(gè)字符轉(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è)計(jì),19,(3) 遞推計(jì)算最優(yōu)值的改進(jìn),省略數(shù)組a(i,j)與amax也,以上遞推可簡化為：for(d=0,j=1;j<=n;j++) {d

16、=d*10+b[j-1]-48; /* 把b數(shù)組的一個(gè)字符轉(zhuǎn)化為數(shù)值 */ f[j][0]=d; } /* 計(jì)算初始值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、 計(jì)算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è)計(jì),20,為了能打印相應(yīng)的插入乘號(hào)的乘積式,設(shè)置標(biāo)注位置的數(shù)組t(k)與c(i,k)，其中c(i,k)為相應(yīng)的f(i,k)的第k個(gè)乘號(hào)的位置，而t(k)標(biāo)

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

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

20、 首先計(jì)算m(n,j) */else m[n][j]=0;for(i=n-1;i>=1;i--) /* 逆推計(jì)算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è)計(jì),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、計(jì),26,,3. 動(dòng)態(tài)規(guī)劃順推設(shè)計(jì),常用算法與程序設(shè)計(jì),27,② 　順推計(jì)算最優(yōu)值 for(j=0;j=w[1] ) g[1][j]=p[1]; /* 首先計(jì)算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è)計(jì),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è)計(jì),29,6.4.2

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

25、值加1，表示加上a(i)本身這一項(xiàng)?！　∫蚨羞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è)計(jì),31,(2） 逆推計(jì)算最優(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個(gè)值得其中的最大值lmax，即為所求的最長非降子序列的長度即最優(yōu)值。,常用算法與程序設(shè)計(jì),32,,(3） 構(gòu)造最優(yōu)解　　從序列的第1項(xiàng)開始，依次輸出b(i)分別等于lmax,lmax-1,…,1的項(xiàng)a(i)，這就是所求的一個(gè)最長非降子序列。(4） 算法復(fù)雜度分析　　以上動(dòng)態(tài)規(guī)劃算法的時(shí)間

27、復(fù)雜度為O(n^2)，空間復(fù)雜度為O(n)。,常用算法與程序設(shè)計(jì),33,6.5.2 最長公共子序列,常用算法與程序設(shè)計(jì),34,(1） 建立遞推關(guān)系,常用算法與程序設(shè)計(jì),35,(2) 逆推計(jì)算最優(yōu)值,根據(jù)以上遞推關(guān)系, 逆推計(jì)算最優(yōu)值c(0,0)流程為:for(i=0;i=0;i--) /* 計(jì)算最優(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è)計(jì),36,(3) 構(gòu)造最優(yōu)解,為構(gòu)造最優(yōu)解，設(shè)置數(shù)組s(i,j)： 當(dāng)x(i)

29、=y(j)時(shí)s(i,j)=1；當(dāng)x(i)≠y(j)時(shí)s(i,j)=0。實(shí)施x(i)與 y(j)比較，其中i=0,1,…,m-1;j=t,1,…,n-1； 變量t從0開始取值，當(dāng)確定最長公共子序列一項(xiàng)時(shí)，t=j+1。若s(i,j)=1且c(i,j)=c(0,0)時(shí)，取x(i)為最長公共子序列的第1項(xiàng);若s(i,j)=1且c(i,j)=c(0,0)-1時(shí)，取x(i)最長公共子序列的第2項(xiàng);一般地，若s(i,j)=1且c

30、(i,j)= c(0,0)-w時(shí)(w從0開始，每確定最長公共子序列的一項(xiàng)，w增1)，取x(i)最長公共子序列的第w項(xiàng)。構(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è)計(jì),37,6.6 最優(yōu)路徑搜索,【例6.8】 隨機(jī)產(chǎn)生一個(gè)n行的點(diǎn)數(shù)值三角形(即三角形的每一個(gè)點(diǎn)都帶有一個(gè)正整數(shù)),尋找從頂點(diǎn)開始每一步可沿左斜（L）或右斜（R）向下至底的一條路徑,使該路徑所經(jīng)過的點(diǎn)的數(shù)值和最大。例如，n=6時(shí)給出的點(diǎn)數(shù)值三角形如下圖所示。,6.6.1 點(diǎn)數(shù)值三角形的最優(yōu)路徑搜索,7 22 11 22 9 285 14 23

32、 33 11 23 1 16 613 8 14 32 28 3,常用算法與程序設(shè)計(jì),38,(1） 建立遞推關(guān)系,設(shè)數(shù)組b(i,j)為點(diǎn)(i,j)到底的最大數(shù)值和，字符數(shù)組stm(i,j)指明點(diǎn)(i,j)向左或向右的路標(biāo)。b(i,j)與stm(i,j)(i=n-1,…,2,1)的值由b數(shù)組的第i+1行的第j個(gè)元素與第j+1個(gè)元素值的大小比較決定，即有遞推關(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è)計(jì),39,(2) 逆推計(jì)算最優(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è)計(jì),40,(3) 構(gòu)造最優(yōu)解,為了確定與并輸出最大路徑,利用stm數(shù)組從上而下查找:先打印a(1,1),若stm(1,1)="R "，則下一個(gè)打印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);同時(shí)賦值j=j+1. 若 stm(i-1,j)="L" 則打印 "-L-";a(i,j);.依此打印出最大路徑，即所求的最優(yōu)解.,常用算法與程序設(shè)計(jì),41,6.6.2 邊數(shù)值矩形的最優(yōu)路徑搜索,【例6.9】 已知n行m列的邊數(shù)值矩陣，每一個(gè)點(diǎn)可向右或向下兩個(gè)去向，試求左上角頂點(diǎn)到右下角頂點(diǎn)的所經(jīng)邊數(shù)值

37、和最小的路徑。例如給出一個(gè)4行5列的邊數(shù)值矩形如下圖所示。,常用算法與程序設(shè)計(jì),42,(1） 建立遞推關(guān)系,從點(diǎn)(i,j)水平向右的邊長記為r(i,j)(j<m)，點(diǎn)(i,j)向下的邊長記為d(i,j)(i<n)。設(shè)a(i,j)為點(diǎn)（i,j）到右下角頂點(diǎn)的最短路程。st(i,j)為點(diǎn)(i,j)路標(biāo)數(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è)計(jì),43,(2） 逆推計(jì)算最優(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';}所求左上角頂點(diǎn)到右下角頂點(diǎn)的最短路程即最優(yōu)值為a(

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

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

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

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