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

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

2、，這是該領(lǐng)域的第一本著作。 動態(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ī)劃)，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。動態(tài)規(guī)劃的基本思想動態(tài)規(guī)劃是：將待求的問題分解成若干個相互聯(lián)系的子問題，先求解子問題，然后從這些子問題的解得到原問題的解；對于重復(fù)出現(xiàn)的子問題，只在第一次遇到的時候?qū)λ苯忧蠼猓汛鸢副４嫫?/p>

3、來，讓以后再次遇到是直接引用答案，不必從新求解，其實質(zhì)是分治思想和解決冗余。例1：求AB的最短路徑圖1這是一個利用動態(tài)規(guī)劃思想的經(jīng)典問題，通過直接觀察圖1我們可以枚舉出20多條路徑，并可以計算出其中最短的路徑長度為16階段用動態(tài)規(guī)劃的思想來分析，我們可以把這個問題轉(zhuǎn)換成下面這個模型狀態(tài)決策圖2階段：根據(jù)問題的特點和需要，將問題按時間或空間特征分解為若干相互聯(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)確定后，從該

4、狀態(tài)到下階段某狀態(tài)的選擇。比如S(A)，它可以選擇通過C到達B，也可以選擇通過D到達B。狀態(tài)轉(zhuǎn)移方程：系統(tǒng)由某階段的一個狀態(tài)轉(zhuǎn)變到下一階段的另一狀態(tài)稱狀態(tài)轉(zhuǎn)移，體現(xiàn)轉(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)移方程(i)=MINS(j)+Vij(j為與i相鄰接的節(jié)點，Vij表示鄰接節(jié)點i，j之間的距離)。一個動態(tài)規(guī)劃模型應(yīng)該滿足以下幾個性質(zhì)：1.最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)可這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余

5、下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(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)若路線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的最

6、優(yōu)路徑W2。最優(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ī)劃問題的基本方法。可以看出，圖2的模型是滿足最優(yōu)子結(jié)構(gòu)性質(zhì)的。2子問題重疊性質(zhì)在我們根據(jù)狀態(tài)轉(zhuǎn)移方程用遞歸算法自頂向下對問題進行求解時，每次產(chǎn)生的子問題并不總是新的，而且某些子問題會被重復(fù)計算多次，比如，在求S（C）時需要遞歸求出S（F）的值，而在求S（D）時也需要遞歸求出S（F）的值，因此整個求解過程中S（F）的值會被求解兩次，如果我們能把這多余的一次重復(fù)計算剔除，將可以最大程度的提高程序執(zhí)行效率；動態(tài)規(guī)劃正是利用了這種

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

8、某天,雷達捕捉到敵國的導(dǎo)彈來襲.由于該系統(tǒng)還在試用階段,所以只有一套系統(tǒng),因此有可能不能攔截所有的導(dǎo)彈.輸入導(dǎo)彈依次飛來的高度(雷達給出的高度數(shù)據(jù)是不大于 30000 的正整數(shù)),計算這套系統(tǒng)最多能攔截多少導(dǎo)彈,并依次輸出被攔截的導(dǎo)彈飛來時候的高度.樣例:INPUT389 207 155 300 299 170 158 65OUTPUT6 (最多能攔截的導(dǎo)彈數(shù))389 300 299 170 158 65分析: 因為只有一套導(dǎo)彈攔截系統(tǒng),并且這套系統(tǒng)除了第一發(fā)炮彈能到達任意高度外,以后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度;所以,被攔截的導(dǎo)彈應(yīng)該按飛來的高度組成一個非遞增序列.題目要求我們計算

