ACM培訓(xùn)03-動(dòng)態(tài)規(guī)劃課件

10動(dòng)態(tài)規(guī)劃10動(dòng)態(tài)規(guī)劃1圖1DAGCKBNPOMJFHELI312345214323142212223344階段1階段2階段3階段4階段5任務(wù)：P是出發(fā)點(diǎn)，從P到A，求最短路徑（圖1）圖1DAGCKBNPOMJFHELI3123452143232思路先看第5階段，到達(dá)A點(diǎn)有兩條路BA，需要2kmCA，需要3km令從PA的最短路徑為P(A)；從PB的最短路徑為P(B)；從PC的最短路徑為P(C)……P(A)=min{P(B)+2,P(C)+3}；P(B)=min{P(D)+1,P(E)+2}；P(C)=min{P(E)+5,P(F)+4}；思路先看第5階段，到達(dá)A點(diǎn)有兩條路3P(A)=min{P(B)+2,P(C)+3}；P(B)=min{P(D)+1,P(E)+2}；P(C)=min{P(E)+5,P(F)+4}；

D1B2A235P(B)EC4P(C)FP(A)=min{P(B)+2,P(C)+3}；4P(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(A)。…P(N)=2; 上述遞推公式告訴我們，要求P(A)需要先5選擇數(shù)據(jù)結(jié)構(gòu)，將每條路經(jīng)的長(zhǎng)度存在數(shù)組中。東西方向上的道路長(zhǎng)度存在兩維數(shù)組h[4][3]中規(guī)定數(shù)組的第一維為行號(hào)，第二維為列號(hào)。312345214323h[4][3]={{3,2,3},{2,1,4},{3,4,5},{3,1,2}};0121023選擇數(shù)據(jù)結(jié)構(gòu)，將每條路經(jīng)的長(zhǎng)度存在數(shù)組中。3123452146南北方向上道路長(zhǎng)度存至數(shù)組v[3][4]中，也規(guī)定第一維為行號(hào)，第二維為列號(hào)。0123210223441241223v[3][4]={{2,2,3,4},{4,1,2,4},{1,2,2,3}};南北方向上道路長(zhǎng)度存至數(shù)組v[3][4]中，也規(guī)定第一維為行7為了計(jì)算方便，將圖1改為圖2h[3][0]h[3][1]h[3][2]h[2][0]h[2][1]h[2][2]h[1][0]h[1][1]h[1][2]h[0][0]h[0][1]h[0][2]v[2][0]v[2][1]v[2][2]v[2][3]v[1][0]v[1][1]v[1][2]v[1][3]v[0][0]v[0][1]v[0][2]v[0][3](3,3)0213213yx圖2為了計(jì)算方便，將圖1改為圖2h[3][0]h[3][1]h[8求解過程為從(0,0)到(3,3)求最短路徑問題定義二維數(shù)組，P[4][4]={{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}},第一維為行，第二維為列。這時(shí)P(O)為P[0][1]；P(N)為P[1][0]；…P(A)為P[3][3]，以下為分階段遞推求解過程。對(duì)于階段1:P[0][0]=0;P[0][1]=P[0][0]+h[0][0]=0+3=3;P[1][0]=P[0][0]+v[0][0]=0+2=2;求解過程為從(0,0)到(3,3)求最短路徑問題對(duì)于階段9對(duì)于階段2P[1][1]=min{P[0][1]+v[0][1],P[1][0]+h[1][0]} =min{3+1,2+2}=4P[0][2]=P[0][1]+h[1][0]=3+2=5P[2][0]=P[1][0]+v[1][0]=2+4=6對(duì)于階段3P[1][2]=min{P[0][2]+v[0][2],P[1][1]+h[1][1]} =min{5+3,4+1}=5P[0][3]=P[0][2]+h[0][2]=5+3=8P[2][1]=min{P[1][1]+v[1][1],P[2][0]+h[2][0]} =min{4+1,6+1}=5P[3][0]=P[2][0]+v[2][0]=6+1=7對(duì)于階段210對(duì)于階段4P[1][3]=min{P[0][3]+v[0][3],P[1][2]+h[1][2]} =min{8+4,5+4}=9P[2][2]=min{P[1][2]+v[1][2],P[2][1]+h[2][1]} =min{5+2,5+4}=7P[3][1]=min{P[2][1]+v[2][1],P[3][0]+h[3][0]} =min{5+2,7+3}=7對(duì)于階段5P[2][3]=min{P[1][3]+v[1][3],P[2][2]+h[2][2]} =min{9+4,7+5}=12P[3][2]=min{P[2][2]+v[2][2],P[3][1]+h[3][1]} =min{7+2,7+1}=8對(duì)于階段411最后P[3][3]=min{P[2][3]+v[2][3],P[3][2]+h[3][2]} =min{12+3,8+2}=10

綜上，數(shù)組P的通項(xiàng)表示為P[i][j]=min((p[i-1][j]+v[i-1][j]),(p[i][j-1]+h[i][j-1]))(i,j>0)P[0][j]=P[0][j-1]+h[0][j-1] (i=0,j>0)P[i][0]=P[i-1][0]+v[i-1][0] (i>0,j=0)下面給出P數(shù)組中的數(shù)據(jù)01232100358245965712778103最后0123210035824596571277810312數(shù)組P的通項(xiàng)表示為P[i][j]=min((p[i-1][j]+v[i-1][j]),(p[i][j-1]+h[i][j-1]))(i,j>0)P[0][j]=P[0][j-1]+h[0][j-1] (i=0,j>0)P[i][0]=P[i-1][0]+v[i-1][0] (i>0,j=0)數(shù)組P的通項(xiàng)表示為13畫出用動(dòng)態(tài)規(guī)劃思想求出的各個(gè)路口對(duì)P點(diǎn)的最小距離。圖中圓圈里就是這個(gè)距離。箭頭表示所尋得的最佳行走路徑。（圖3）312345214323142212223344026734575578891210P點(diǎn)A點(diǎn)圖3畫出用動(dòng)態(tài)規(guī)劃思想求出的各個(gè)路口對(duì)P點(diǎn)的最小距離。圖中圓圈里14

參考程序如下參考程序如下15#include<iostream.h>intmin(int,int);intmain()//主函數(shù)

{inth[4][3]={{3,2,3},{2,1,4},{3,4,5},{3,1,2}};intv[3][4]={{2,2,3,4},{4,1,2,4},{1,2,2,3}};intp[4][4]={{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};p[0][0]=0;for(intj=1;j<4;j++) //y軸上的點(diǎn)p[0][j]=p[0][j-1]+h[0][j-1];for(inti=1;i<4;i++) //x軸上的點(diǎn)p[i][0]=p[i-1][0]+v[i-1][0];#include<iostream.h>16

for(inti=1;i<4;i++) //內(nèi)部的點(diǎn)for(intj=1;j<4;j++)p[i][j]=min((p[i-1][j]+v[i-1][j]), (p[i][j-1]+h[i][j-1]));cout<<“fromPtoAis”<<p[3][3]<<endl;//輸出每個(gè)路口對(duì)P點(diǎn)的最小距離for(inti=3;i>=0;i--){ifor(intj=0;j<=3;j++){cout<<p[i][j]<<"";}cout<<endl;}return0;0j}for(inti=1;i<4;i++) //內(nèi)部的點(diǎn)17intmin(inta,intb){if(a<=b)returna;elsereturnb;}intmin(inta,intb)18動(dòng)態(tài)規(guī)劃的幾個(gè)概念:階段：據(jù)空間順序或時(shí)間順序?qū)栴}的求解劃分階段。狀態(tài)：描述事物的性質(zhì)，不同事物有不同的性質(zhì)，因而用不同的狀態(tài)來刻畫。對(duì)問題的求解狀態(tài)的描述是分階段的。決策：根據(jù)題意要求，對(duì)每個(gè)階段所做出的某種選擇性操作。狀態(tài)轉(zhuǎn)移方程：用數(shù)學(xué)公式描述與階段相關(guān)的狀態(tài)間的演變規(guī)律。動(dòng)態(tài)規(guī)劃的幾個(gè)概念:19動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，是解決多階段決策過程最優(yōu)化的一種方法。所謂多階段決策過程，是將所研究的過程劃分為若干個(gè)相互聯(lián)系的階段，在求解時(shí)，對(duì)每一個(gè)階段都要做出決策，前一個(gè)決策確定以后，常常會(huì)影響下一個(gè)階段的決策。動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，是解決多階段決策過程最優(yōu)化的20

動(dòng)態(tài)規(guī)劃所依據(jù)的是“最優(yōu)性原理”?！白顑?yōu)性原理”可陳述為：不論初始狀態(tài)和第一步?jīng)Q策是什么，余下的決策相對(duì)于前一次決策所產(chǎn)生的新狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策序列。最優(yōu)決策序列的子序列，一定是局部最優(yōu)決策子序列。包含有非局部最優(yōu)的決策子序列，一定不是最優(yōu)決策序列。動(dòng)態(tài)規(guī)劃所依據(jù)的是“最優(yōu)性原理”。21動(dòng)態(tài)規(guī)劃的指導(dǎo)思想是：在做每一步?jīng)Q策時(shí)，列出各種可能的局部解，之后依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解。這樣，在每一步都經(jīng)過篩選，以每一步都是最優(yōu)的來保證全局是最優(yōu)的。篩選相當(dāng)于最大限度地有效剪枝（從搜索角度看），效率會(huì)十分高。但它又不同于貪心法。貪心法只能做到局部最優(yōu)，不能保證全局最優(yōu)，因?yàn)橛行﹩栴}不符合最優(yōu)性原理。動(dòng)態(tài)規(guī)劃的指導(dǎo)思想是：在做每一步?jīng)Q策22兩種算法的差別在于，貪心法產(chǎn)生一個(gè)按貪心策略形成的判定序列，該序列不保證解是全局最優(yōu)的。而動(dòng)態(tài)規(guī)劃會(huì)產(chǎn)生許多判定序列，再按最優(yōu)性原理對(duì)這些序列加以篩選，去除那些非局部最優(yōu)的子序列。兩種算法的差別在于，貪心法產(chǎn)生一個(gè)按貪心策略形成的判定序列，23

