動(dòng)態(tài)規(guī)劃(普及組-吳建鋒)

1、動(dòng)態(tài)規(guī)劃（普及組）紹興柯橋中學(xué)吳建鋒認(rèn)識(shí)動(dòng)態(tài)規(guī)劃n動(dòng)態(tài)規(guī)劃在運(yùn)籌學(xué)等領(lǐng)域都得到很大的運(yùn)用，它是求解最優(yōu)化分階段決策問(wèn)題的一種數(shù)學(xué)方法，大約產(chǎn)生于50年代。1951年美國(guó)數(shù)學(xué)家Bellman等人根據(jù)一類(lèi)多階段決策問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換為一系列互相聯(lián)系的單階段問(wèn)題，然后逐個(gè)加以解決。與此同時(shí)，他提出了解決這類(lèi)問(wèn)題的“最優(yōu)性原理”，研究了許多實(shí)際問(wèn)題，從而創(chuàng)建了解決最優(yōu)化問(wèn)題的一種新的方法動(dòng)態(tài)規(guī)劃。 多階段決策過(guò)程123n“動(dòng)態(tài)”的內(nèi)涵n在分階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與時(shí)間有關(guān)的，決策依賴(lài)于當(dāng)前的狀態(tài)，又隨即引起狀態(tài)的改變（轉(zhuǎn)移），一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)

2、的，所以有“動(dòng)態(tài)”的含義。因此，把處理它的方法稱(chēng)為動(dòng)態(tài)規(guī)劃方法。 問(wèn)題1：求最短路徑長(zhǎng)度n假如有下圖所示的交通示意圖，有向邊上的數(shù)值表示邊的長(zhǎng)度，求A到D的最短路徑的長(zhǎng)度 。ABCD13192815解法1：從初始階段出發(fā)的順推求解n1、用fi表示A到結(jié)點(diǎn)i的最短距離 n2、我們可以求得fA=13，fB19 （第一階段）n3、第二階段求解過(guò)程如下：nfB+28=41 fD的候選最優(yōu)解nfC+15=34 fD的候選最優(yōu)解 n4、保存較優(yōu)解：fD=minfB+28,fC+15 解法2：目標(biāo)階段出發(fā)的逆推求解n1、如果用fi表示編號(hào)為i的結(jié)點(diǎn)到終點(diǎn)d的最短距離，那么動(dòng)態(tài)規(guī)劃分階段求解的過(guò)程如下所示：

3、n（1）fD:=0 初始化n（2）fB:=28+fD; fC:=15+fD 第一階段求解n（3）fA:=min13+fB,19+fC 狀態(tài)轉(zhuǎn)移方程的體現(xiàn)，第二階段求解什么叫狀態(tài)轉(zhuǎn)移方程n對(duì)于當(dāng)前階段的某個(gè)狀態(tài)，必定有有上個(gè)階段的子問(wèn)題的某一批狀態(tài)通過(guò)對(duì)應(yīng)的決策變換而來(lái)，這些子問(wèn)題的一批狀態(tài)通過(guò)對(duì)應(yīng)的決策應(yīng)用，就導(dǎo)致了狀態(tài)轉(zhuǎn)移，新的狀態(tài)就是當(dāng)前階段的某個(gè)狀態(tài)。由于這個(gè)新?tīng)顟B(tài)的子狀態(tài)可能不止一個(gè)，所以決策后的對(duì)應(yīng)局部解也可能不止一個(gè)，在這些解中取一個(gè)最優(yōu)解，就是當(dāng)前階段當(dāng)前狀態(tài)的最優(yōu)解，這個(gè)求最優(yōu)解的過(guò)程可用一個(gè)表達(dá)式來(lái)描述，這個(gè)表達(dá)式就是狀態(tài)轉(zhuǎn)移方程。 狀態(tài)轉(zhuǎn)移方程應(yīng)用舉例n在下列交通路線中，求

4、節(jié)點(diǎn)1到節(jié)點(diǎn)10 的最短路徑的長(zhǎng)度。14326598710132191517324527111381916251120分階段決策的手工計(jì)算n第一階段：nf2=f1+13=13;f3=f1+21=21;f4=f1+9=9n第二階段：nf5=minf2+15,f3+17,f4+24=28;nf6=minf2+3,f3+5,f4+27=16n第三階段：nf7=minf5+11,f6+8=24;nf8=minf5+13,f6+19=35;nf9=minf6+16=32n 目標(biāo)階段求解n第四階段：nf10=minf7+25,f8+11,f9+20=46具體化的狀態(tài)轉(zhuǎn)移方程n1、f5=minfj+x,，f

