動態(tài)規(guī)劃程序設(shè)計

1、動態(tài)規(guī)劃程序設(shè)計青島二中 04 級李辰 動態(tài)規(guī)劃是信息學(xué)競賽中的一種利用擴(kuò)大空間占用而縮短 時間消耗的設(shè)計方法?，F(xiàn)今的幾乎所有程序設(shè)計競賽中，隨著空間的限制逐漸減 小，時間已經(jīng)成為極重要的衡量程序優(yōu)劣的標(biāo)準(zhǔn)。因此，動態(tài)規(guī) 劃以其靈活性和高效性逐漸為大家的所喜愛。 但是由于其概念比 較抽象，對剛接觸的人來講理解起來并不容易。 本文將結(jié)合例題， 系統(tǒng)細(xì)致地解釋動態(tài)規(guī)劃， 同時介紹一些在使用動態(tài)規(guī)劃過程中 常運(yùn)用到的技巧。相信所有程序設(shè)計者對搜索算法很熟悉， 而在搜索能解決的 題目中， 有很大一部分題能利用動態(tài)規(guī)劃解決， 而其效率是搜索 所無法比擬的。這類題目的一大特點(diǎn)是在用搜索解決的過程中， 不斷

2、重復(fù)了一項已經(jīng)進(jìn)行過的工作。 動態(tài)規(guī)劃之所以能極大地提 高解題效率，是因?yàn)樗鼉Υ嫦铝诉@些已經(jīng)進(jìn)行過得工作的結(jié)果， 下次使用時只需將結(jié)果調(diào)出。 這也是為什么現(xiàn)在很多人把動態(tài)規(guī) 劃叫做：記憶化搜索。下面這道題就是一個從搜索轉(zhuǎn)到記憶化搜索動態(tài)規(guī)劃 的很好例子。一個數(shù)字三角形 , 形式如下 :12 34 5 67 8 9 10找出從第一層到最后一層的一條路 , 使得所經(jīng)過的權(quán)值之和 最大 . 從每層到下面一層只能向左下或右下走。讓我們來模擬一下深度優(yōu)先搜索的過程（走法選擇先選左 下，后選右下， <表示無法深入搜索，回溯） ：1 2 4 7 < 8 < < 5 8 < 9

3、< < < 3 5 8 < 9 < < 6 9 < 10< < < < 不計回溯總共需要 15 步（因?yàn)槊繉拥较乱粚佣加星抑?有 2 種選擇，所以理論上三角形有 n 層就需要 2 的 n 次方 -1 步）仔細(xì)觀察不難發(fā)現(xiàn)， 想到達(dá)每層中除了最左邊和最右邊的數(shù) 字都只有兩種選擇（左上或右上） 。達(dá)任意數(shù)字時的最大值是該 數(shù)字 +到達(dá)左上或右上數(shù)字時的最大值中的較大值。這樣寫比較 難懂，讓我們用數(shù)學(xué)語言解釋。不妨設(shè)va , b表示第a行第b列的數(shù)字。fa ， b 表示從頂端到第 a 行第 b 列的數(shù)字得到的最大值。max（a, b）

4、表示a, b中較大的那一個。則 fa ， b=max（ fa-1 ， b-1 ， fa-1 ， b ）+va ， b這樣就抽象出了動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程，我們只需要找出實(shí)現(xiàn)動態(tài)方程的循環(huán)方法，該循環(huán)方法要保證在計算到當(dāng)前所求值 時方程右邊的元素已經(jīng)全部算出。即在計算到fa，b時保證已經(jīng)計算出了 fa-1 ，b-1和fa-1 ，b （va，b為已知值）此題的循環(huán)方法較簡單，設(shè)i表示第i行，j表示第j列雙 重循環(huán)即可實(shí)現(xiàn)。For i:=2 to n doFor j:=1 to i do （第i行有i個數(shù)字）fi，j=max（ fi-1，j-1，fi-1 ，j）+vi，j（在三角形兩邊需要簡單地特殊處

