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

1、1第 6 章236.1 一般方法與求解步驟一般方法與求解步驟動(dòng)態(tài)規(guī)劃簡(jiǎn)介 動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。 20世紀(jì)50年代美國(guó)數(shù)學(xué)家貝爾曼（R.Bellman）等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)性原理，創(chuàng)立了解決多階段過(guò)程優(yōu)化問(wèn)題的新方法動(dòng)態(tài)規(guī)劃。 動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái)，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。46.1.11.幾個(gè)概念幾個(gè)概念 多階段決策問(wèn)題，是指這樣的一類特殊的活動(dòng)過(guò)程，問(wèn)題可以分解成若干相互聯(lián)系的階段，在每一個(gè)階段都要做出決策，形成一個(gè)決策序列，該決策序列也稱為一個(gè)策略。 對(duì)于每一個(gè)決策序列，可以在滿足問(wèn)

2、題的約束條件下用一個(gè)數(shù)值函數(shù)（即目標(biāo)函數(shù)）衡量該策略的優(yōu)劣。多階段決策問(wèn)題的最優(yōu)化求解目標(biāo)是獲取導(dǎo)致問(wèn)題最優(yōu)值的最優(yōu)決策序列（最優(yōu)策略），即得到最優(yōu)解。 52. 舉例說(shuō)明舉例說(shuō)明67 3. 最優(yōu)性原理最優(yōu)性原理 最優(yōu)性原理：“作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)，無(wú)論過(guò)去的狀態(tài)和決策如何,對(duì)前面的決策所形成的狀態(tài)而言,余下的諸決策必須構(gòu)成最優(yōu)策略”。 也就是說(shuō),最優(yōu)決策序列中的任何子序列都是最優(yōu)的。 最優(yōu)性原理體現(xiàn)為問(wèn)題的最優(yōu)子結(jié)構(gòu)特性。當(dāng)一個(gè)問(wèn)題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解時(shí)，則稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)特性。 最優(yōu)子結(jié)構(gòu)特性是動(dòng)態(tài)規(guī)劃求解問(wèn)題的必要條件。 8 例如，求得在數(shù)字串8473139

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

4、并確定初始（邊界）條件。（3） 應(yīng)用遞推求解最優(yōu)值。（4） 根據(jù)計(jì)算最優(yōu)值時(shí)所得到的信息，構(gòu)造最優(yōu)解。 構(gòu)造最優(yōu)解就是具體求出最優(yōu)決策序列。通常在計(jì)算最優(yōu)值時(shí)，根據(jù)問(wèn)題具體實(shí)際記錄更多的信息，根據(jù)所記錄的信息構(gòu)造出問(wèn)題的最優(yōu)解。 6.1.2 動(dòng)態(tài)規(guī)劃求解步驟動(dòng)態(tài)規(guī)劃求解步驟10 6.2 裝載問(wèn)題裝載問(wèn)題11(2） 動(dòng)態(tài)規(guī)劃設(shè)計(jì)1213 14【例6.3】 在一個(gè)由n個(gè)數(shù)字組成的數(shù)字串中插入r個(gè)乘號(hào)(1rn10)，將它分成r+1個(gè)整數(shù)，找出一種乘號(hào)的插入方法，使得這r+1個(gè)整數(shù)的乘積最大。例如，對(duì)給定的整數(shù)847313926，如何插入r=5個(gè)乘號(hào)，使其乘積最大? 如何插入r=4個(gè)乘號(hào)，使其乘積最大

5、?15例子給定一個(gè)數(shù)字串：847313926，插入r=5個(gè)乘號(hào)目標(biāo)：求最優(yōu)值目標(biāo)：求最優(yōu)值f(9,5)設(shè)前8個(gè)數(shù)字中已插入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ù)值的最大值即為個(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ù)字中已插入3個(gè)

6、乘號(hào)，則最大乘積為f(5,3)*392設(shè)前4個(gè)數(shù)字中已插入3個(gè)乘號(hào)，則最大乘積為f(4,3)*1392比較以上比較以上4個(gè)數(shù)值的最大值即為個(gè)數(shù)值的最大值即為f(8,4)為了求取f(i,k)，考察數(shù)字串的前i個(gè)數(shù)字，設(shè)前j(kji)個(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) (kji)前j個(gè)數(shù)字沒(méi)有插入乘號(hào)時(shí)的值顯然為前j個(gè)數(shù)字組成的整數(shù)，f(j,0)=a(1,j) (1ji)18for(d=0,j=1;j=n;j+) d=d*10+bj-1

