算法合集之《動態(tài)規(guī)劃》

1、本資料由-大學生創(chuàng)業(yè)|創(chuàng)業(yè)|創(chuàng)業(yè)網(wǎng) 動態(tài)規(guī)劃關(guān)健字：階段 狀態(tài) 決策 函數(shù)遞推式 摘要： 動態(tài)規(guī)劃是解決多階段決策最優(yōu)化問題的一種思想方法。所謂“動態(tài)”，指的是在問題的多階段決策中，按某一順序，根據(jù)每一步所選決策的不同，將隨即引起狀態(tài)的轉(zhuǎn)移，最終在變化的狀態(tài)中產(chǎn)生一個決策序列。動態(tài)規(guī)劃就是為了使產(chǎn)生的決策序列在符合某種條件下達到最優(yōu)。動態(tài)規(guī)劃思想近來在各類型信息學競賽中頻繁出現(xiàn)，它的應(yīng)用也越來越受人重視。本文就是討論如何運用動態(tài)規(guī)劃的思想設(shè)計出有效的數(shù)學模型來解決問題一 動態(tài)規(guī)劃問題的數(shù)學描述 我們先來看一個簡單的多階段決策問題。 例1現(xiàn)有一張地圖，各結(jié)點代表城市，兩結(jié)點間連線代表道路，線上數(shù)

2、字表示城市間的距離。如圖1所示，試找出從結(jié)點1到結(jié)點10的最短路徑。 第一階段 第二階段 第三階段 第四階段 第五階段 圖1本問題的解決可采用一般的窮舉法，即把從結(jié)點1至結(jié)點10的所有道路列舉出來，計算其長度，再進行比較，找出最小的一條。雖然問題能解決，但采用這種方法，當結(jié)點數(shù)增加，其運算量將成指數(shù)級增長，故而效率是很低的。分析圖1可知，各結(jié)點的排列特征： (1) 可將各結(jié)點分為5個階段；(2) 每個階段上的結(jié)點只跟相鄰階段的結(jié)點相連，不會出現(xiàn)跨階段或同階段結(jié)點相連的情況，如不會出現(xiàn)結(jié)點1與結(jié)點4連、結(jié)點4與結(jié)點5連的情況。 (3) 除起點1和終點10外，其它各階段的結(jié)點既是上一階段的終點，又

3、是下一階段的起點。例如第三階段的結(jié)點4、5、6，它即是上一階段結(jié)點2、3中某結(jié)點的終點，又是下一階段結(jié)點7、8、9中某結(jié)點的起點。 根據(jù)如上特征，若對于第三階段的結(jié)點5，選擇1-2-5和1-3-5這兩條路徑，后者的費用要小于前者。那么考慮一下，假設(shè)在所求的結(jié)點1到結(jié)點10最短路徑中要經(jīng)過結(jié)點5，那我們在結(jié)點1到結(jié)點5之間會取那條路徑呢？顯然，無論從結(jié)點5出發(fā)以后的走法如何，前面選擇1-3-5這條路都總是會優(yōu)于1-2-5的。也就是說，當某階段結(jié)點一定時，后面各階段路線的發(fā)展不受這點以前各階段的影響。反之，到該點的最優(yōu)決策也不受該點以后的發(fā)展影響。由此，我們可以把原題所求分割成幾個小問題，從階段1

4、開始，往后依次求出結(jié)點1到階段2、3、4、5各結(jié)點的最短距離，最終得出答案。在計算過程中，到某階段上一結(jié)點的決策，只依賴于上一階段的計算結(jié)果，與其它無關(guān)。例如，已求得從結(jié)點1到結(jié)點5的最優(yōu)值是6，到結(jié)點6的最優(yōu)值是5，那么要求到下一階段的結(jié)點8的最優(yōu)值，只須比較min6+5,5+5即可。這樣，運用動態(tài)規(guī)劃思想大大節(jié)省了計算量。可以看出，動態(tài)規(guī)劃是解決此類多階段決策問題的一種有效方法。二 動態(tài)規(guī)劃中的主要概念，名詞術(shù)語 1階段：把問題分成幾個相互聯(lián)系的有順序的幾個環(huán)節(jié)，這些環(huán)節(jié)即稱為階段。 2 狀態(tài)：某一階段的出發(fā)位置稱為狀態(tài)。通常一個階段包含若干狀態(tài)。如圖1中，階段3就有三個狀態(tài)結(jié)點4、5、6

