1、第11章 動態(tài)規(guī)劃2011-12-136A-01712圖1DAGCKBNPOMJFHELI312345214323142212223344階段1階段2階段3階段4階段5任務(wù)：P是出發(fā)點，從P到A，求最短路徑（圖1）3思路先看第5階段，到達A點有兩條路B A，需要2kmC A，需要3km B 2 A P(A) 令 P(B) 3從P A的最短路徑為P(A)； C從P B的最短路徑為P(B)； P(C)從P C的最短路徑為P(C) 5階段P(A) = minP(B)+2, P(C)+3；P(B) = minP(D)+1, P(E)+2；P(C) = minP(E)+5, P(F)+4；4P(A) =

2、 minP(B)+2, P(C)+3；P(B) = minP(D)+1, P(E)+2；P(C) = minP(E)+5, P(F)+4； P(D) D 1 B 2 A 2 3 5 P(B) E C 4 P(C) P(E) F P(F)5P(N) = 2;P(O) = 3;上述遞推公式告訴我們，要求P(A)需要先求出階段5中的P(B)和P(C)；要求 P(B) (或者P(C)），又要先求出階段4中的 P(D) 和 P(E) (或P(F)和P(E)顯然，要依照上述遞推過程求解，需要倒過來，從P(P)出發(fā)，先求出第一階段的P(O)和P(N)，再求第二階段的P(K)，P(L)，P(M)；，最后得到P

3、(A)。6選擇數(shù)據(jù)結(jié)構(gòu)，將每條路經(jīng)的長度存在數(shù)組中。東西方向上的道路長度存在兩維數(shù)組h43中規(guī)定數(shù)組的第一維為行號，第二維為列號。312345214323h43 = 3,2,3, 2,1,4, 3,4,5, 3,1,2 ;01210237南北方向上道路長度存至數(shù)組v34中，也規(guī)定第一維為行號，第二維為列號。0123210223441241223v34 = 2, 2, 3, 4,4, 1, 2, 4,1, 2, 2, 3;8為了計算方便，使地圖更好地與二維數(shù)組對應(yīng)，下面將圖1改為圖2h30h31h32h20h21h22h10h11h12h00h01h02v20v21v22v23v10v11v12

4、v13v00v01v02v03(3, 3)0213213yx圖29求解過程為從(0, 0)到(3, 3)求最短路徑問題定義二維數(shù)組，P44=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,第一維為行，第二維為列。這時：P(O)為P01；P(N)為P10；P(A)為P33，以下為分階段遞推求解過程。對于階段1:P00 = 0;P01 = P00+h00 = 0+3 = 3;P10 = P00+v00 = 0+2 = 2;10 p30 p31 p32 p33 h30 h31 h32 v20 v21 v22 v23 p20 p21 p22 p23 h20 h21 h22 階段 5 v

5、10 v11 v12 v13 p10 p11 p12 p13 h10 h11 h12 階段 4 v00 v01 v02 v03 p00 p01 p02 p03 h00 h01 h02 階段 3 階段 1 階段 211對于階段2P11 = min P01+v01, P10+h10 = min3+1, 2+2 = 4P02 = P01+h10 = 3+2 = 5P20 = P10+v10 = 2+4 = 6對于階段3P12 = min P02+v02, P11+h11 = min5+3, 4+1 = 5P03 = P02+h02 = 5+3 = 8P21 = min P11+v11, P20+h2

6、0 = min4+1, 6+1 = 5P30 = P20+v20 = 6+1 = 712對于階段4P13 = min P03+v03, P12+h12 = min8+4, 5+4 = 9P22 = min P12+v12, P21+h21 = min5+2, 5+4 = 7P31 = min P21+v21, P30+h30 = min5+2, 7+3 = 7對于階段5P23 = min P13+v13, P22+h22 = min9+4, 7+5 = 12P32 = min P22+v22, P31+h31 = min7+2, 7+1 = 813最后P33 = min P23+v23, P3

7、2+h32 = min12+3, 8+2 = 10 綜上，數(shù)組P的通項表示為 Pij= min( (pi-1j+vi-1j), (pij-1+hij-1) ) (i, j0)P0j=P0j-1+h0j-1 (i=0, j0)Pi0=Pi-10+vi-10 (i0, j=0)下面給出P數(shù)組中的數(shù)據(jù)0123210035824596571277810314數(shù)組P的通項表示為Pij= min( (pi-1j+vi-1j), (pij-1+hij-1) ) (i, j0)P0j=P0j-1+h0j-1( i=0, j0)Pi0=Pi-10+vi-10( i0, j=0)15畫出用動態(tài)規(guī)劃思想求出的各個路

8、口對P點的最小距離。圖中圓圈里就是這個距離。箭頭表示所尋得的最佳行走路徑。（圖3）312345214323142212223344026734575578891210P點A點圖316參考程序如下17 #include using namespace std; int min(int,int); / 聲明有子函數(shù) min() int main() / 主函數(shù) int h43= 3,2,3,2,1,4,3,4,5,3,1,2 ;/東西路段 int v34= 2,2,3,4,4,1,2,4,1,2,2,3 ; /南北路段 int p44= 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

9、0 ; p00=0; / ? int p44 = 0; /初始化 for(int j=1;j4;j+) /y軸上的點 p0j=p0j-1+h0j-1; for(int i=1;i4;i+)/x軸上的點 pi0=pi-10+vi-10; 18 for(int i=1;i4;i+)/內(nèi)部的點 for(int j=1;j4;j+) pij=min( ( pi-1j+vi-1j), (pij-1+hij-1) ); / min() : next pagecout“from P to A is ”p33=0;i-) i for(int j=0;j=3;j+) coutpij ; 3 coutendl;

10、2 1return 0; 0 1 2 3 j 19int min(int a,int b) if (a=b ) return a; else return b;/ 兩整數(shù)比大小，返回小者20動態(tài)規(guī)劃的基本概念:階段：據(jù)空間順序或時間順序?qū)栴}的求解劃分階段。狀態(tài)：描述事物的性質(zhì)，不同事物有不同的性質(zhì)，因而用不同的狀態(tài)來刻畫。對問題的求解狀態(tài)的描述是分階段的。決策：根據(jù)題意要求，對每個階段所做出的某種選擇性操作。狀態(tài)轉(zhuǎn)移方程：用數(shù)學公式描述與階段相關(guān)的狀態(tài)間的演變規(guī)律。21動態(tài)規(guī)劃是運籌學的一個重要分支，是解決多階段決策過程最優(yōu)化的一種方法。所謂多階段決策過程，是將所研究的過程劃分為若干個相互聯(lián)

