動態(tài)規(guī)劃思想入門(論文)

1、動態(tài)規(guī)劃思想入門陳喻2008年10月7日關(guān)鍵字：動態(tài)規(guī)劃，最優(yōu)子結(jié)構(gòu)，記憶化搜索引言動態(tài)規(guī)劃(dynamicprogramming)是運籌學(xué)的一個分支，是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法動態(tài)規(guī)劃。1957年出版了他的名著DynamicProgramming，這是該領(lǐng)域的第一本著

2、作。動態(tài)規(guī)劃問世以來，在經(jīng)濟管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。動態(tài)規(guī)劃的基本思想動態(tài)規(guī)劃是：將待求的問題分解成假設(shè)干個相互聯(lián)系的子問題，先求解子問題，然后從這些子問題的解得到原問題的解；對于重復(fù)出現(xiàn)的子問題，只在第一次遇到的時候?qū)λ苯忧蠼猓汛鸢副４嫫饋?，讓以后再次遇到是?/p>

3、接引用答案，不必從新求解，其實質(zhì)是分治思想和解決冗余。例1:求A>B的最短路徑圖1這是一個利用動態(tài)規(guī)劃思想的經(jīng)典問題，通過直接觀察圖1我們可以枚舉出20多條路徑，并可以計算出其中最短的路徑長度為16用動態(tài)規(guī)劃的思想來分析，我們可以把這個問題轉(zhuǎn)換成下面這個模型階段：根據(jù)問題的特點和需要，將問題按時間或空間特征分解為假設(shè)干相互聯(lián)系的階段。在本例中，我們根據(jù)空間特性將問題分成了6個階段。狀態(tài)：各階段的開始條件，本例中，A,B,CP這些節(jié)點都屬于狀態(tài)，表示從該點到B的最短路徑，在這里我們計做S(i),表示從第i個節(jié)點狀態(tài)到B的最短路徑?jīng)Q策：某階段狀態(tài)確定后，從該狀態(tài)到下階段某狀態(tài)的選擇。比方S(

4、A),它可以選擇通過C到達(dá)B,也可以選擇通過D到達(dá)B。狀態(tài)轉(zhuǎn)移方程：系統(tǒng)由某階段的一個狀態(tài)轉(zhuǎn)變到下一階段的另一狀態(tài)稱狀態(tài)轉(zhuǎn)移，表達(dá)轉(zhuǎn)移規(guī)律的方程稱狀態(tài)轉(zhuǎn)移方程。在本例中，我們不難推出S(A尸MINS(C)+4,S(D)+3,S(C尸MINS(E)+5,S(F)+3S(B)=0,由此我們可以得出狀態(tài)轉(zhuǎn)移方程S(i)=MINS(j)+Vij(j為與i相鄰接的節(jié)點,Vij表示鄰接節(jié)點i,j之間的距離)。一個動態(tài)規(guī)劃模型應(yīng)該滿足以下幾個性質(zhì):最優(yōu)子結(jié)構(gòu)可這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不管過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的

5、子策略總是最優(yōu)的。例如在圖2的模型中，S(A)是A到B的最短路徑(最優(yōu)策略)，而它所依賴的S(C)和S(D)作為S(A)的子策略分別是C到B的最短路徑和D到B的最短路徑，也是最優(yōu)的。因此根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)我們得出了上面的狀態(tài)轉(zhuǎn)移方程。證明：如圖2設(shè)路線W1=(A,C),(C,F),(F,J)W2=(J,M),(M,O),(O,B)假設(shè)品&線W1和W2是A到B的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線W2必是從J到B的最優(yōu)路線。用反證法證明：假設(shè)有另一路徑W2'是J到B的最優(yōu)路徑，則A到B的路線取W1和W2'比W1和W2更優(yōu)，矛盾。從而證明W2'必是J到B的最優(yōu)路徑W2。

6、最優(yōu)子結(jié)構(gòu)性質(zhì)是動態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)子結(jié)構(gòu)性質(zhì)的支持，就不可能用動態(tài)規(guī)劃方法計算。根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)導(dǎo)出的動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程是解決一切動態(tài)規(guī)劃問題的基本方法?？梢钥闯觯瑘D2的模型是滿足最優(yōu)子結(jié)構(gòu)性質(zhì)的。2.子問題重疊性質(zhì)在我們根據(jù)狀態(tài)轉(zhuǎn)移方程用遞歸算法自頂向下對問題進(jìn)行求解時，每次產(chǎn)生的子問題并不總是新的，而且某些子問題會被重復(fù)計算多次，比方，在求SC時需要遞歸求出SF的值，而在求SD時也需要遞歸求出SF的值，因此整個求解過程中SF的值會被求解兩次，如果我們能把這多余的一次重復(fù)計算剔除，將可以最大程度的提高程序執(zhí)行效率；動態(tài)規(guī)劃正是利用了這種子問題的重疊性質(zhì)，對每個子問題