5、理一下，例如把fi,0和fi,i+1 均賦值為0等很多方法都可以）若三角形有n層則此算法的理論計算量為n的平方。理論效率N=10N=100N=1000搜索2的n次方1024 次約10的31次方次約10的300次方動態(tài)規(guī)劃N的平方100次10000 次10的6次方按一臺計算機(jī)每秒運(yùn)算1億次來看，即使n=10000用動態(tài)規(guī) 劃也可在1秒鐘左右出結(jié)果。而搜索的時間代價已經(jīng)大得無法接 受。相信通過上面的例子大家已經(jīng)對動態(tài)規(guī)劃有了一定認(rèn)識。但動態(tài)規(guī)劃的思想絕不僅僅是“記憶化搜索”這幾個字能概括的，動態(tài)規(guī)劃還有一個重要的特點(diǎn)是它的目標(biāo)狀態(tài)是由前面一個狀態(tài)得到的，而前面一個狀態(tài)又由再前面一個狀態(tài)得到，有點(diǎn)類

6、似遞推或遞歸，但又不像遞推和遞歸那樣一步步按部就班，目的明確。動態(tài)規(guī)劃方程運(yùn)算結(jié)束后， 我們會發(fā)現(xiàn)除了從初始狀態(tài)到目 標(biāo)狀態(tài)的各個狀態(tài)外，我們還對許多其他“多余”的狀態(tài)進(jìn)行了 處理，但在動態(tài)規(guī)劃方程運(yùn)算結(jié)束之前我們并不知道哪些狀態(tài)無 法達(dá)到目標(biāo)狀態(tài)，因此無從取舍。拿上面的題舉例子，我們不但 找到了到達(dá)10的最大權(quán)值和走法，我們還找到了到達(dá)任何一個 頂點(diǎn)的最大權(quán)值和走法，這雖然看上去是一種浪費(fèi)， 但其實(shí)我們 不得不做，因?yàn)樵诮Y(jié)果得出前我們不知道哪個狀態(tài)是真正必要 的，所以所有狀態(tài)都要計算出。 并且往往前一個狀態(tài)都是此時的 局部的最優(yōu)解，后一個狀態(tài)則是由這個局部最優(yōu)解得到的大一點(diǎn) 的局部的最優(yōu)解，

7、直到得出目標(biāo)狀態(tài)，即全局最優(yōu)解。因此可以說動態(tài)規(guī)劃具有最優(yōu)子結(jié)構(gòu)特性。讓我們再看看另一道經(jīng)典題目。有一個容積為n的袋子，又知道m(xù)個貨物各自的體積和價值， 要求你將貨物裝到袋子里，使袋子中的貨物價值和最大。假如袋子的容積為10，現(xiàn)有貨物貨物名ABCDE體積44323價值56423很顯然，最優(yōu)解為裝B,C,E，價值為13。這個例子也說明并不是不斷將價值最大的貨物放進(jìn)袋子就能得到最優(yōu)解。其他與之相似的各類貪心法均可證明是錯誤的我們的目的是要 “記憶化搜索” 出 x 個貨物， 使它們的體積 和小于n價值和盡可能大。與上一道題目相類似，如果在放入 一些貨物后， 再放入一個貨物后能得到最優(yōu)解， 那么在放入

8、這個 貨物前， 所有貨物無論怎么搭配， 也不可能出現(xiàn)體積和小于或等 于此時袋中物品體積和而價值和大于此時袋中貨物的價值和的 情況。即無論貨物怎么搭配裝進(jìn)袋子，比此時的價值和大，比此 時的體積和小這兩種情況不可能同時滿足， 這就可以稱作是最優(yōu) 子結(jié)構(gòu)了。由此得出狀態(tài)轉(zhuǎn)移方程 :設(shè) fi,x 表示前 i 個貨物，用體積等于 x 時的袋子裝能得 到的最大價值（最優(yōu)子結(jié)構(gòu)的體現(xiàn)） ， wi 表示第 i 個貨物的體 積， vi 表示第 i 個貨物的價值。fi ， j=max（fi-1 ， j-wi+vi, fi-1,j）（i 表示當(dāng)前搜索到第 i 個貨物， j 表示袋中體積和等于 j 時的情況 ,fi-