9、這套系統(tǒng)最多能攔截的導(dǎo)彈數(shù),并依次輸出被攔截導(dǎo)彈的高度,實際上就是要求我們在導(dǎo)彈依次飛來的高度序列中尋找一個最長非遞增子序列.解決思路：設(shè) X=x 1 ,x 2 ,x n 為依次飛來的導(dǎo)彈序列, Y=y 1 ,y 2 ,y k 為問題的最優(yōu)解(即 X 的最長非遞增子序列), s 為問題的狀態(tài)(表示導(dǎo)彈攔截系統(tǒng)當前發(fā)送炮彈能夠到達的最大高度,初值為 s= 第一發(fā)炮彈能夠到達任意的高度).如果 y 1 =x 1 ,即飛來的第一枚導(dǎo)彈被成功攔截.那么,根據(jù)題意每一發(fā)炮彈都不能高于前一發(fā)的高度,問題的狀態(tài)將由 s= 變成 sx 1 ( x 1 為第一枚導(dǎo)彈的高度);在當前狀態(tài)下,序列 Y 1 =y 2

10、 ,y k 也應(yīng)該是序列 X 1 =x 2 ,x n 的最長非遞增子序列(用反證法很容易證明).也就是說,在當前狀態(tài) sx 1 下,問題的最優(yōu)解 Y 所包含的子問題(序列 X 1 )的解(序列 Y 1 )也是最優(yōu)的.這就是攔截導(dǎo)彈問題的最優(yōu)子結(jié)構(gòu)性質(zhì).D(i)=1 (i=n或者xi=minxiXn)MaxD(j)+1 (ji且j=n且xj=xi)根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)推出狀態(tài)轉(zhuǎn)移方程：設(shè) D(i) 為第 i 枚導(dǎo)彈被攔截之后,這套系統(tǒng)最多還能攔截的導(dǎo)彈數(shù)(包含被攔截的第 i 枚).我們可以設(shè)想,當系統(tǒng)攔截了第 k 枚導(dǎo)彈 x k ,而 x k 又是序列 X=xk ,xn 中的最小值,即第 k 枚導(dǎo)

11、彈之后飛來的導(dǎo)彈高度都比它高,則有 D(k)=1 ;當系統(tǒng)攔截了最后一枚導(dǎo)彈 x n ,那么,系統(tǒng)最多也只能攔截這一枚導(dǎo)彈了,即 D(n)=1 ;其它情況下,也應(yīng)該有 D(i)1 .根據(jù)以上分析,可歸納出問題的動態(tài)規(guī)劃遞歸方程為:假設(shè)系統(tǒng)最多能攔截的導(dǎo)彈數(shù)為 dmax (即問題的最優(yōu)值),則dmax ( i 為被系統(tǒng)攔截的第一枚導(dǎo)彈的順序號)所以,要計算問題的最優(yōu)值 dmax ,需要分別計算出 D(1) , D(2) , D(n) 的值,然后將它們進行比較,找出其中的最大值.即：dmax=maxD(i)(1=i且i=n)分析子問題重疊，解決冗余根據(jù)上面分析出來的遞歸方程,我們完全可以設(shè)計一個遞

12、歸函數(shù),采用自頂向下的方法計算 D(i) 的值.然后,對 i 從 1 到 n 分別調(diào)用這個遞歸函數(shù),就可以計算出 D(1) , D(2) , D(n) .程序如下：int D(int i) int j,max=0;if(i=n)|(min(x,i,n)=xi)/min(x,i,n) 返回數(shù)組x在下標in之間的最小值 return 1; else for(j=i+1;j=n;j+) if(xjmax) max=D(j)+1; return max; 從這個程序的遞歸模型中可以看出，會有大量的子問題被重復(fù)計算.比如在調(diào)用遞歸函數(shù)計算 D(1) 的時候,可能需要先計算 D(5) 的值;之后在分別調(diào)用