5、6=minfk+y, n2、fj+x中的fj就是上階段子問(wèn)題各狀態(tài)的最優(yōu)解 ；而x則是某個(gè)子狀態(tài)轉(zhuǎn)移到當(dāng)前狀態(tài)產(chǎn)生的決策效應(yīng)（或者是代價(jià)）一般化的狀態(tài)轉(zhuǎn)移方程n實(shí)際編程實(shí)現(xiàn)時(shí)，狀態(tài)轉(zhuǎn)移方程往往是一個(gè)通用計(jì)算式，在這個(gè)通用計(jì)算式中往往會(huì)包含各種子狀態(tài)、子狀態(tài)對(duì)應(yīng)子問(wèn)題的最優(yōu)解、決策等參數(shù)。 動(dòng)態(tài)規(guī)劃的算法設(shè)計(jì)n如果用i表示當(dāng)前需求解的階段號(hào)（有時(shí)為了描述的方便，i也可表示當(dāng)前階段的前一個(gè)階段），j表示當(dāng)前階段各個(gè)狀態(tài)（或者說(shuō)是階段的各個(gè)節(jié)點(diǎn)編號(hào)），k表示前一階段各個(gè)子狀態(tài)能選擇的策略，用fI,j表示起點(diǎn)1到第i階段編號(hào)為j的結(jié)點(diǎn)（也可理解為狀態(tài)）的最短距離，那么上面問(wèn)題用動(dòng)態(tài)規(guī)劃求解的大致程序結(jié)

6、構(gòu)如下： n窮舉所有的階段（for i:=1 to 4 do） n 窮舉當(dāng)前階段i所有可能的狀態(tài)jn 窮舉j狀態(tài)所有對(duì)應(yīng)的子狀態(tài)的所有可選擇的策略kn FI,j:=minfi-1,j1+xj1,k | j1表示狀態(tài)j所有可能的子狀態(tài)程序代碼實(shí)現(xiàn)n輸入數(shù)據(jù)：n2 3 4 0n5 6 0n7 8 9 0n10 0n0 13 21 9 maxint maxint maxint maxint maxint maxintnmaxint 0 maxint maxint 15 3 maxint maxint maxint maxintnmaxint maxint 0 maxint 17 5 maxint m

7、axint maxint maxintnmaxint maxint maxint 0 24 27 maxint maxint maxint maxintn數(shù)據(jù)結(jié)構(gòu)nAI,j=k表示第i階段的第j個(gè)決策點(diǎn)（后繼節(jié)點(diǎn)）是k；nDI,j=k表示i和j節(jié)點(diǎn)之間的直接聯(lián)邊長(zhǎng)度是k，如果是maxint則表示沒(méi)有直接聯(lián)邊。如果是0則表示節(jié)點(diǎn)本身。程序框架nfor i:=1 to 4 donbeginn j:=1;n repeatn j2:=aI,j;n k:=1;n repeatn j1:=ai-1,k;n if dj1,j2maxint then fI,j2:=minfI,j2,fi-1,j1+dj1,j

8、2n inc(k);n until ai-1,k=0;n inc(j);n until aI,j=0;nend;一些關(guān)鍵的要素n1、階段n每個(gè)階段的處理是相同的。n2、狀態(tài)n每個(gè)抽象化的節(jié)點(diǎn)所共有的特性值。n3、決策n所選擇的處理。分析動(dòng)態(tài)規(guī)劃n1、何時(shí)可考慮動(dòng)態(tài)規(guī)劃n2、階段、狀態(tài)、決策如何提煉n3、如何抽象出狀態(tài)轉(zhuǎn)移方程問(wèn)題2：數(shù)字三角形n下圖所示為一個(gè)數(shù)字三角形，其中三角形中的數(shù)值為不超過(guò)100的整數(shù)，現(xiàn)規(guī)定從最頂層往下走到底層，每一步可沿左斜線向下或右斜線向下走。n 7n 3 8n 8 1 0n 2 7 4 4n4 5 2 6 5n 假設(shè)三角形行數(shù)=100，編程計(jì)算從最頂層走到最底層的

