動態(tài)規(guī)劃(普及組-)課件

動態(tài)規(guī)劃（普及組）紹興柯橋中學(xué)吳建鋒動態(tài)規(guī)劃（普及組）紹興柯橋中學(xué)認識動態(tài)規(guī)劃動態(tài)規(guī)劃在運籌學(xué)等領(lǐng)域都得到很大的運用，它是求解最優(yōu)化分階段決策問題的一種數(shù)學(xué)方法，大約產(chǎn)生于50年代。1951年美國數(shù)學(xué)家Bellman等人根據(jù)一類多階段決策問題的特點，把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然后逐個加以解決。與此同時，他提出了解決這類問題的“最優(yōu)性原理”，研究了許多實際問題，從而創(chuàng)建了解決最優(yōu)化問題的一種新的方法―――動態(tài)規(guī)劃。認識動態(tài)規(guī)劃動態(tài)規(guī)劃在運籌學(xué)等領(lǐng)域都得到很大的運用，它是求解多階段決策過程123n多階段決策過程123n“動態(tài)”的內(nèi)涵在分階段決策問題中，各個階段采取的決策，一般來說是與時間有關(guān)的，決策依賴于當(dāng)前的狀態(tài)，又隨即引起狀態(tài)的改變（轉(zhuǎn)移），一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以有“動態(tài)”的含義。因此，把處理它的方法稱為動態(tài)規(guī)劃方法?！皠討B(tài)”的內(nèi)涵在分階段決策問題中，各個階段采取的決策，一般來問題1：求最短路徑長度假如有下圖所示的交通示意圖，有向邊上的數(shù)值表示邊的長度，求A到D的最短路徑的長度。ABCD13192815問題1：求最短路徑長度假如有下圖所示的交通示意圖，有向邊上的解法1：從初始階段出發(fā)的順推求解1、用f[i]表示A到結(jié)點i的最短距離2、我們可以求得f[A]=13，f[B]＝19（第一階段）3、第二階段求解過程如下：f[B]+28=41{f[D]的候選最優(yōu)解}f[C]+15=34{f[D]的候選最優(yōu)解}4、保存較優(yōu)解：f[D]=min{f[B]+28,f[C]+15}解法1：從初始階段出發(fā)的順推求解1、用f[i]表示A到結(jié)點i解法2：目標階段出發(fā)的逆推求解1、如果用f[i]表示編號為i的結(jié)點到終點d的最短距離，那么動態(tài)規(guī)劃分階段求解的過程如下所示：（1）f[D]:=0{初始化}（2）f[B]:=28+f[D];f[C]:=15+f[D]{第一階段求解}（3）f[A]:=min{13+f[B],19+f[C]}{狀態(tài)轉(zhuǎn)移方程的體現(xiàn)，第二階段求解}解法2：目標階段出發(fā)的逆推求解1、如果用f[i]表示編號為i什么叫狀態(tài)轉(zhuǎn)移方程對于當(dāng)前階段的某個狀態(tài)，必定有有上個階段的子問題的某一批狀態(tài)通過對應(yīng)的決策變換而來，這些子問題的一批狀態(tài)通過對應(yīng)的決策應(yīng)用，就導(dǎo)致了狀態(tài)轉(zhuǎn)移，新的狀態(tài)就是當(dāng)前階段的某個狀態(tài)。由于這個新狀態(tài)的子狀態(tài)可能不止一個，所以決策后的對應(yīng)局部解也可能不止一個，在這些解中取一個最優(yōu)解，就是當(dāng)前階段當(dāng)前狀態(tài)的最優(yōu)解，這個求最優(yōu)解的過程可用一個表達式來描述，這個表達式就是狀態(tài)轉(zhuǎn)移方程。什么叫狀態(tài)轉(zhuǎn)移方程對于當(dāng)前階段的某個狀態(tài)，必定有有上個階段的狀態(tài)轉(zhuǎn)移方程應(yīng)用舉例在下列交通路線中，求節(jié)點1到節(jié)點10的最短路徑的長度。14326598710132191517324527111381916251120狀態(tài)轉(zhuǎn)移方程應(yīng)用舉例在下列交通路線中，求節(jié)點1到節(jié)點10的分階段決策的手工計算第一階段：f[2]=f[1]+13=13;f[3]=f[1]+21=21;f[4]=f[1]+9=9第二階段：f[5]=min{f[2]+15,f[3]+17,f[4]+24}=28;f[6]=min{f[2]+3,f[3]+5,f[4]+27}=16第三階段：f[7]=min{f[5]+11,f[6]+8}=24;f[8]=min{f[5]+13,f[6]+19}=35;f[9]=min{f[6]+16}=32