11、系的階段，在求解時，對每一個階段都要做出決策，前一個決策確定以后，常常會影響下一個階段的決策。22 動態(tài)規(guī)劃所依據(jù)的是“最優(yōu)性原理”。 “最優(yōu)性原理”可陳述為：不論初始狀態(tài)和第一步?jīng)Q策是什么，余下的決策相對于前一次決策所產(chǎn)生的新狀態(tài)，構(gòu)成一個最優(yōu)決策序列。 最優(yōu)決策序列的子序列，一定是局部最優(yōu)決策子序列。 包含有非局部最優(yōu)的決策子序列，一定不是最優(yōu)決策序列。23 動態(tài)規(guī)劃的指導(dǎo)思想是：在做每一步?jīng)Q策時，列出各種可能的局部解，之后依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解。這樣，在每一步都經(jīng)過篩選，以每一步都是最優(yōu)的來保證全局是最優(yōu)的。篩選相當于最大限度地有效剪枝（從搜索角度看），效率

12、會十分高。 貪心法與動態(tài)規(guī)劃思想不同：貪心法只能做到局部最優(yōu)，不能保證全局最優(yōu)，因為有些問題不符合最優(yōu)性原理。24兩種算法的差別在于， 貪心法產(chǎn)生一個按貪心策略形成的判定序列，該序列不保證解是全局最優(yōu)的。 動態(tài)規(guī)劃會產(chǎn)生許多判定序列，再按最優(yōu)性原理對這些序列加以篩選，去除那些非局部最優(yōu)的子序列。25 動態(tài)規(guī)劃舉例任務(wù)： 編寫一個程序做到在一個給定的數(shù)字串中插入 k 個乘號使總的乘積最大。 如何尋找解題思路？我們還是從具體例子說起吧 26 * * * s 3 2 1 5 1 2 5 0 1 2 3 4 5 6 請插入3個乘號使乘積最大 32*15*12*5=28800 第1種方案 3*215*1

13、2*5=38700 第2種方案 321*51*2*5=163710 第3種方案 27 定義 : p(l , r , k )為從 l 到 r 加入 k 個乘號的最大乘積值. d (l , q)= sl sl+1sq 令 p(l , r , k ) =d(l ,q) * p(q+1,r,k-1) 插入一個乘號* l l+1 l+2 . . . q q+1 q+2 . . . r d ( l , q ) p(q+1,r,k-1) 不帶乘號的數(shù)字串 帶 k-1 個乘號的數(shù)字串 28p( l,r,k )=max d( l, q ) * p( q+1, r ,k-1 ) q q = l, l+1, , r