7、只計算一次，然后將其結(jié)果保存在一個表格中，當(dāng)再次需要計算已經(jīng)計算過的子問題時，只是在表格中簡單的查詢一下結(jié)果，從而獲得較高的解題效率，這個方法就是我們常說的記憶化搜索。因此，如果我們把第一次求解出的SF的值用一種數(shù)據(jù)結(jié)構(gòu)保存下來，下次再用到SF時，我們直接去查，這樣能使程序的時間和空間效率將會大大提高。下面通過對具體實例的分析，幫助大家領(lǐng)會動態(tài)規(guī)劃的這兩個性質(zhì)和動態(tài)規(guī)劃的算法設(shè)計思想例：導(dǎo)彈攔截某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng).但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度.某大，雷達(dá)捕捉到敵國的導(dǎo)彈來襲.由于該

8、系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈.輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)）,計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，并依次輸出被攔截的導(dǎo)彈飛來時候的高度.樣例：INPUT38920715530029917015865OUTPUT6（最多能攔截的導(dǎo)彈數(shù)）38930029917015865分析：因為只有一套導(dǎo)彈攔截系統(tǒng)，并且這套系統(tǒng)除了第一發(fā)炮彈能到達(dá)任意高度外,以后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度；所以,被攔截的導(dǎo)彈應(yīng)該按飛來的高度組成一個非遞增序列.題目要求我們計算這套系統(tǒng)最多能攔截的導(dǎo)彈數(shù)，并依次輸出被攔截導(dǎo)彈的高度，實際上就是要求

9、我們在導(dǎo)彈依次飛來的高度序列中尋找一個最長非遞增子序列.解決思路：設(shè)X=x1,x2,xn為依次飛來的導(dǎo)彈序列，Y=y1,y2,yk為問題的最優(yōu)解（即X的最長非遞增子序列）,s為問題的狀態(tài)（表示導(dǎo)彈攔截系統(tǒng)當(dāng)前發(fā)送炮彈能夠到達(dá)的最大高度，初值為s=第一發(fā)炮彈能夠到達(dá)任意的高度）.如果y1=x1,即飛來的第一枚導(dǎo)彈被成功攔截.那么，根據(jù)題意"每一發(fā)炮彈都不能高于前一發(fā)的高度"，問題的狀態(tài)將由s=8變成s<x1（x1為第一枚導(dǎo)彈的高度）；在當(dāng)前狀態(tài)下，序列Y1=y2,yk也應(yīng)該是序列X1=x2,xn的最長非遞增子序列（用反證法很容易證明）.也就是說，在當(dāng)前狀態(tài)s<x1