舉例說明動(dòng)態(tài)規(guī)劃思路

問題：在數(shù)字串中插入若干乘號(hào)使總的乘積最大

24***

s32151250123456

請(qǐng)插入3個(gè)乘號(hào)使乘積最大

32*15*12*5=288003*215*12*5=38700321*51*2*5=163710

25解題思路定義:從l

到r加入k個(gè)乘號(hào)的最大乘積值*p(l,r,k)

ll+1l+2...qq+1q+2...r

d(l,q)p(q+1,r,k-1)

d(l,q)=s[l]s[l+1]…s[q]解題思路26q的變化范圍：從q+1到r之間所包含的數(shù)字個(gè)數(shù)應(yīng)大于k-1（乘號(hào)個(gè)數(shù)）。r-(q+1)+1>k-1q<r-k+1q的變化范圍：從q+1到r之間所包含的數(shù)字個(gè)數(shù)應(yīng)大于k-1（27

p(l,r,k)=max{d(l,q)*p(q+1,r,k-1)}

q=l,l+1,…,r-k

*

q=l=032151250123456

d(l,q)=d(0,0)=3p(q+1,r,k-1)=p(1,6,2)(p(0,6,3)|q=0)=3*p(1,6,2)

28

q=l+1=1*32151250123456

d(l,q)=d(0,1)=32p(q+1,r,k-1)=p(2,6,2)