13、遞歸函數(shù)計算 D(2) , D(3) , D(4) 的時候,都有可能需要先計算 D(5) 的值.如此一來,在整個問題的求解過程中, D(5) 可能會被重復(fù)計算很多次,從而造成了冗余,降低了程序的效率.其實,通過以上分析,我們已經(jīng)知道: D(n)=1 .如果將 n 作為階段對問題進行劃分,根據(jù)問題的動態(tài)規(guī)劃遞歸方程,我們可以采用自底向上的方法依次計算出 D(n-1) , D(n-2) , D(1) 的值.這樣,每個 D(i) 的值只計算一次,并在計算的同時把計算結(jié)果保存下來,程序如下：void D() int i,j;for( i=1;i=1;i-) for(j=i+1;j=n;j+) if (

14、x(j)dmax) dmax=d(i); xh=i; 由此我們出了最大攔截數(shù)的第一枚導(dǎo)彈的順序號 xh，即d(xh)為問題的解從而避免了有些子問題被重復(fù)計算的情況發(fā)生,提高了程序的效率.在實際應(yīng)用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動態(tài)規(guī)劃解決，也就是分治算法的思想。例2：傳球游戲（NOIP2008普及組第三題）【問題描述】上體育課的時候，小蠻的老師經(jīng)常帶著同學們一起做游戲。這次，老師帶著同學們一起做傳球游戲。游戲規(guī)則是這樣的：n個同學站成一個

15、圓圈，其中的一個同學手里拿著一個球，當老師吹哨子時開始傳球，每個同學可以把球傳給自己左右的兩個同學中的一個（左右任意），當老師再次吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學就是敗者，要給大家表演一個節(jié)目。聰明的小蠻提出一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了m次以后，又回到小蠻手里。兩種傳球的方法被視作不同的方法，當且僅當這兩種方法中，接到球的同學按接球順序組成的序列是不同的。比如有3個同學1號、2號、3號，并假設(shè)小蠻為1號，球傳了3次回到小蠻手里的方式有1-2-3-1和1-3-2-1，共2種?！据斎搿枯斎胛募all.in共一行，有兩個用空格隔開的整數(shù)

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

17、們分析出F1,0的解只與F1,1和Fn,1有關(guān)，而F1,1和Fn,1也是最優(yōu)問題解，因此，該問題符合最優(yōu)子結(jié)構(gòu)性質(zhì)。F(p,t)=1 (t=m，p=1)0 (t=m，p!=1)FRp,t+1+FLp,t+1 (1=p=n，0=tm)Rp：p右邊同學的編號Lp：p左邊同學的編號根據(jù)最優(yōu)性原理我們可以得到以下狀態(tài)轉(zhuǎn)移方程：通過以上分析，根據(jù)狀態(tài)轉(zhuǎn)移方程，運用記憶化搜索策略，采用自頂向下的過程可遞歸求出F1,0，程序如下：#include#include#define maxn 31/最大人數(shù)，編號從1n #define maxm 30/最大傳球次數(shù) long fmaxnmaxm;/表示傳了T次球以

18、后球在P號手里，包括在剩下的M-T次傳球中有多少種方法走到1 long m,n;void find(long p,long t) if(t=m)/傳了M次球了 if(p=1)/傳到了1 fpt=1; else/沒傳到1 fpt=0; return; if(fpt!=-1) return;/如果這個狀態(tài)搜到過了，沒必要再搜 fpt=0;/標記該狀態(tài)被搜過了 find(p%n+1,t+1);/搜把球傳給P右邊的同學的狀態(tài) fpt+=fp%n+1t+1; int p1=p-1; if(p1=0)p1=n; find(p1,t+1);/搜把球傳給P左邊的同學的狀態(tài) fpt+=fp1t+1;main()

19、 int i,j; /一開始所有狀態(tài)都沒到過 for(i=0;imaxn;i+) for(j=0;jmaxm;j+) fij=-1; scanf(%d%d,&n,&m); find(1,0); printf(%ld,f10);代入數(shù)據(jù)測算例：input：3 3F1,0=2F2,1=1F3,1=1F1,2=0F3,2=1F1,2=0F2,2=1F3,3=0F2,3=0F1,3=1F2,3=0F1,3=1F3,3=0數(shù)據(jù)模型如下： ：可以從記憶數(shù)組中直接獲??；：需搜索記憶的狀態(tài)；由于采用了記憶化搜索，處于不同位置的相同狀態(tài)不會被多次搜索，因此可以在O(mn)的時間復(fù)雜度內(nèi)完成任務(wù)，同樣避免了子問題被重復(fù)計算的情況。