5、。 3 決策：從某階段的一個狀態(tài)演變到下一個階段某狀態(tài)的選擇。4策略：由開始到終點的全過程中，由每段決策組成的決策序列稱為全過程策略，簡稱策略。 5 狀態(tài)轉(zhuǎn)移方程：前一階段的終點就是后一階段的起點，前一階段的決策選擇導(dǎo)出了后一階段的狀態(tài)，這種關(guān)系描述了由k階段到k+1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。 6 目標函數(shù)與最優(yōu)化概念：目標函數(shù)是衡量多階段決策過程優(yōu)劣的準則。最優(yōu)化概念是在一定條件下找到一個途徑，經(jīng)過按題目具體性質(zhì)所確定的運算以后，使全過程的總效益達到最優(yōu)。三 運用動態(tài)規(guī)劃需符合的條件 任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同理，動態(tài)規(guī)劃也并不是萬能的。那么

6、使用動態(tài)規(guī)劃必須符合什么條件呢？必須滿足最優(yōu)化原理和無后效性。 1 最優(yōu)化原理 最優(yōu)化原理可這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀 圖2態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。 如圖2中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。這可用反證法證明：假設(shè)有另一路徑J是B到C的最優(yōu)路徑，則A到C的路線取I和J比I和J更優(yōu)，這與原名題矛盾。從而證明J必是B到C的最優(yōu)路徑。 最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。 2 無

7、后效性 “過去的步驟只能通過當前狀態(tài)影響未來的發(fā)展，當前的狀態(tài)是歷史的總結(jié)”。這條特征說明動態(tài)規(guī)劃只適用于解決當前決策與過去狀態(tài)無關(guān)的問題。狀態(tài)，出現(xiàn)在策略任何一個位置，它的地位相同，都可實施同樣策略，這就是無后效性的內(nèi)涵。 由上可知，最優(yōu)化原理，無后效性，是動態(tài)規(guī)劃必須符合的兩個條件。四 動態(tài)規(guī)劃的計算方法 對于一道題，怎樣具體運用動態(tài)規(guī)劃方法呢？（1） 首先，分析題意，考察此題是否滿足最優(yōu)化原理與無后效性兩個條件。（2） 接著，確定題中的階段，狀態(tài)，及約束條件。（3） 推導(dǎo)出各階段狀態(tài)間的函數(shù)基本方程，進行計算。 具體求解則有多種方法。 1 前向與后向動態(tài)規(guī)劃法 所謂前向與后向，指的是從起

8、點出發(fā)，層層遞推，直到終點，或從終點出發(fā)，逆向求解。這兩種方法本質(zhì)上是一樣的，具體解題時，可根據(jù)實際情況來選用。 例2 排隊買票 問題描述：一場演唱會即將舉行?，F(xiàn)有N（ON=200）個歌迷排隊買票，一個人買一張，而售票處規(guī)定，一個人每次最多只能買兩張票。假設(shè)第I位歌迷買一張票需要時間Ti（1=I=n），隊伍中相鄰的兩位歌迷（第j個人和第j+1個人）也可以由其中一個人買兩張票，而另一位就可以不用排隊了，則這兩位歌迷買兩張票的時間變?yōu)镽j，假如RjTj+Tj+1，則這樣做就可以縮短后面歌迷等待的時間，加快整個售票的進程?，F(xiàn)給出N，Tj和Rj，求使每個人都買到票的最短時間和方法。解決問題：本題的階段

9、十分明顯，只要按排隊的先后順序劃分即可。而買票的方式只有兩種，要么一人買一張，要么一人買兩張，整個過程呈線性排列。要使前I個人買票時間最短，只需考慮前I個人的買票方式，與隊列以后的人無關(guān)。而且顯而易見，在最優(yōu)策略中，任意m個連續(xù)的決策也肯定是最優(yōu)的。這樣，問題就符合了最優(yōu)化原理及無后效性，能運用動態(tài)規(guī)劃。那如何構(gòu)造函數(shù)遞推式呢？可以以到每個人為止所需的最短時間為狀態(tài)值，設(shè)為f（i），于是有f（i）=minf（i-1）+Ti，f（i-2）+Ri-1，起步時f（0）=0，f（1）=T1 。如此從前往后，只需遍歷一次即可。上面的分析是從前往后進行的。其實倒過來逆推也一樣。設(shè)f（I）表示當票賣到第I個