9、1,j-wi+vi表示放 i 貨物時的最大價值，fi-1,j 表示不放 i 貨物時的最大價值）由于 j 的循環(huán)是建立在已經(jīng)確定 i 的基礎(chǔ)上，因此 j 的循環(huán) 在 i 循環(huán)的內(nèi)部。因此具體實(shí)現(xiàn)方法為：for i ： =1 to n dofor j:=1 to m do beginfi,j:=fi-1,j;if (j>=wi) thenif (fi-1,j-wi+vi>fi,j) thenfi,j:=fi-1,j-wi+vi;end;這里還有些細(xì)節(jié)要處理，比如要預(yù)先將 f 數(shù)組清零等等 .寫到這里我想向大家介紹一種減少空間使用的辦法， 若用二 維數(shù)組表示狀態(tài)（即狀態(tài)表示為 fi,j

10、的形式），則我們不妨稱 fi 為一個狀態(tài)層， 每個層中含有若干個狀態(tài)。 細(xì)心觀察不難發(fā) 現(xiàn)，這道貨物裝袋題與上面一道數(shù)字三角形的程序?qū)崿F(xiàn)中， 要推 得下面一個狀態(tài)層只需要當(dāng)前這個狀態(tài)層而不需要當(dāng)前狀態(tài)層 之前層的狀態(tài)，即要推得 fi ，只需要 fi-1 。這樣說來求出 最優(yōu)解我們只需要兩個線性數(shù)組， 一個記錄前面的狀態(tài)層另一個 記錄后面的狀態(tài)層。以貨物裝袋為例，再來看一道全國信息學(xué)奧林匹克原題： 某國為了防御敵國的 導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。 但是這種導(dǎo)彈攔截系統(tǒng) 有 一個缺陷： 雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度， 但是以后 每一發(fā)炮彈都不能高 于前一發(fā)的高度。 某天， 雷達(dá)捕捉到

11、敵國 的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以 只有一套系統(tǒng)， 因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來的高度， 計 算這套系統(tǒng)最多能攔截多少導(dǎo)彈。設(shè) hi 表示第 i 個導(dǎo)彈的高度， 再通過預(yù)處理得到導(dǎo)彈數(shù) n 按先前的思路進(jìn)行分析，假設(shè) fi 表示到第 i 個導(dǎo)彈時所 能擊中的最大導(dǎo)彈數(shù)，但是發(fā)現(xiàn)接下來沒法寫出狀態(tài)轉(zhuǎn)移方程， 因?yàn)樵谇?fi 時還有一個條件是要考慮現(xiàn)在要打的導(dǎo)彈高度不 能超過最近打下的一個導(dǎo)彈的高度。 所以顯然我們的狀態(tài)轉(zhuǎn)移方 程中要考慮到這一點(diǎn)。因此我們再次假設(shè) fi 表示在打下第 i 個導(dǎo)彈的前提下所 能打下的導(dǎo)彈數(shù)最大值。因?yàn)槲覀儗⒋蛳碌?i 個導(dǎo)彈列為前提，

12、 因此也就確定了 fi 這個狀態(tài)打的下一個導(dǎo)彈高度只需要 <=hi 。而且打下第 i 個導(dǎo)彈數(shù)最大的情況一定是打下前面某個 導(dǎo)彈最大數(shù)情況 , 再打下第 i 個導(dǎo)彈，或者該系統(tǒng)打下的第一個 導(dǎo)彈就是 i (最優(yōu)子結(jié)構(gòu)明顯的體現(xiàn)) 。將 f 數(shù)組的所有元素賦值為 1，就是說當(dāng)以該導(dǎo)彈為第一個 打下的導(dǎo)彈時打下了 1 個導(dǎo)彈。For i:=2 to n doFor j:=1 to i-1 doif (hi<=hj) thenfi:=max(fi,fj+1)最后要線性掃描一下 f 數(shù)組，找到其中的最大值。 (不能簡 單的將 fn 定為答案，因?yàn)樽顑?yōu)解的情況未必會打下最后一顆 導(dǎo)彈)讓我們

13、再來看看這道較上面幾道相對另類的題。最長公共子串：已知兩個字符串， 要求求出它們最長的公共子串的長度 （子 串中的每個字符都能在兩個原串中找到，而且每個字符的順 序和原串中的順序一致，子串可不連續(xù)） 。例如： abbbdcdcd 和 abcdaabd 的最長公共子串是 abcdd, 其 長度為 5。這道題看上去很棘手， 怎么做？最直接的方法， 從長到短枚 舉其中一個字符串的所有子串， 在另一個字符串中一一比對， 直 到在另一個字符串中找到一個和枚舉的子串相符的子串， 那么這 個子串的長度即為所求答案。假設(shè)兩個字符串長度均為n,枚舉子串時間復(fù)雜度為 2 的 n 次方，在另一個字符串中比對是否有相

