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

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

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

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

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

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

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

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

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

10、很容易證明）.也就是說(shuō)，在當(dāng)前狀態(tài)s<x1下，問(wèn)題的最優(yōu)解Y所包含的子問(wèn)題（序列X1）的解（序列Y1）也是最優(yōu)的.這就是攔截導(dǎo)彈問(wèn)題的最優(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)彈之后飛來(lái)的導(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ù)以上分析，可歸納出問(wèn)題的動(dòng)態(tài)規(guī)劃遞歸方程為：11(i

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

12、程序如下：intD(inti)intj,max=0;if(i=n)|(min(x,i,n)=xi)/min(x,i,n)返回?cái)?shù)組x在下標(biāo)in之間的最小值return1;elsefor(j=i+1;j<=n;j+)if(xj<=xi)if(D(j)+1>max)max=D(j)+1;returnmax;)從這個(gè)程序的遞歸模型中可以看出，會(huì)有大量的子問(wèn)題被重復(fù)計(jì)算.比如在調(diào)用遞歸函數(shù)計(jì)算D(1)的時(shí)候，可能需要先計(jì)算D(5)的值；之后在分別調(diào)用遞歸函數(shù)計(jì)算D(2),D(3),D(4)的時(shí)候，都有可能需要先計(jì)算D(5)的值.如此一來(lái),在整個(gè)問(wèn)題的求解過(guò)程中，D(5)可能會(huì)被重復(fù)計(jì)算

13、很多次，從而造成了冗余，降低了程序的效率.其實(shí),通過(guò)以上分析，我們已經(jīng)知道：D(n)=1.如果將n作為階段對(duì)問(wèn)題進(jìn)行劃分，根據(jù)問(wèn)題的動(dòng)態(tài)規(guī)劃遞歸方程，我們可以采用自底向上的方法依次計(jì)算出D(n-1),D(n-2),D(1)的值.這樣，每個(gè)D(i)的值只計(jì)算一次，并在計(jì)算的同時(shí)把計(jì)算結(jié)果保存下來(lái)，程序如下：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;）由此我們

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

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

16、;=n<=30,1<=m<=30）o【輸出】輸出文件ball.out共一行，有一個(gè)整數(shù)，表示符合題意的方法數(shù)?！据斎胼敵鰳永縝all.in33ball.out2【限制】40%的數(shù)據(jù)滿足：3<=n<=30,1<=m<=20100%的數(shù)據(jù)滿足：3<=n<=30,1<=m<=30解決思路：給n個(gè)同學(xué)從1n編號(hào)，設(shè)狀態(tài)Fp,t表示傳了t次球后，球在p手中，在剩下的m-t次傳球中共有多少種方案到達(dá)1,由于在問(wèn)題的求解中，球是從1號(hào)開(kāi)始傳，并最后回到1號(hào)，顯然我們所求的目標(biāo)狀態(tài)就是是F1,0o由于球只能傳遞給左右的兩個(gè)同學(xué)，也只能通過(guò)左右

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

18、emaxn31最大人數(shù)，編號(hào)從1n#definemaxm30最大傳球次數(shù)longfmaxnmaxm;/表示傳了T次球以后球在P號(hào)手里，包括在剩下的M-T次傳球中有多少種方法走到1longm,n;voidfind(longp,longt)if(t=m)傳了M次球了if(p=1)/傳到了1fpt=1;else/沒(méi)傳到1fpt=0;return;if(fpt!=-1)return;/如果這個(gè)狀態(tài)搜到過(guò)了，沒(méi)必要再搜fpt=0;/標(biāo)記該狀態(tài)被搜過(guò)了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;一開(kāi)始所有狀態(tài)都沒(méi)到過(guò)for(i=0;i<maxn;i+)for(j=0;j<maxm;j+)fij=-1;scanf("%d%d",&n,&m);find(1,0);代入數(shù)據(jù)測(cè)算例：input:33數(shù)據(jù)模型如下：_:可以從記憶數(shù)組中直接獲?。欢盒杷阉饔洃浀臓顟B(tài)；由于采用了記憶化搜索，處于不同位置的相同狀態(tài)不會(huì)被多次搜索，因此可以在O(mxn)的時(shí)間復(fù)雜度內(nèi)完成任務(wù)，同樣避免了子問(wèn)題被重復(fù)計(jì)算的情況。由此可