10、人時，最少還需多少時間才能賣完。則函數(shù)遞推式為f（I）=minf（I+1）+Ti，f（I+2）+Ri，從后往前逆推，起步時f（n）=Tn，f（n+1）=0 。采用前向還是后向動態(tài)規(guī)劃，要看實際情況而定，哪一種直觀、簡便，就運用哪一種。 2 具有隱含階段的問題（即階段不明顯） 動態(tài)規(guī)劃的一個重要環(huán)節(jié)是階段劃分，可有些題目無明顯階段，但也符合最優(yōu)化原理，怎么解決呢？下面來看一道例題。 例3 最小費用問題問題描述：已知從A到J的路線及費用如圖3，求從A到J的最小費用路線。 圖3 解決問題：本問題沒有明顯的階段劃分，各點間沒有一定的先后次序，不能按照最少步數(shù)來決定順序，如從A到D走捷徑需4，但A-C-

11、D只需3，更優(yōu)?？磥韴D中出現(xiàn)回路，不能實施動態(tài)規(guī)劃。其實不然。細想一下，從A到J的最優(yōu)策略，它每一部分也是最優(yōu)的（可以用前述的反證法來證明），換言之，本題也具有最優(yōu)化性質(zhì)，只是階段不明顯而已。對于這類問題，我們可以換個角度分析，構(gòu)造算法。比較一下前面所講的前向與后向動態(tài)規(guī)劃法，都是以某個狀態(tài)為終點，尋找到達次點的路徑，然后比較優(yōu)劣，確定此狀態(tài)最優(yōu)值。可是，本題階段不明顯，各狀態(tài)之間的道路會出現(xiàn)嵌套，故此法不能使用。變一下角度，每次都以某個狀態(tài)為起點，遍歷由它引申出去的路徑，等所有已知狀態(tài)都擴展完了，再來比較所有新狀態(tài)，把值最小的那個狀態(tài)確定下來，其它的不動。如圖3，先從A出發(fā)，找到3個結(jié)點B，

12、D，C，費用為F（B）=3，F(xiàn)（D）=4，F(xiàn)（C）=2。因為F（B），F(xiàn)（D）都大于F（C），那么可以確定：不可能再有路線從B或D出發(fā)到C，比A-C更優(yōu)。這樣F（C）的最優(yōu)值便確定了?？墒牵袥]有路線從C出發(fā)到B或D，比A-B或A-D更優(yōu)呢？還不清楚。繼續(xù)下去，因為A擴展完了，只有從C開始，得到A-C-D=3，A-C-F=3，于是F（D）的值被刷新了，等于3。現(xiàn)在，有F（B）=F（D）=F（F）=3，于是，三點的最優(yōu)值都確定下來了。然后以分別以三個點為起點，繼續(xù)找。以次類推，直到J點的最優(yōu)值確定為止。細心觀察，其實本題的隱含階段就是以各結(jié)點的最優(yōu)值的大小來劃分的，上述過程就是按最優(yōu)值從小到大前

13、向動態(tài)規(guī)劃。人們習慣上把此題歸入到圖論范疇中，并將上述方法稱為標號法。五 動態(tài)規(guī)劃的應(yīng)用 上文敘述了動態(tài)規(guī)劃的幾種解法，下面我們通過例題來加深了解。 例4 復(fù)制書稿（BOOKS） 問題描述：假設(shè)有M本書（編號為1，2，M），想將每本復(fù)制一份，M本書的頁數(shù)可能不同（分別是P1，P2，PM）。任務(wù)時將這M本書分給K個抄寫員（K=M，每本書只能分配給一個抄寫員進行復(fù)制，而每個抄寫員所分配到的書必須是連續(xù)順序的。意思是說，存在一個連續(xù)升序數(shù)列0=bob1b2<bk-1 <bk=m，這樣，第I號抄寫員得到的書稿是從bi-1+1到第bi本書。復(fù)制工作是同時開始進行的，并且每個抄寫員復(fù)制的速度都