14、 符子串的復(fù)雜度為 n*n, 所以理論復(fù)雜度為 n*n* （2 的 n 次方）， 用這種方法只能保證當(dāng) n 小于 20 時在 1 秒內(nèi)出結(jié)果。很明顯這 不是我們想要的效率。讓我們來觀察一下這道題能否用動態(tài)規(guī)劃解決， 試著利用最 優(yōu)子結(jié)構(gòu)的思想分析后得到：設(shè)兩個子串分別為串1和串 2，若串 1 和串 2末尾字母相同則所求解即串 1 和串 2 分別去掉末尾字 母后的最長公共子串長度 +1，否則所求解即串 1 去掉末尾字母后 和串 2的最長公共子串長度或串 2去掉末尾字母后和串 1的最長 公共子串長度中較大的一個。 因?yàn)槿サ裟┪沧帜傅淖址挚梢?看成一個新字符串， 這樣就具有了最優(yōu)子結(jié)構(gòu)， 但是因

15、為遞歸的 思想在程序中實(shí)現(xiàn)起來編寫難度和時間復(fù)雜度都比遞推大， 而且 這道題遞推的狀態(tài)轉(zhuǎn)移方法也比較簡單， 因此我們就用遞推來實(shí) 現(xiàn)。用數(shù)學(xué)語言表示一下，不妨設(shè)，a1,a2分別表示2個字符串， fi,j 表示al字符串前i個字符與a2字符串前j個字符的最長 公共子串長度， l1,l2 分別表示 a1,a2 字符串的長度。動歸的實(shí)現(xiàn)方法：For i:=1 to l1 doFor j:=1 to l2 doIf a1i=a2j then fi,j:=fi-1,j-1+1;Else fi,j:=max（fi-1,j,fi,j-1）這樣時間復(fù)雜度 n*n 的程序可以接受 2個長度為 1 0000的字

16、符串，幾乎不需要預(yù)處理（ fi,j 中 i,j 的下界應(yīng)為 0，數(shù)組清 零）編寫起來也明顯比搜索簡單得多， 看來動態(tài)規(guī)劃確實(shí)是程序 設(shè)計者一項利器。讓我們最后看看一道題，Tom的煩惱，希望在看完上面文字 后，讀者能嘗試著自主完成此題。Tom 是一個非常有創(chuàng)業(yè)精神的人，由于大學(xué)學(xué)的是汽車制造 專業(yè)，所以畢業(yè)后他用有限的資金開了一家汽車零件加工廠， 專 門為汽車制造商制造零件。由于資金有限， 他只能先購買一臺加 工機(jī)器。 現(xiàn)在他卻遇到了麻煩，多家汽車制造商需要他加工一些 不同零件（由于廠家和零件不同，所以給的加工費(fèi)也不同） ，而 且不同廠家對于不同零件的加工時間要求不同 （有些加工時間要 求甚至是沖突的，但開始和結(jié)束時間相同不算沖突）。Tom當(dāng)然希 望能把所有的零件都加工完，以得到更多的加工費(fèi)， 但當(dāng)一些零 件的加工時間要求有沖突時， 在某個時間內(nèi)他只能選擇某種零件 加工（因?yàn)樗挥幸慌_機(jī)器） ，為了賺得盡量多的加工費(fèi)， Tom 不知如何進(jìn)行取舍。設(shè)有 n 個廠家，每個廠家要求的起始時間 si, 結(jié)束時間 ei ，加工費(fèi) vi 。讀者已經(jīng)有思路了嗎？讓我們看看分析。做這道題， 切入點(diǎn)就在于找出最優(yōu)子結(jié)構(gòu)。 先將廠家的任務(wù) 以結(jié)束時間從小到大排序。設(shè) fx 為到達(dá)第 x 時間時能獲得的 最大利潤 ,i 為第 i 個廠家的任務(wù)。因?yàn)橐呀?jīng)將任務(wù)以結(jié)束時間 排列，而