10、下，問題的最優(yōu)解Y所包含的子問題（序列X1）的解（序列Y1）也是最優(yōu)的.這就是攔截導(dǎo)彈問題的最優(yōu)子結(jié)構(gòu)性質(zhì).根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)推出狀態(tài)轉(zhuǎn)移方程：設(shè)D(i)為第i枚導(dǎo)彈被攔截之后，這套系統(tǒng)最多還能攔截的導(dǎo)彈數(shù)(包含被攔截的第i枚).我們可以設(shè)想，當(dāng)系統(tǒng)攔截了第k枚導(dǎo)彈xk，而xk又是序列X=xk,xn中的最小值，即第k枚導(dǎo)彈之后飛來的導(dǎo)彈高度都比它高，則有D(k)=1;當(dāng)系統(tǒng)攔截了最后一枚導(dǎo)彈xn，那么，系統(tǒng)最多也只能攔截這一枚導(dǎo)彈了,即D(n)=1;其它情況下，也應(yīng)該有D(i)>1.根據(jù)以上分析，可歸納出問題的動態(tài)規(guī)劃遞歸方程為："1(i=n或者xi=minxiXn)D(i)=

11、<mMaxD(j)+1(j>i且j<=n且xj<=xi)假設(shè)系統(tǒng)最多能攔截的導(dǎo)彈數(shù)為dmax(即問題的最優(yōu)值),則dmax(i為被系統(tǒng)攔截的第一枚導(dǎo)彈的順序號)所以,要計算問題的最優(yōu)值dmax,需要分別計算出D(1),D(2),D(n)的值,然后將它們進(jìn)行比較，找出其中的最大值.即：dmax=maxD(i)(1<=i且i<=n)分析子問題重疊，解決冗余根據(jù)上面分析出來的遞歸方程，我們完全可以設(shè)計一個遞歸函數(shù)，采用自頂向下的方法計算D(i)的值.然后，對i從1到n分別調(diào)用這個遞歸函數(shù)，就可以計算出D(1),D(2),D(n).程序如下：intD(inti)in

12、tj,max=0;if(i=n)|(min(x,i,n)=xi)/min(x,i,n)返回數(shù)組x在下標(biāo)in之間的最小值return1;else學(xué)習(xí)文檔僅供參考for(j=i+1;j<=n;j+)if(xj<=xi)if(D(j)+1>max)max=D(j)+1;returnmax;從這個程序的遞歸模型中可以看出，會有大量的子問題被重復(fù)計算.比方在調(diào)用遞歸函數(shù)計算D(1)的時候,可能需要先計算D(5)的值;之后在分別調(diào)用遞歸函數(shù)計算D(2),D(3),D(4)的時候,都有可能需要先計算D(5)的值.如此一來,在整個問題的求解過程中,D(5)可能會被重復(fù)計算很多次,從而造成了冗

13、余,降低了程序的效率.其實,通過以上分析,我們已經(jīng)知道:D(n)=1.如果將n作為階段對問題進(jìn)行劃分,根據(jù)問題的動態(tài)規(guī)劃遞歸方程,我們可以采用自底向上的方法依次計算出D(n-1),D(n-2),D(1)的值.這樣，每個D(i)的值只計算一次，并在計算的同時把計算結(jié)果保存下來,程序如下：voidD()inti,j;for(i=1;i<=n;i+)d(i)=1for(i=n-1;i>=1;i-)for(j=i+1;j<=n;j+)if(x(j)<=x(i)&&d(i)=d(j)+1>dmax)dmax=d(i);xh=i;由此我們出了最大攔截數(shù)的第一枚

14、導(dǎo)彈的順序號xh,即d(xh)為問題的解從而防止了有些子問題被重復(fù)計算的情況發(fā)生,提高了程序的效率.在實際應(yīng)用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解即滿足最優(yōu)子化原理，則可以考慮用動態(tài)規(guī)劃解決，也就是分治算法的思想。例2：傳球游戲NOIP2008普及組第三題【問題描述】上體育課的時候，小蠻的老師經(jīng)常帶著同學(xué)們一起做游戲。這次，老師帶著同學(xué)們一起做傳球游戲。游戲規(guī)則是這樣的：n個同學(xué)站成一個圓圈，其中的一個同學(xué)手里拿著一個球，當(dāng)老師吹哨子時開始傳球，每個同學(xué)可以把球傳給自己左右的兩個