14、是一樣的。所以，復(fù)制完所有書稿所需時間取決于分配得到最多工作的那個抄寫員的復(fù)制時間。試找一個最優(yōu)分配方案，使分配給每一個抄寫員的頁數(shù)的最大值盡可能?。ㄈ绱嬖诙鄠€最優(yōu)方案，只輸出其中一種）。解決問題：該題中M本書是順序排列的，K個抄寫員選擇數(shù)也是順序且連續(xù)的。不管以書的編號，還是以抄寫員標號作為參變量劃分階段，都符合策略的最優(yōu)化原理和無后效性。考慮到K=M，以抄寫員編號來劃分會方便些。設(shè)F（I，J）為前I個抄寫員復(fù)制前J本書的最小“頁數(shù)最大數(shù)”。于是便有F（I，J）=MIN F（I-1，V），T（V+1，J） （1=I=K，I=J=M-K+I，I-1=V=J-1。 其中T（V+1，J）表示從第V

15、+1本書到第J本書的頁數(shù)和。起步時F（1，1）=P1。觀察函數(shù)遞推式，發(fā)現(xiàn)F（I）階段只依賴于F（I-1）階段的狀態(tài)值，編程時可令數(shù)組F的范圍為（01,1M），便于縮小空間復(fù)雜度。 例5 多米諾骨牌（DOMINO）問題描述：有一種多米諾骨牌是平面的，其正面被分成上下兩部分，每一部分的表面或者為空，或者被標上1至6個點。現(xiàn)有一行排列在桌面上：頂行骨牌的點數(shù)之和為6+1+1+1=9；底行骨牌點數(shù)之和為1+5+3+2=11。頂行和底行的差值是2。這個差值是兩行點數(shù)之和的差的絕對值。每個多米諾骨牌都可以上下倒置轉(zhuǎn)換，即上部變?yōu)橄虏?，下部變?yōu)樯喜俊，F(xiàn)在的任務(wù)是，以最少的翻轉(zhuǎn)次數(shù)，使得頂行和底行之間的差值

16、最小。對于上面這個例子，我們只需翻轉(zhuǎn)最后一個骨牌，就可以使得頂行和底行的差值為0，所以例子的答案為1。解決問題：例子的上下部分之差是6+1+1+1-（1+5+3+2）=（6-1）+（1-5）+（1-3）+（1-2）=-2，而翻轉(zhuǎn)最后一個骨牌后，上下之差變?yōu)椋?-1）+（1-5）+（1-3）+（2-1）=0。由此看出，一個骨牌對翻轉(zhuǎn)策略造成影響的是上下兩數(shù)之差，骨牌上的數(shù)則是次要的了。這么一來，便把骨牌的放置狀態(tài)由8個數(shù)字變?yōu)?個： 5 -4 -2 -1，翻轉(zhuǎn)時只需取該位數(shù)字的相反數(shù)就行了。在本題中，因為各骨牌的翻轉(zhuǎn)順序沒有限定，所以不能按骨牌編號作為階段來劃分。怎么辦呢？考慮到隱含階段類型的問

17、題可以按狀態(tài)最優(yōu)值的大小來劃分階段。于是，我們以骨牌序列上下兩部分的差值I作為狀態(tài)，把達到這一狀態(tài)的翻轉(zhuǎn)步數(shù)作為狀態(tài)值，記為f（I）。便有f（I）=minf（I+j）+1 （-12=j<=12,j為偶數(shù)，且要求當前狀態(tài)有差值為j/2的骨牌）。這里，I不是無限增大或減小，其范圍取決于初始骨牌序列的數(shù)字差的和的大小。具體動態(tài)規(guī)劃時，如例題，我們以f（-2）=0起步，根據(jù)骨牌狀態(tài)，進行一次翻轉(zhuǎn)，可得到f（-12）=1，f（6）=1，f（2）=1，f（0）=1，由于出現(xiàn)了f（0），因此程序便可以結(jié)束，否則將根據(jù)四個新狀態(tài)繼續(xù)擴展，直至出現(xiàn)f（0）或者無法生成新狀態(tài)為止。注意：在各狀態(tài)，除記錄最少