9、一條路徑，使得沿著該路徑所經(jīng)過(guò)的數(shù)字之和最大，輸出最大值。 輸入和輸出ntrigon.inn7n3 8n8 1 0n2 7 4 4n4 5 2 6 5ntrigon.outn30為什么可用動(dòng)態(tài)規(guī)劃n 7n 3 8n 8 1 0n 2 7 4 4n4 5 2 6 5算法設(shè)計(jì)n1、階段就是行號(hào)n2、狀態(tài)就是每行上的某個(gè)數(shù)字（位置號(hào)表示）n3、決策就是向右（還是向左）的走法。狀態(tài)轉(zhuǎn)移方程n若用fI,j表示起點(diǎn)到i階段第j個(gè)數(shù)字的最優(yōu)解，用j1表示j對(duì)應(yīng)的子狀態(tài)，xj1,k表示j1子狀態(tài)變換到j(luò)狀態(tài)中的第k個(gè)決策所產(chǎn)生的決策效應(yīng)，則可寫(xiě)出狀態(tài)轉(zhuǎn)移方程如下：nfI,j=maxfi-1,j1+xj1,k

10、| j1和k最多取二個(gè)值結(jié)合數(shù)據(jù)結(jié)構(gòu)調(diào)整方程n根據(jù)輸入數(shù)據(jù)特點(diǎn)，考慮用aI,j保存第i行第j個(gè)位置上的數(shù)字，那么前面方程中j1可取的值為j-1和j，所以狀態(tài)轉(zhuǎn)移方程可細(xì)化為：nfI,j=maxfi-1,j+aI,j,fi-1,j+1+aI,jn 其中1=i=n，1=j=i，初始化時(shí)f1,1=7。寫(xiě)出核心程序段nfillchar(f,sizeof(f),0);nf1,1:=a1,1;nfor i:=2 to n do 枚舉階段n for j:=1 to I do 枚舉狀態(tài)n for k:=j-1 to j do 枚舉決策n if fI,jfi-1,k+aI,j then fI,j:=fi-1,k

11、+aI,j;n這樣最后求得的fn,n是否是本問(wèn)題的最優(yōu)解？問(wèn)題3：彩石運(yùn)輸n阿強(qiáng)是一個(gè)汽車(chē)運(yùn)輸工，他正在給一項(xiàng)裝飾工程運(yùn)輸所需的彩色石頭。這些石頭的顏色各異，價(jià)格也各不相同。有一天阿強(qiáng)突發(fā)奇想，他想在一堆彩石中有選擇地把彩石裝上他的卡車(chē)，使得卡車(chē)上裝載的石頭總價(jià)值是所有裝載方案中最大的?，F(xiàn)在有一堆彩石堆放在阿強(qiáng)面前，他知道任何兩塊石頭的顏色都是不同的，但兩塊顏色不同的石頭的重量和價(jià)格可能相同。n 阿強(qiáng)的卡車(chē)總共可裝載的重量是W，而且他知道總的彩石的塊數(shù)，請(qǐng)你幫助阿強(qiáng)確定一個(gè)方案，滿足阿強(qiáng)的奇想。n 輸入文件stone.in的第一行是二個(gè)整數(shù)，依次表示卡車(chē)的載重量W和總的彩石塊數(shù)n，下面共有n行

12、，每行包含二個(gè)用空格分隔的整數(shù)，依次表示某種顏色彩石的重量和價(jià)值。n 輸出文件stone.out只包含一行一個(gè)整數(shù)，表示卡車(chē)最終裝載彩石的最大總價(jià)值。 輸入輸出nstone.inn30 5n20 50n10 30n15 44n5 14n4 13nstone.outn88問(wèn)題分析n1、有些選手會(huì)陷入二種錯(cuò)誤的貪心算法中n2、為什么可用動(dòng)態(tài)規(guī)劃n3、3個(gè)要素的分析n（1）階段n（2）狀態(tài)n（3）決策提煉出狀態(tài)轉(zhuǎn)移方程n用wi保存第i種彩石的重量，用pi表示它的價(jià)值，用j表示狀態(tài)，則狀態(tài)轉(zhuǎn)移方程如下：nfI,j=maxfi-1,j-wi+pi,fi-1,j 核心程序代碼nfillchar(f,siz

13、eof(f),0);nfor i:=1 to n donfor j:=1 to w donbeginn fI,j:=fi-1,j;n if (wi=w) and (fI,jfi-1,j-wi+pi) then fI,j:=fi-1,j-wi+pi;nend;nwrite(fn,w);問(wèn)題4：joy的工具箱nJoy是一位非常出色的汽車(chē)維修工，而且他的創(chuàng)業(yè)能力也很強(qiáng)，這不，最近他成立了自己的汽車(chē)維修110公司，一旦汽車(chē)在半途拋錨，只要一個(gè)電話，joy就會(huì)立刻帶著他的工具箱趕到事故地點(diǎn)，為駕駛員朋友維修汽車(chē)，由于搶修及時(shí)以及維修技術(shù)高，汽車(chē)維修110公司的生意越來(lái)越紅火。n 但joy是一個(gè)追求無(wú)止境