(p(0,6,3)|q=1)=32*p(2,6,2)

29

q=l+2=2*32151250123456

d(l,q)=d(0,2)=321p(q+1,r,1)=p(3,6,2)

(p(0,6,3)|q=2)=321*p(3,6,2)ACM培訓(xùn)03-動(dòng)態(tài)規(guī)劃30

q=l+3=3*

32151250123456

d(l,q)=d(0,3)=3215p(q+1,r,k-1)=p(4,6,2)

(p(0,6,3)|q=3)=3215*p(4,6,2)ACM培訓(xùn)03-動(dòng)態(tài)規(guī)劃31p(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(0,6,3)=max{3*p(1,6,232p(1,6,2)

2151252*p(2,6,1

)123456

215125

21*p(3,6,1)123456

215125

215*p(4,6,1)123456

215125

2151*p(5,6,1)123456

p(1,6,2)33

p(2,6,1)

151251*512523456

1

5125

15*12523456

15

125

15

1*2523456

151

25

1512*523456

p(2,6,1)34

p(2,6,1)=max{1*5125,15*125,151*25,

1512*5}=7560

35

p(3,6,1)

51255*1253456

5

125

51*253456

5

125

5

12*53456p(3,6,1)=max{5*125,51*25,512*5}

=2560

p(3,6,1)36

p(4,6,1)

1251*25456

125

12*5456

p(4,6,1)=max{1*25,12*5}

=60p(4,6,1)37

p(5,6,1)

252*556

p(5,6,1)=10p(5,6,1)38

p(2,6,2)

151251*p(3,6,1

)23456

1

5125

15*p(4,6,1)23456

15

125

151*p(5,6,1)23456

p(2,6,2)={1*2560,15*60,151*10}

=2560p(2,6,2)39

p(3,6,2)

51255*p(4,6,1

)3456

5125

51*p(5,6,1)3456

p(3,6,2)={5*60,51*10}=510

p(3,6,2)40

p(4,6,2)

1251*2*5456

p(4,6,2)=10

41

p(4,6,2)

1251*p(5,6,1

)456

p(5,6,1)=2*5=10

p(4,6,2)=1*p(5,6,1)=10

p(4,6,2)42p(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)=53760p(2,6,2)=2560

p(3,6,2)

=510

p(4,6,2)=60p(0,6,3)=max{3*p(1,6,243p(1,6,2)

2151252*p(2,6,1

)123456

215125

21*p(3,6,1)123456

215125

215*p(4,6,1)123456

215125

2151*p(5,6,1)123456

p(1,6,2)44

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)}=max{2*7560,21*2560,215*60,2151*10}=53760

45p(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)=53760p(2,6,2)=2560

p(3,6,2)

=510

p(4,6,2)=60p(0,6,3)=max{3*p(1,6,246p(0,6,3)=max{3*53760,

32*2560,

321*510,3215*60}=163710

p(1,6,2)=53760p(2,6,2)=2560

p(3,6,2)

=510

p(4,6,2)=60p(0,6,3)=max{3*53760,47分析狀態(tài)轉(zhuǎn)移方程p(l,r,k)=max{d(l,q)*p(q+1,r,k-1)}

q=l,l+1,…,r-k

要求p(l,r,k)先要求p(q+1,r,k-1)是一個(gè)遞歸問題。對(duì)p(l,r,k)而言，字符串下界是l上界是r，對(duì)p(q+1,r,k-1)而言，字符串下界是q+1上界是r，乘號(hào)數(shù)為k-1這時(shí)很容易計(jì)算出要從多少個(gè)子項(xiàng)中選一個(gè)最大的出來：

p(q+1,r,k-1)=max{d(q+1，t)*p(t+1,r,k-2)}t=q+1,q+2,…,r-(k-1)遞歸的邊界是P(u,r,0)=d(u,r)=SuSu+1…..Sr是不含乘號(hào)的數(shù)字串的值，可構(gòu)建下表，事先將d(u,r)算出備用。分析狀態(tài)轉(zhuǎn)移方程p(l,r,k)=max{d(l,48

P(l,r,k)

k=0k!=0d(l,r)

q=l

q=l+1q=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

d[i][j]

j0123456i0332321321532151321512321512512212152151215122151252115151151215125355151251254112125522565d[i][j]j01250

怎樣計(jì)算這張表?分兩步1.先算出j=6那一列的數(shù)：d[i][6],i=0,1,2,3,4,5,6.

d[0][6]=s=3215125

去掉最高位3就是d[1][6]=215125=3215125%1000000=s%1000000s1=1000000=s%s1

s1=s1/10

d[2][6]=d[1][6]%s1怎樣計(jì)算這張表?分兩步1.先算出j=651

s1=1000000;d[0][6]=s;for(inti=1;i<=6;i++){d[i][6]=d[i-1][6]%s1;s1=s1/10;}s1=1000000;52

怎樣求d[i][5],d[i][4],…d[i][0]?d[i][5]=d[i][6]/10,i=0,1,2,3,4,5,6for(intj=5;j>=0;j--)for(inti=0;i<=j;i++){d[i][j]=d[i][j+1]/10;}

53

參考程序#include<iostream>//預(yù)編譯命令#include<cstring>//預(yù)編譯命令usingnamespacestd;//使用名字空間constintS=3215125;//定義常整數(shù)intd[7][7];//定義二維數(shù)組參考程序54

intP(intl,intr,intk)//計(jì)算P函數(shù)值{if(k==0)returnd[l][r];intx,ans=0;for(intq=1;q<=r-k;q++){x=d[l][q]*P(q+1,r,k-1);if(x>ans)ans=x;}returnans;}intP(intl,intr,intk)55intmain(){memset(d,0,sizeof(d));//初始化數(shù)組元素為0ints1=1000000;d[0][6]=s;for(inti=1;i<=6;i++){d[i][6]=d[i-1][6]%s1;s1=s1/10;}intmain()56

for(intj=5;j>=0;j--)for(inti=0;i<=j;i++){d[i][j]=d[i][j+1]/10;}

cout<<P(0,6,3)<<endl;return0;}for(intj=5;j>=0;57

hanoi塔問題的動(dòng)態(tài)規(guī)劃解法

令m－－－柱子數(shù)

n－－－圓盤數(shù)

hanoi(m,n)表示具有m根柱子n個(gè)圓盤的搬移設(shè)起始柱為from終止柱為to中轉(zhuǎn)柱為temp[i]i=1,2,…m-2hanoi塔問題的動(dòng)態(tài)規(guī)劃解法58

思路

將from上的圓盤分成上下兩部分，下面的盤數(shù)為k,上面的為n-k。先用hanoi(m,n-k)將from上的n-k個(gè)圓盤借助于其他圓盤搬至temp[m-2](也可以用別的);然后再用hanoi(m-1,k)將下面k個(gè)從from移至to;

之后再將temp[m-2]上的n-k個(gè)圓盤,借助于其他圓盤,用hanoi(m,n-k)搬至to

思路59

第1步第3步

n-k個(gè)

k個(gè)

fromtemp[1]temp[2]to

第2步

60

搬移過程廣義數(shù)學(xué)式

hanoi(m,n)=hanoi(m,n-k)+hanoi(m-1,k)+hanoi(m,n-k)

抽象為h=a+b+c

令s(m,n)---hanoi(m,n)的最少移動(dòng)步數(shù)

s(m,n)=min{s(m,n-k)+s(m-1,k)+s(m,n-k)}

k

k=1,2,…,nm>3k=1m=3搬移過程廣義數(shù)61m為柱子數(shù)，n為盤子數(shù)k是下面盤子數(shù)

s(m,n)=min{2*s(m,n-k)+s(m-1,k)}

k

1.s(m,n)=1,m=2,n=1

2.s(m,n)=1,m=3,n=13.s(m,n)=3,m=3,n=24.s(m,n)=3,m=4,n=25.s(m,n)=7,m=3,n=36.s(m,n)=5,m=4,n=3m為柱子數(shù)，n為盤子數(shù)k是下面盤子數(shù)62

1245

fromtemp[1]temp[2]to3

63

分析：k值的選擇是關(guān)鍵1.問題的解決有若干個(gè)階段，是一個(gè)多步?jīng)Q策的過程。2.對(duì)于階段b而言，階段a的解決與之無關(guān),相關(guān)的只是階段a解決后的狀態(tài)。問題的階段劃分滿足無后效性的要求。3.問題的最優(yōu)策略是各階段最優(yōu)子策略的組合，若問題h取得最優(yōu)解，則其在階段a,b,c上也必然取得最優(yōu)解。問題滿足動(dòng)態(tài)規(guī)劃的最優(yōu)性原理。分析：k值的選擇是關(guān)鍵64

動(dòng)態(tài)規(guī)劃一般式

min{s(m,n-k)+s(m-1,k)+s(m,n-k)}

k

k=1,2,…,m>3n>1s(m,n)=k=1m=3n>1

1m=2n=1

0其它動(dòng)態(tài)規(guī)劃一般式65

m=3,n=2k=1s(m,n)=min{2*s(m,n-k)+s(m-1,k)}s(3,2)=min{2*s(3,2-1)+s(3-1,1)}=min{2*s(3,1)+s(2,1)}=min{2*1+1}=3

66

m=3,n=3k=1s(m,n)=min{2*s(m,n-k)+s(m-1,k)}s(3,3)=min{2*s(3,3-1)+s(3-1,1)}=min{2*s(3,2)+s(2,1)}=min{2*3+1}=7

67

m=3,n=4k=1s(m,n)=min{2*s(m,n-k)+s(m-1,k)}s(3,4)=min{2*s(3,4-1)+s(3-1,1)}=min{2*s(3,3)+s(2,1)}=min{2*7+1}=15

68

m=3,n=5k=1s(m,n)=min{2*s(m,n-k)+s(m-1,k)}s(3,5)=min{2*s(3,5-1)+s(3-1,1)}=min{2*s(3,4)+s(2