18、步數(shù)外，還需記錄到達這一狀態(tài)時各骨牌的放置情況；而當?shù)竭_某一狀態(tài)發(fā)現(xiàn)已記錄有一種翻轉(zhuǎn)策略時，則取步數(shù)較小的一種。六 小結(jié) 動態(tài)規(guī)劃是一種高效算法。若能成功運用，必會使程序效率，無論時間還是空間，都有著質(zhì)的飛躍。因此，我們視其為算法思想中的一項重要內(nèi)容，有熟練掌握，深入研究的必要。希望本文能給大家一點啟發(fā)。附錄例4：輸入格式： 文件的第一行是兩個整數(shù)m和k (1=k=m=500)。第二行有m個整數(shù)P1，P2，Pm，這m個整數(shù)均為正整數(shù)且都不超過1000000。每兩個整數(shù)之間用空格分開。輸出格式：文件有k行，每行有兩個正整數(shù)。整數(shù)之間用空格分開。第I行的兩個整數(shù)ai和bi，表示第I號抄寫員所分配得

19、到的書稿的起始編號與終止編號。程序如下：program books;type tp=array1.500 of integer; tc=array1.500 of longint;var c:array1.500 of tp; 記錄路徑f:array0.1 of tc;狀態(tài)值t:tc;書本頁數(shù)和cc:tp;鏈接路徑 i,j,v,k,m,x,y,min,p1,p2:longint; f1,f2:text;procedure init;輸入部分begin assign(f1,'books.dat'); reset(f1); assign(f2,'books.out'

20、); rewrite(f2); readln(f1,m,k); if k=1 then begin writeln(f2,1,' ',m); close(f2); halt; end; 當k=1時,作特殊處理 for i:=1 to m do begin read(f1,j); if i=1 then t1:=j else ti:=ti-1+j; 累加頁數(shù) end; for i:=1 to k do new(ci);end;procedure main;主過程begin p1:=1;f1:=t; 起步狀態(tài) for i:=2 to k-1 do 利用函數(shù)遞推式計算 begin p

21、2:=p1;p1:=1-p2; for j:=i to m-k+i do begin min:=maxlongint;y:=0; for v:=i-1 to j-1 do begin if fp2,v>tj-tv then x:=fp2,v else x:=tj-tv; if x<min then begin min:=x;y:=v;end; end; fp1,j:=min; cij:=y; end; end; p2:=p1;p1:=1-p2; min:=maxlongint;y:=0; for i:=k-1 to m-1 do begin if fp2,i>tm-ti th

22、en x:=fp2,i else x:=tm-ti; if x<min then begin min:=x;y:=i;end; end; 最后找出最優(yōu)分配方案 for i:=k-1 downto 1 do begin cci:=y; y:=ciy; end; 鏈接路徑 writeln(f2,1,' ',cc1); for j:=2 to k-1 do writeln(f2,ccj-1+1,' ',ccj); writeln(f2,cck-1+1,' ',m); close(f2); 打印end;begin init; main;end.例5

23、：輸入格式：文件的第一行是一個整數(shù)n（1=n=1000，表示有n個多米諾骨牌在桌面上排成一行。接下來共有n行，每行包含兩個整數(shù)a、b（0=a、b=6，中間用空格分開。第I+1行的a、b分別表示第I個多米諾骨牌的上部與下部的點數(shù)（0表示空）。輸出格式：只有一個整數(shù)在文件的第一行。這個整數(shù)表示翻動骨牌的最少次數(shù)，從而使得頂行和底行的差值最小。程序如下：program domino;type tp=array1.6 of integer;var t:array1.6000 of tp; 記錄骨牌擺放狀態(tài)f:array-6000.6000 of integer;記錄達到某個差值的最少步數(shù)l:array

24、1.6000 of integer;擴展隊列tt:tp; i,j,n,m,x,y,ft,re:integer; f1,f2:text;procedure init;程序初始化begin assign(f1,'domino.dat'); reset(f1); assign(f2,'domino.out'); rewrite(f2); m:=0; ft:=0;re:=1;new(t1); fillchar(t1,sizeof(t1),0); fillchar(f,sizeof(f),0); fillchar(tt,sizeof(tt),0); readln(f1,n); for i:=1 to n do begin readln(f1,x,y); if x<>y then begin x:=x-y; inc(m,x); inc(ttabs(x); if x>0 then inc(t1x); end; end; if m=0 then begin writeln(f2,0); close(f2); halt; end; 處理步數(shù)為零的情況 l1:=m; fm:=1;end;procedure main;主過程begin repeatfo