分階段決策的手工計算第一階段：目標階段求解第四階段：f[10]=min{f[7]+25,f[8]+11,f[9]+20}=46目標階段求解第四階段：具體化的狀態(tài)轉(zhuǎn)移方程1、f[5]=min{f[j]+x,……}，f[6]=min{f[k]+y,……}2、f[j]+x中的f[j]就是上階段子問題各狀態(tài)的最優(yōu)解；而x則是某個子狀態(tài)轉(zhuǎn)移到當(dāng)前狀態(tài)產(chǎn)生的決策效應(yīng)（或者是代價）具體化的狀態(tài)轉(zhuǎn)移方程1、f[5]=min{f[j]+x,……一般化的狀態(tài)轉(zhuǎn)移方程實際編程實現(xiàn)時，狀態(tài)轉(zhuǎn)移方程往往是一個通用計算式，在這個通用計算式中往往會包含各種子狀態(tài)、子狀態(tài)對應(yīng)子問題的最優(yōu)解、決策等參數(shù)。一般化的狀態(tài)轉(zhuǎn)移方程實際編程實現(xiàn)時，狀態(tài)轉(zhuǎn)移方程往往是一個通動態(tài)規(guī)劃的算法設(shè)計如果用i表示當(dāng)前需求解的階段號（有時為了描述的方便，i也可表示當(dāng)前階段的前一個階段），j表示當(dāng)前階段各個狀態(tài)（或者說是階段的各個節(jié)點編號），k表示前一階段各個子狀態(tài)能選擇的策略，用f[I,j]表示起點1到第i階段編號為j的結(jié)點（也可理解為狀態(tài)）的最短距離，那么上面問題用動態(tài)規(guī)劃求解的大致程序結(jié)構(gòu)如下：動態(tài)規(guī)劃的算法設(shè)計如果用i表示當(dāng)前需求解的階段號（有時為了描窮舉所有的階段（fori:=1to4do）窮舉當(dāng)前階段i所有可能的狀態(tài)j窮舉j狀態(tài)所有對應(yīng)的子狀態(tài)的所有可選擇的策略kF[I,j]:=min{f[i-1,j1]+x[j1,k]|j1表示狀態(tài)j所有可能的子狀態(tài)}窮舉所有的階段（fori:=1to4do）程序代碼實現(xiàn)輸入數(shù)據(jù)：23405607890100013219maxintmaxintmaxintmaxintmaxintmaxintmaxint0maxintmaxint153maxintmaxintmaxintmaxintmaxintmaxint0maxint175maxintmaxintmaxintmaxintmaxintmaxintmaxint02427maxintmaxintmaxintmaxint……程序代碼實現(xiàn)輸入數(shù)據(jù)：數(shù)據(jù)結(jié)構(gòu)A[I,j]=k表示第i階段的第j個決策點（后繼節(jié)點）是k；D[I,j]=k表示i和j節(jié)點之間的直接聯(lián)邊長度是k，如果是maxint則表示沒有直接聯(lián)邊。如果是0則表示節(jié)點本身。數(shù)據(jù)結(jié)構(gòu)A[I,j]=k表示第i階段的第j個決策點（后繼節(jié)點程序框架fori:=1to4dobeginj:=1;repeatj2:=a[I,j];k:=1;repeatj1:=a[i-1,k];ifd[j1,j2]<>maxintthenf[I,j2]:=min{f[I,j2],f[i-1,j1]+d[j1,j2]}inc(k);untila[i-1,k]=0;inc(j);untila[I,j]=0;end;程序框架fori:=1to4do一些關(guān)鍵的要素1、階段每個階段的處理是相同的。2、狀態(tài)每個抽象化的節(jié)點所共有的特性值。3、決策所選擇的處理。一些關(guān)鍵的要素1、階段分析動態(tài)規(guī)劃1、何時可考慮動態(tài)規(guī)劃2、階段、狀態(tài)、決策如何提煉3、如何抽象出狀態(tài)轉(zhuǎn)移方程分析動態(tài)規(guī)劃1、何時可考慮動態(tài)規(guī)劃問題2：數(shù)字三角形下圖所示為一個數(shù)字三角形，其中三角形中的數(shù)值為不超過100的整數(shù)，現(xiàn)規(guī)定從最頂層往下走到底層，每一步可沿左斜線向下或右斜線向下走。738810274445265

假設(shè)三角形行數(shù)<=100，編程計算從最頂層走到最底層的一條路徑，使得沿著該路徑所經(jīng)過的數(shù)字之和最大，輸出最大值。問題2：數(shù)字三角形下圖所示為一個數(shù)字三角形，其中三角形中的數(shù)輸入和輸出trigon.in738810274445265trigon.out30輸入和輸出trigon.in為什么可用動態(tài)規(guī)劃738810274445265為什么可用動態(tài)規(guī)劃算法設(shè)計1、階段就是行號2、狀態(tài)就是每行上的某個數(shù)字（位置號表示）3、決策就是向右（還是向左）的走法。算法設(shè)計1、階段就是行號狀態(tài)轉(zhuǎn)移方程若用f[I,j]表示起點到i階段第j個數(shù)字的最優(yōu)解，用j1表示j對應(yīng)的子狀態(tài)，x[j1,k]表示j1子狀態(tài)變換到j(luò)狀態(tài)中的第k個決策所產(chǎn)生的決策效應(yīng)，則可寫出狀態(tài)轉(zhuǎn)移方程如下：f[I,j]=max{f[i-1,j1]+x[j1,k]|j1和k最多取二個值}狀態(tài)轉(zhuǎn)移方程若用f[I,j]表示起點到i階段第j個數(shù)字的最優(yōu)結(jié)合數(shù)據(jù)結(jié)構(gòu)調(diào)整方程根據(jù)輸入數(shù)據(jù)特點，考慮用a[I,j]保存第i行第j個位置上的數(shù)字，那么前面方程中j1可取的值為j-1和j，所以狀態(tài)轉(zhuǎn)移方程可細化為：f[I,j]=max{f[i-1,j]+a[I,j],f[i-1,j+1]+a[I,j]}其中1<=i<=n，1<=j<=i，初始化時f[1,1]=7。結(jié)合數(shù)據(jù)結(jié)構(gòu)調(diào)整方程根據(jù)輸入數(shù)據(jù)特點，考慮用a[I,j]保存寫出核心程序段fillchar(f,sizeof(f),0);f[1,1]:=a[1,1];fori:=2tondo{枚舉階段}forj:=1toIdo{枚舉狀態(tài)}fork:=j-1tojdo{枚舉決策}iff[I,j]<f[i-1,k]+a[I,j]thenf[I,j]:=f[i-1,k]+a[I,j];寫出核心程序段fillchar(f,sizeof(f),0)這樣最后求得的f[n,n]是否是本問題的最優(yōu)解？動態(tài)規(guī)劃(普及組-)課件問題3：彩石運輸阿強是一個汽車運輸工，他正在給一項裝飾工程運輸所需的彩色石頭。這些石頭的顏色各異，價格也各不相同。有一天阿強突發(fā)奇想，他想在一堆彩石中有選擇地把彩石裝上他的卡車，使得卡車上裝載的石頭總價值是所有裝載方案中最大的。現(xiàn)在有一堆彩石堆放在阿強面前，他知道任何兩塊石頭的顏色都是不同的，但兩塊顏色不同的石頭的重量和價格可能相同。阿強的卡車總共可裝載的重量是W，而且他知道總的彩石的塊數(shù)，請你幫助阿強確定一個方案，滿足阿強的奇想。輸入文件stone.in的第一行是二個整數(shù)，依次表示卡車的載重量W和總的彩石塊數(shù)n，下面共有n行，每行包含二個用空格分隔的整數(shù)，依次表示某種顏色彩石的重量和價值。輸出文件stone.out只包含一行一個整數(shù)，表示卡車最終裝載彩石的最大總價值。問題3：彩石運輸阿強是一個汽車運輸工，他正在給一項裝飾工程運輸入輸出stone.in305205010301544514413stone.out88輸入輸出stone.in問題分析1、有些選手會陷入二種錯誤的貪心算法中2、為什么可用動態(tài)規(guī)劃3、3個要素的分析（1）階段（2）狀態(tài)（3）決策問題分析1、有些選手會陷入二種錯誤的貪心算法中提煉出狀態(tài)轉(zhuǎn)移方程用w[i]保存第i種彩石的重量，用p[i]表示它的價值，用j表示狀態(tài)，則狀態(tài)轉(zhuǎn)移方程如下：f[I,j]=max{f[i-1,j-w[i]]+p[i],f[i-1,j]}提煉出狀態(tài)轉(zhuǎn)移方程用w[i]保存第i種彩石的重量，用p[i]核心程序代碼fillchar(f,sizeof(f),0);fori:=1tondoforj:=1towdobeginf[I,j]:=f[i-1,j];if(w[i]<=w)and(f[I,j]<f[i-1,j-w[i]]+p[i])thenf[I,j]:=f[i-1,j-w[i]]+p[i];end;write(f[n,w]);核心程序代碼fillchar(f,sizeof(f),0);問題4：joy的工具箱Joy是一位非常出色的汽車維修工，而且他的創(chuàng)業(yè)能力也很強，這不，最近他成立了自己的汽車維修110公司，一旦汽車在半途拋錨，只要一個電話，joy就會立刻帶著他的工具箱趕到事故地點，為駕駛員朋友維修汽車，由于搶修及時以及維修技術(shù)高，汽車維修110公司的生意越來越紅火。但joy是一個追求無止境的人，在生意越做越大的同時，他又動開了新腦筋。他發(fā)現(xiàn)無論維修工具箱買得如何大，肯定不能把他公司里所有的維修工具裝進去，100％的故障排除率不僅需要精湛的維修技術(shù)，如何選擇并把最為合適的維修工具裝入工具箱，并把工具箱帶到故障現(xiàn)場，也是一個非常重要的技巧。由于工具眾多，joy無法根據(jù)駕駛員報告的故障現(xiàn)象確定最為合適的一些工具，作為朋友的你決定通過程序來幫助joy選擇最為合適的工具轉(zhuǎn)入到工具箱中。

問題4：joy的工具箱Joy是一位非常出色的汽車維修工，而且當(dāng)然，joy會事先告訴你一些必要的信息。比如，他的每個工具都是不同的，工具箱的總體積，joy還會告訴你他根據(jù)故障特點給每個工具合適程度的效率分數(shù)，你的程序必須能確定哪些工具被裝入工具箱，并輸出總的最大效率分。當(dāng)然，joy會事先告訴你一些必要的信息。比如，他的每個工具都輸入文件joy.in第一行包含二個整數(shù)v和n，分別表示工具箱總體積和所有可供選擇的工具的數(shù)量。下面共有n行，每行有二個用空格分隔的整數(shù)，依次分別表示每個工具的體積大小和joy給定的效率分。輸出文件joy.out包含一個整數(shù)，表示在工具箱有限的空間內(nèi)，所裝入的所有工具的效率分數(shù)的最大值。輸入文件joy.in第一行包含二個整數(shù)v和n，分別表示工具箱輸入和輸出joy.in23511209191015714815joy.out39輸入和輸出joy.in關(guān)鍵要素分析1、階段2、狀態(tài)3、決策關(guān)鍵要素分析1、階段分析狀態(tài)轉(zhuǎn)移方程F[I,j]表示前i個工具選擇部分裝入占用容量為j的工具箱中的最大效率分：f[i,j]:=max{f[i-1,j-v1[i]]+p[i]|}分析狀態(tài)轉(zhuǎn)移方程F[I,j]表示前i個工具選擇部分裝入占用容核心程序段fillchar(f,sizeof(f),0);fori:=1tondoforj:=1tovdobeginf[i,j]:=f[i-1,j];if(v1[i]<=j)and(f[i,j]<f[i-1,j-v1[i]]+p[i])thenf[i,j]:=f[i-1,j-v1[i]]+p[i];end;write(f[n,v]);核心程序段fillchar(f,sizeof(f),0);動態(tài)規(guī)劃的應(yīng)用（問題5）導(dǎo)彈攔截。某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈？如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)？動態(tài)規(guī)劃的應(yīng)用（問題5）導(dǎo)彈攔截。某國為了防御敵國的導(dǎo)彈襲擊輸入和輸出missile.in38920715530029917015865