15、同學(xué)中的一個左右任意，當(dāng)老師再次吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學(xué)就是敗者，要給大家表演一個節(jié)目。聰明的小蠻提出一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了m次以后，又回到小蠻手里。兩種傳球的方法被視作不同的方法，當(dāng)且僅當(dāng)這兩種方法中，接到球的同學(xué)按接球順序組成的序列是不同的。比方有3個同學(xué)1號、2號、3號，并假設(shè)小蠻為1號，球傳了3次回到小蠻手里的方式有1->2->3->1和1->3->2->1，共2種。【輸入】輸入文件ball.in共一行，有兩個用空格隔開的整數(shù)n，m3<=n<=30，1<=m

16、<=30?！据敵觥枯敵鑫募all.out共一行，有一個整數(shù)，表示符合題意的方法數(shù)?！据斎胼敵鰳永繉W(xué)習(xí)文檔 僅供參考ball.out2【限制】40%的數(shù)據(jù)滿足：3<=n<=30,1<=m<=20100%的數(shù)據(jù)滿足：3<=n<=30,1<=m<=30解決思路：給n個同學(xué)從1n編號，設(shè)狀態(tài)Fp,t表示傳了t次球后，球在p手中，在剩下的m-t次傳球中共有多少種方案到達(dá)1,由于在問題的求解中，球是從1號開始傳，并最后回到1號，顯然我們所求的目標(biāo)狀態(tài)就是是F1,0o由于球只能傳遞給左右的兩個同學(xué)，也只能通過左右的兩個同學(xué)傳遞給自己，如以下圖：學(xué)習(xí)文

17、檔僅供參考由此，我們分析出F1,0的解只與F1,1和Fn,1有關(guān)，而F1,1和Fn,1也是最優(yōu)問題解，因此，該問題符合最優(yōu)子結(jié)構(gòu)性質(zhì)。根據(jù)最優(yōu)性原理我們可以得到以下狀態(tài)轉(zhuǎn)移方程:1(t=m,p=1)F(P，t尸00(t=m,p!=1),0<=t<m)IFRp,t+1+FLp,t+1(1<=p<=nRp:p右邊同學(xué)的編號Lp:p左邊同學(xué)的編號通過以上分析，根據(jù)狀態(tài)轉(zhuǎn)移方程，運用記憶化搜索策略，采用自頂向下的過程可遞歸求出F1,0，程序如下：#include<stdio.h>#include<stdlib.h>#definemaxn31最大人數(shù)，編號

18、從1n#definemaxm30/最大傳球次數(shù)longfmaxnmaxm;/表示傳了T次球以后球在P號手里，包括在剩下的M-T次傳球中有多少種方法走到1longm,n;voidfind(longp,longt)if(t=m)/傳了M次球了if(p=1)/傳到了1fpt=1;else/沒傳到1fpt=0;return;if(fpt!=-1)return;/如果這個狀態(tài)搜到過了，沒必要再搜fpt=0;/標(biāo)記該狀態(tài)被搜過了find(p%n+1,t+1);/搜把球傳給P右邊的同學(xué)的狀態(tài)fpt+=fp%n+1t+1;intp1=p-1;if(p1=0)p1=n;find(p1,t+1);/搜把球傳給P左邊的同學(xué)的狀態(tài)fpt+=fp1t+1;main()inti,j;/一開始所有狀態(tài)都沒到過for(i=0;i<maxn;i+)for(j=0;j<maxm;j+)fij=-1;scanf("%d%d",&n,&m);find(1,0);printf("%ld",f10);代入數(shù)據(jù)測算例：input:33數(shù)據(jù)模型如下：由于采用了記憶化搜索，處于不同位置的相同狀態(tài)不會被多次搜索，因此可以在O(mxn)的時間復(fù)雜度內(nèi)完成任務(wù)，同樣防止了子問題被重復(fù)計算的情況。由此可知