14、-k q * q=l=0 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,0)=3 p( q+1,r,k-1 )=p( 1,6,2 ) (p( 0,6,3)|q=0) = 3 * p( 1,6,2 ) 3 * 215125 29 q= l+1=1 * 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d(l,q)=d(0,1)= 32 p( q+1,r,k-1 )=p( 2,6,2 ) (p( 0,6,3)|q=1) = 32 * p( 2,6,2 )30 q=l+2=2 * 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,

15、2)=321 p( q+1,r,1 )=p( 3,6,2 ) (p( 0,6,3)|q=2) = 321 * p( 3,6,2 )31 q=l+3=3 * 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,3)=3215 p( q+1,r,k-1 )=p( 4,6,2 ) ( p( 0,6,3)|q=3) = 3215 * p( 4,6,2 )32p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3,6,2 ) , / q=2 3215 * p( 4,6,2 ) / q=3

16、33p( 1,6,2 ) 2 1 5 1 2 5 2 * p(2,6,1 ) 1 2 3 4 5 6 2 1 5 1 2 5 21 * p(3,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 215 * p(4,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 2151 * p(5,6,1) 1 2 3 4 5 6 34 p( 2,6,1 ) 1 5 1 2 5 1* 5125 2 3 4 5 6 1 5 1 2 5 15 * 125 2 3 4 5 6 1 5 1 2 5 15 1* 25 2 3 4 5 6 1 5 1 2 5 1512 *5 2 3 4 5 6 35 p

17、(2,6,1) = max 1 * 5125 , 15 * 125 , 151 * 25 , 1512 * 5 = 7560 36 p( 3,6,1 ) 5 1 2 5 5 * 125 3 4 5 6 5 1 2 5 51 * 25 3 4 5 6 5 1 2 5 5 12* 5 3 4 5 6 p( 3,6,1 )=max5*125, 51*25, 512*5 = 2560 37 p( 4,6,1 ) 1 2 5 1 * 25 4 5 6 1 2 5 12 * 5 4 5 6 p( 4,6,1 ) = max 1 * 25, 12 * 5 = 6038 p( 5,6,1 ) 2 5 2 *

18、5 5 6 p(5,6,1) = 1039 p( 2,6,2 ) 1 5 1 2 5 1* p(3,6,1 ) 2 3 4 5 6 1 5 1 2 5 15 * p(4,6,1) 2 3 4 5 6 1 5 1 2 5 151 * p(5,6,1) 2 3 4 5 6 p( 2,6,2 )= 1 * 2560, 15 * 60, 151 * 10 = 256040 p( 3,6,2 ) 5 1 2 5 5 * p(4,6,1 ) 3 4 5 6 5 1 2 5 51 * p(5,6,1) 3 4 5 6 p( 3,6,2 ) = 5 * 60 , 51 * 10 = 510 41 p( 4,6

19、,2 ) 1 2 5 1 * 2 * 5 4 5 6 p( 4,6,2 ) = 1042 p( 4,6,2 ) 1 2 5 1* p(5,6,1 ) 4 5 6 p(5,6,1) = 2 * 5 = 10 p(4,6,2) = 1 * p(5,6,1) = 10 43p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3,6,2 ) , / q=2 3215 * p( 4,6,2 ) / q=3 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 2560 p( 3,6,2 ) = 510 p(

20、 4,6,2 ) = 6044p( 1,6,2 ) 2 1 5 1 2 5 2 * p(2,6,1 ) 1 2 3 4 5 6 2 1 5 1 2 5 21 * p(3,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 215 * p(4,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 2151 * p(5,6,1) 1 2 3 4 5 6 45 p( 1,6,2 )= max 2 * p( 2,6,1 ) , 21 * p( 3,6,1) , 215 * p( 4,6,1) , 2151 * p( 5,6,1) =max2*7560,21*2560,215*60,2151*

21、10 = 53760 46p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3,6,2 ) , / q=2 3215 * p( 4,6,2 ) / q=3 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 2560 p( 3,6,2 ) = 510 p( 4,6,2 ) = 6047p( 0,6,3)= max 3 * 53760 , 32 * 2560 , 321* 510, 3215 * 60 = 163710 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 2560 p( 3,6,2 ) = 510 p( 4,6,2 ) = 6048 P(l,r,k) k=0 k !=0 d(l,r) q=l q=l+1 q=r-k p(l+1,r,k-1) 求max值 d(l,l)* p(l+1,r,k-1) d(l,r-k)* p(r-k+1,r,k-1) p(r-k+1,r,k-1) p(l+2,r,k-1) d(l,l+1)* p(l+2,r,k-1) 49 dij j 0 1 2 3 4 5 6 i 0 3 32 321 3215 32151 321512 3215125