missile.out6（最多能攔截的導(dǎo)彈數(shù)）

2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）輸入和輸出missile.in順推求解1、用f[i]表示從第1枚導(dǎo)彈到第i枚導(dǎo)彈這個子問題的最優(yōu)解（包含這枚導(dǎo)彈的決策序列），a[j]表示第j枚導(dǎo)彈的高度。2、開始時所有的f[i]都初始化為13、i從2開始直到n進行順推計算所有的f[i]4、最后輸出最大的f[i]順推求解1、用f[i]表示從第1枚導(dǎo)彈到第i枚導(dǎo)彈這個子問題某個階段i的f[i]求解1、f[i]的子問題是哪些？2、f[i]子問題的最優(yōu)解保存在哪里？3、如何根據(jù)子問題的最優(yōu)解推算父問題的最優(yōu)解？某個階段i的f[i]求解1、f[i]的子問題是哪些？狀態(tài)轉(zhuǎn)移方程F[i]=max{f[j]+1|必須滿足的是所有的a[j]都必須不小于a[i]}狀態(tài)轉(zhuǎn)移方程F[i]=max{f[j]+1|必須滿足的是核心程序段fillchar(f,sizeof(f),1);best:=1;fori:=2tondobeginforj:=1toi-1doif(a[j]>=a[i])and(f[j]+1>f[i])thenf[i]:=f[j]+1;ifbest<f[i]thenbest:=f[i];end;write(best);核心程序段fillchar(f,sizeof(f),1);逆推求解如何進行？逆推求解問題6：乘積最大在一次數(shù)學(xué)智力競賽中，主持人給所有參加活動的選手出了一道題目：設(shè)有一個長度為N的數(shù)字串，要求選手使用M個乘號將它分成M＋1部分，求出一種分法，使得這M+1個部分的乘積最大。同時，為了幫助選手能夠理解題意，主持人還舉了如下一個例子：有一個數(shù)字串：312，當(dāng)N=3,M=1時有二種分法：（1）3×12＝36；（2）31×2＝62

這時，符合題意要求的結(jié)果是：31×2＝62。現(xiàn)在要求設(shè)計一個程序，以求得正確的答案。輸入文件product.in第一行包含二個整數(shù)，分別表示N，M（2<=N<=10，1<=M<=5），第二行是一個長度為N的數(shù)字串。輸出文件product.out包含一行一個自然數(shù)，表示求得的最大乘積。問題6：乘積最大在一次數(shù)學(xué)智力競賽中，主持人給所有參加活動的輸入和輸出product.in421231product.out62輸入和輸出product.in算法分析1、本來用搜索也可2、n，m擴大時，必須用動態(tài)規(guī)劃3、用f[I,j]表示在前i個數(shù)字中插入j個乘號可以獲得的最大值，那么f[n,m]就是問題的最優(yōu)解。算法分析1、本來用搜索也可特殊到一般抽象出轉(zhuǎn)移方程1、顯然f[I,j]這個最優(yōu)解肯定是在下列情形中產(chǎn)生的：f[j,j-1]*Aj+1…Aif[j+1,j-1]*Aj+2…Ai……f[i-1,j-1]*Ai特殊到一般抽象出轉(zhuǎn)移方程1、顯然f[I,j]這個最優(yōu)解肯定是2、提煉出初步的轉(zhuǎn)移方程：f[I,j]=max{f[i1,j-1]*(a[i1+1]…a[i])|j<=i1<=i-1}3、其中的(a[i1+1]…a[i])表示第i1+1位到第i位數(shù)字串所組成的整數(shù)。2、提煉出初步的轉(zhuǎn)移方程：勾畫出初步的代碼Fori:=1tondoForj:=0tomdoIfj<=i-1thenFori1:=jtoi-1doIff[I,j]<f[i1,j-1]*num(a[i1+1]…a[i]);*開始時所有的f[I,j]初始化為0勾畫出初步的代碼Fori:=1tondo思考1、有沒有發(fā)現(xiàn)算法中的漏洞？2、分析邊界、確定遞推初始值中完善算法思考1、有沒有發(fā)現(xiàn)算法中的漏洞？完善后的算法所有的f[I,j]初始化為0；fori:=1ton-mdof[I,0]:=num(a[1]…a[i]);Fori:=2tondoForj:=1tomdoIfj<=i-1thenFori1:=jtoi-1doIff[I,j]<f[i1,j-1]*num(a[i1+1]…a[i]);完善后的算法所有的f[I,j]初始化為0；注意的細節(jié)實際編程時還須使用高精度算法，由于這里著重介紹動態(tài)規(guī)劃，故本過程省略。注意的細節(jié)問題7：校慶100周年在柯中建校100周年之際，學(xué)校決定舉辦校慶活動，發(fā)出校慶通告和邀請后，學(xué)校收到了k多的祝賀條幅，在把這些條幅掛起來的時候，學(xué)校負責(zé)人要考慮到祝賀單位和個人的知名度和發(fā)送祝賀的先后順序，覺得有必要統(tǒng)籌地安排位置來掛這些條幅。在柯中校門口的正面，有一座氣勢雄偉的綜合樓，前面有n（1<=k<=n<=100）多的位置可以用來掛條幅，如何把這k條條幅掛到這n個位置上使之總體效果最大呢？學(xué)校負責(zé)人是這樣考慮的：首先給所有條幅按照送來的順序從1開始編號，然后給綜合樓可掛條幅的位置也從1開始編號，無論怎么考慮最大效果，編號小的條幅必須掛在編號大的條幅的前面（即所在位置的編號較?。?；但考慮到送條幅單位或個人知名度的問題，負責(zé)人又給每個條幅掛在每個位置上的效果打了分。最終希望掛條幅的效果分到達最大。問題7：校慶100周年在柯中建校100周年之際，學(xué)校決定舉辦輸入文件aniversary.in第一行包含二個空格分隔的整數(shù)k和n，分別表示總條幅數(shù)量和總的可掛條幅的數(shù)量。下面一共有k行，每行有n個空格分隔的整數(shù)，輸入文件第i+1行第j列的整數(shù)表示編號為i的條幅掛在編號為j的位置上的效果分（在－50到50之間）。輸出文件aniversary.out包含一行一個整數(shù)，表示可能獲得的最大的效果分。輸入文件aniversary.in第一行包含二個空格分隔的整輸入和輸出aniversary.in35723-5-2416521-41023-215-4-2020aniversary.out53輸入和輸出aniversary.in三要素分析1、橫幅作為階段I2、前i個橫幅放置所占的前j個位置作為狀態(tài)3、決策就是第i個橫幅放置在前j個位置的哪個位置上三要素分析1、橫幅作為階段I狀態(tài)轉(zhuǎn)移方程用ans[I,j]表示前i個橫幅放入前j個位置，并且第i個橫幅放置于第j個位置上的最優(yōu)解。Ans[I,j]=max{ans[i-1,t]+a[I,j]|i<=j<=n-(k-i),i-1<=t<=j-1}狀態(tài)轉(zhuǎn)移方程用ans[