14、的人，在生意越做越大的同時(shí)，他又動(dòng)開(kāi)了新腦筋。他發(fā)現(xiàn)無(wú)論維修工具箱買(mǎi)得如何大，肯定不能把他公司里所有的維修工具裝進(jìn)去，100的故障排除率不僅需要精湛的維修技術(shù)，如何選擇并把最為合適的維修工具裝入工具箱，并把工具箱帶到故障現(xiàn)場(chǎng)，也是一個(gè)非常重要的技巧。由于工具眾多，joy無(wú)法根據(jù)駕駛員報(bào)告的故障現(xiàn)象確定最為合適的一些工具，作為朋友的你決定通過(guò)程序來(lái)幫助joy選擇最為合適的工具轉(zhuǎn)入到工具箱中。n n當(dāng)然，joy會(huì)事先告訴你一些必要的信息。比如，他的每個(gè)工具都是不同的，工具箱的總體積，joy還會(huì)告訴你他根據(jù)故障特點(diǎn)給每個(gè)工具合適程度的效率分?jǐn)?shù)，你的程序必須能確定哪些工具被裝入工具箱，并輸出總的最大效

15、率分。 n輸入文件joy.in第一行包含二個(gè)整數(shù)v和n，分別表示工具箱總體積和所有可供選擇的工具的數(shù)量。下面共有n行，每行有二個(gè)用空格分隔的整數(shù)，依次分別表示每個(gè)工具的體積大小和joy給定的效率分。n 輸出文件joy.out包含一個(gè)整數(shù)，表示在工具箱有限的空間內(nèi)，所裝入的所有工具的效率分?jǐn)?shù)的最大值。輸入和輸出njoy.inn23 5n11 20n9 19n10 15n7 14n8 15njoy.outn39關(guān)鍵要素分析n1、階段n2、狀態(tài)n3、決策分析狀態(tài)轉(zhuǎn)移方程nFI,j表示前i個(gè)工具選擇部分裝入占用容量為j的工具箱中的最大效率分：nfi,j:=maxfi-1,j-v1i+pi |核心程序段

16、nfillchar(f,sizeof(f),0);n for i:=1 to n don for j:=1 to v don beginn fi,j:=fi-1,j;n if (v1i=j) and (fi,j=ai) and (fj+1fi) then fi:=fj+1;n if bestfi then best:=fi;nend;nwrite(best); 逆推求解n如何進(jìn)行？問(wèn)題6：乘積最大n在一次數(shù)學(xué)智力競(jìng)賽中，主持人給所有參加活動(dòng)的選手出了一道題目：設(shè)有一個(gè)長(zhǎng)度為N的數(shù)字串，要求選手使用M個(gè)乘號(hào)將它分成M1部分，求出一種分法，使得這M+1個(gè)部分的乘積最大。n 同時(shí)，為了幫助選手能夠理

17、解題意，主持人還舉了如下一個(gè)例子：n 有一個(gè)數(shù)字串：312，當(dāng)N=3,M=1時(shí)有二種分法：n （1）31236；n （2）31262n 這時(shí)，符合題意要求的結(jié)果是：31262。現(xiàn)在要求設(shè)計(jì)一個(gè)程序，以求得正確的答案。n 輸入文件product.in第一行包含二個(gè)整數(shù)，分別表示N，M（2=N=10，1=M=5），第二行是一個(gè)長(zhǎng)度為N的數(shù)字串。n 輸出文件product.out包含一行一個(gè)自然數(shù)，表示求得的最大乘積。 輸入和輸出nproduct.inn4 2n1231nproduct.outn62算法分析n1、本來(lái)用搜索也可n2、n，m擴(kuò)大時(shí)，必須用動(dòng)態(tài)規(guī)劃n3、用fI,j表示在前i個(gè)數(shù)字中插入j