7、-48; /* 把b數(shù)組的一個(gè)字符轉(zhuǎn)化為數(shù)值 */ a1j=d; fj0=a1j; /* f(j,0)賦初始值 */ for(k=1;k=r;k+) for(i=k+1;i=n;i+) for(amax=0,j=k;ji;j+) for(d=0,u=j+1;u=i;u+) d=d*10+bu-1-48; aj+1i=d; if(amaxfjk-1*aj+1i) /* 求f(j,k-1)*a(j+1,i)最大值 */ amax=fjk-1*aj+1i; fik=amax; /* 賦值給f(i,k) */ printf(“printf(“最優(yōu)值為最優(yōu)值為%ld”,fn,r);%ld”,fn,r);

8、 nn19省略數(shù)組a(i,j)與amax也,以上遞推可簡(jiǎn)化為：for(d=0,j=1;j=n;j+) d=d*10+bj-1-48; /* 把b數(shù)組的一個(gè)字符轉(zhuǎn)化為數(shù)值 */ fj0=d; /* 計(jì)算初始值fj0 */ for(k=1;k=r;k+) for(i=k+1;i=n;i+) for(j=k;ji;j+) for(d=0,u=j+1;u=i;u+) d=d*10+bu-1-48; /* 計(jì)算d即為a(j+1,i) */ if(fikm(i+1,cw), i=1,2,n-1則 xi=1; 裝載w(i). 其中cw=c開(kāi)始， cw=cw-x(i)*w(i).否則, x(i)=0,不裝載w

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

10、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個(gè)值得其個(gè)值得其中的最大值中的最大值lmaxlmax，即為所求的最長(zhǎng)非降子序列的長(zhǎng)度即最，即為所求的最長(zhǎng)非降子序列的長(zhǎng)度即最優(yōu)值優(yōu)值。 32(3） 構(gòu)造最優(yōu)解從序列的第1項(xiàng)開(kāi)始，依次輸出b(i)分別等于lmax,lmax-1,1的項(xiàng)a(i)，這就是所求的一個(gè)最長(zhǎng)非降子序列。(4） 算法復(fù)雜度分析以上動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為以上動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為O(n2)O

11、(n2)，空間復(fù)雜度為空間復(fù)雜度為O(n)O(n)。 336.5.2 最長(zhǎng)公共子序列34(1） 建立遞推關(guān)系35(2) 逆推計(jì)算最優(yōu)值根據(jù)以上遞推關(guān)系, 逆推計(jì)算最優(yōu)值c(0,0)流程為:for(i=0;i=m;i+) cin=0; /* 賦初始值 */ for(j=0;j=0;i-) /* 計(jì)算最優(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(最長(zhǎng)公共子串的長(zhǎng)度為：最長(zhǎng)公共子串的長(zhǎng)度為：%d,c00);%d,c00);

12、36(3) 構(gòu)造最優(yōu)解為構(gòu)造最優(yōu)解，設(shè)置數(shù)組s(i,j)： 當(dāng)x(i)=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開(kāi)始取值，當(dāng)確定最長(zhǎng)公共子序列一項(xiàng)時(shí)，t=j+1。若s(i,j)=1且c(i,j)=c(0,0)時(shí)，取x(i)為最長(zhǎng)公共子序列的第1項(xiàng);若s(i,j)=1且c(i,j)=c(0,0)-1時(shí)，取x(i)最長(zhǎng)公共子序列的第2項(xiàng);一般地，若s(i,j)=1且c(i,j)= c(0,0)-w時(shí)(w從0開(kāi)始，每確定最長(zhǎng)公共子序列的一項(xiàng)，w增1)，取x(i)最長(zhǎng)公共子序列的第w項(xiàng)。構(gòu)造

13、最長(zhǎng)公共子序列描述：構(gòu)造最長(zhǎng)公共子序列描述：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ù)值和即問(wèn)題的最優(yōu)值為所求的最大路徑數(shù)值和即問(wèn)題的最優(yōu)值為b(1,1)b(1,1)。 39(2) 逆推計(jì)算最優(yōu)值for(j=1;j=1;i-) /* 逆推得bij */for(j=1;jbi+1j) bij=aij+bi+1j+1; stmij=R; else

14、bij=aij+bi+1j; stmij=L;Printf(“%d”,b(1,1);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)=R 則打印 -R-;a(i,j+1);同時(shí)賦值j=j+1. 若 stm(i-1,j)=L 則打印 -L-;a(i,j);.依此打印出最大路徑，即所求的最優(yōu)解依此打印出最大路徑，即所求的最優(yōu)解. 416.6.2 邊數(shù)值矩形的最優(yōu)路徑搜索【例6.9】 已知n行m列的邊數(shù)值矩陣，

15、每一個(gè)點(diǎn)可向右或向下兩個(gè)去向，試求左上角頂點(diǎn)到右下角頂點(diǎn)的所經(jīng)邊數(shù)值和最小的路徑。例如給出一個(gè)例如給出一個(gè)4 4行行5 5列的邊數(shù)值矩形如下圖所示。列的邊數(shù)值矩形如下圖所示。 42(1(1） 建立遞推關(guān)系建立遞推關(guān)系 從點(diǎn)(i,j)水平向右的邊長(zhǎng)記為r(i,j)(jm)，點(diǎn)(i,j)向下的邊長(zhǎng)記為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-) /* 逆推求解a(i,j) */ for(j=m-1;j

16、=1;j-) if(ai+1j+dijaij+1+rij) aij=ai+1j+dij;stij=d; else aij=aij+1+rij;stij=r;所求左上角頂點(diǎn)到右下角頂點(diǎn)的最短路程即最優(yōu)值為所求左上角頂點(diǎn)到右下角頂點(diǎn)的最短路程即最優(yōu)值為a(1,1)a(1,1)。 44(3) 構(gòu)造最優(yōu)解利用路標(biāo)數(shù)組輸出最優(yōu)解，從點(diǎn)（1,1）即i=1,j=1開(kāi)始判斷： if(stij=d) printf(-%d-,dij);i+; else printf(-%d-,rij);j+;必要時(shí)可打印出點(diǎn)座標(biāo)。(4） 算法的復(fù)雜度分析以上動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為以上動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為O(mn)O(m

17、n)。 456.7 動(dòng)態(tài)規(guī)劃與其他算法的比較6.7.1 動(dòng)態(tài)規(guī)劃與遞推比較(1) 動(dòng)態(tài)規(guī)劃是用來(lái)求解多階段最優(yōu)化問(wèn)題的有效算法，而遞推一般是解決某些判定性問(wèn)題或計(jì)數(shù)問(wèn)題的方法，兩者求解對(duì)象有區(qū)別。(2) 動(dòng)態(tài)規(guī)劃求解的多階段決策問(wèn)題必須滿足最優(yōu)子結(jié)構(gòu)特性，而遞推所求解的計(jì)數(shù)問(wèn)題無(wú)需滿足最優(yōu)子結(jié)構(gòu)特性。(3) 動(dòng)態(tài)規(guī)劃在求得問(wèn)題的最優(yōu)值后通常需構(gòu)造出最優(yōu)值的最優(yōu)決策序列，即求出最優(yōu)解，而遞推在求出計(jì)數(shù)結(jié)果后沒(méi)有最優(yōu)解的構(gòu)造需求。(4) 從算法的時(shí)間復(fù)雜度而言，動(dòng)態(tài)規(guī)劃通常設(shè)置二維以上數(shù)組，其時(shí)間復(fù)雜度與二重循環(huán)以上的遞推時(shí)間復(fù)雜度基本相同，一般都在O(n2)以上。(5) 當(dāng)動(dòng)態(tài)規(guī)劃與遞推需設(shè)置三維數(shù)組時(shí)，其空間復(fù)雜度都比較高，限制了求解范圍。 466.7.2 動(dòng)態(tài)規(guī)劃與貪心算法比較(1) 動(dòng)態(tài)規(guī)劃算法求解最優(yōu)化問(wèn)題，通過(guò)建立每一階段狀態(tài)轉(zhuǎn)移之間的遞