18、個(gè)乘號(hào)可以獲得的最大值，那么fn,m就是問(wèn)題的最優(yōu)解。特殊到一般抽象出轉(zhuǎn)移方程n1、顯然fI,j這個(gè)最優(yōu)解肯定是在下列情形中產(chǎn)生的：nfj,j-1*Aj+1Ainfj+1,j-1*Aj+2Ainnfi-1,j-1*Ain2、提煉出初步的轉(zhuǎn)移方程：nfI,j=maxfi1,j-1*(ai1+1ai) | j=i1=i-1n3、其中的(ai1+1ai)表示第i1+1位到第i位數(shù)字串所組成的整數(shù)。 勾畫(huà)出初步的代碼nFor i:=1 to n don For j:=0 to m don If j=i-1 then n For i1:=j to i-1 don If fI,jfi1,j-1*num(a

19、i1+1ai); n*開(kāi)始時(shí)所有的fI,j初始化為0思考n1、有沒(méi)有發(fā)現(xiàn)算法中的漏洞？n2、分析邊界、確定遞推初始值中完善算法完善后的算法n所有的fI,j初始化為0；nfor i:=1 to n-m do fI,0:=num(a1ai);n For i:=2 to n don For j:=1 to m don If j=i-1 then n For i1:=j to i-1 don If fI,jfi1,j-1*num(ai1+1ai);注意的細(xì)節(jié)n實(shí)際編程時(shí)還須使用高精度算法，由于這里著重介紹動(dòng)態(tài)規(guī)劃，故本過(guò)程省略。問(wèn)題7：校慶100周年n在柯中建校100周年之際，學(xué)校決定舉辦校慶活動(dòng)，發(fā)

20、出校慶通告和邀請(qǐng)后，學(xué)校收到了k多的祝賀條幅，在把這些條幅掛起來(lái)的時(shí)候，學(xué)校負(fù)責(zé)人要考慮到祝賀單位和個(gè)人的知名度和發(fā)送祝賀的先后順序，覺(jué)得有必要統(tǒng)籌地安排位置來(lái)掛這些條幅。n在柯中校門(mén)口的正面，有一座氣勢(shì)雄偉的綜合樓，前面有n（1=k=n=100）多的位置可以用來(lái)掛條幅，如何把這k條條幅掛到這n個(gè)位置上使之總體效果最大呢？學(xué)校負(fù)責(zé)人是這樣考慮的：首先給所有條幅按照送來(lái)的順序從1開(kāi)始編號(hào)，然后給綜合樓可掛條幅的位置也從1開(kāi)始編號(hào)，無(wú)論怎么考慮最大效果，編號(hào)小的條幅必須掛在編號(hào)大的條幅的前面（即所在位置的編號(hào)較?。?；但考慮到送條幅單位或個(gè)人知名度的問(wèn)題，負(fù)責(zé)人又給每個(gè)條幅掛在每個(gè)位置上的效果打了分

21、。最終希望掛條幅的效果分到達(dá)最大。n輸入文件aniversary.in第一行包含二個(gè)空格分隔的整數(shù)k和n，分別表示總條幅數(shù)量和總的可掛條幅的數(shù)量。下面一共有k行，每行有n個(gè)空格分隔的整數(shù)，輸入文件第i+1行第j列的整數(shù)表示編號(hào)為i的條幅掛在編號(hào)為j的位置上的效果分（在50到50之間）。n 輸出文件aniversary.out包含一行一個(gè)整數(shù)，表示可能獲得的最大的效果分。輸入和輸出naniversary.inn3 5n7 23 -5 -24 16n5 21 -4 10 23n-21 5 -4 -20 20naniversary.outn53三要素分析n1、橫幅作為階段In2、前i個(gè)橫幅放置所占的前j個(gè)位置作為狀態(tài)n3、決策就是第i個(gè)橫幅放置在前j個(gè)位置的哪個(gè)位置上狀態(tài)轉(zhuǎn)移方程n用ansI,j表示前i個(gè)橫幅放入前j個(gè)位置，并且第i個(gè)橫幅放置于第j個(gè)位置上的最優(yōu)解。nAnsI,j=maxansi-1,t+aI,j | i=j=n-(k-i),i-1=t=j-1 算法框架nfor i:=1 to k do 以條幅作為階段枚舉