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

動(dòng)態(tài)規(guī)劃（普及組）1紹興柯橋中學(xué)吳建鋒認(rèn)識(shí)動(dòng)態(tài)規(guī)劃2動(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ù)一類多階段決策問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換為一系列互相聯(lián)系的單階段問(wèn)題，然后逐個(gè)加以解決。與此同時(shí)，他提出了解決這類問(wèn)題的“最優(yōu)性原理”，研究了許多實(shí)際問(wèn)題，從而創(chuàng)建了解決最優(yōu)化問(wèn)題的一種新的方法―――動(dòng)態(tài)規(guī)劃。多階段決策過(guò)程123n3“動(dòng)態(tài)”的內(nèi)涵4在分階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與時(shí)間有關(guān)的，決策依賴于當(dāng)前

的狀態(tài)，又隨即引起狀態(tài)的改變（轉(zhuǎn)移），一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)

的，所以有“動(dòng)態(tài)”的含義。因此，把處理它

的方法稱為動(dòng)態(tài)規(guī)劃方法。問(wèn)題1：求最短路徑長(zhǎng)度假如有下圖所示的交通示意圖，有向邊上的數(shù)值表示邊的長(zhǎng)度，求A到D的最短路徑的長(zhǎng)度。ABCD135192815解法1：從初始階段出發(fā)的順推求解61、用f[i]表示A到結(jié)點(diǎn)i的最短距離2、我們可以求得f[A]=13，f[B]＝19

（第一階段）3、第二階段求解過(guò)程如下：f[B]+28=41f[C]+15=34{f[D]的候選最優(yōu)解}{f[D]的候選最優(yōu)解}4、保存較優(yōu)解：f[D]=min{f[B]+28,f[C]+15}解法2：目標(biāo)階段出發(fā)的逆推求解71、如果用f[i]表示編號(hào)為i的結(jié)點(diǎn)到終點(diǎn)d的最短距離，那么動(dòng)態(tài)規(guī)劃分階段求解的過(guò)程如下所示：（1）f[D]:=0

{初始化}{第一{狀態(tài)轉(zhuǎn)移（2）f[B]:=28+f[D];

f[C]:=15+f[D]階段求解}（3）f[A]:=min{13+f[B],19+f[C]}方程的體現(xiàn)，第二階段求解}什么叫狀態(tài)轉(zhuǎn)移方程8對(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)用舉例143265987101392191517324527在下列交通路線中，求節(jié)點(diǎn)1到節(jié)點(diǎn)10

的最短路徑的長(zhǎng)度。111381916251120分階段決策的手工計(jì)算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

目標(biāo)階段求解11第四階段：f[10]=min{f[7]+25,f[8]+11,f[9]+20}=46具體化的狀態(tài)轉(zhuǎn)移方程121、f[5]=min{f[j]+x,……}，f[6]=min{f[k]+y,……}2、f[j]+x中的f[j]就是上階段子問(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)移方程13實(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ì)14如果用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)能選擇的策略，用f[I,j]表示起點(diǎn)1到第i階段編號(hào)為j的結(jié)點(diǎn)（也可理解為狀態(tài)）的最短距離，那么上面問(wèn)題用動(dòng)態(tài)規(guī)劃求解的大致程序結(jié)構(gòu)如下：窮舉所有的階段（for

i:=1

to

4

do）窮舉當(dāng)前階段i所有可能的狀態(tài)j

窮舉j狀態(tài)所有對(duì)應(yīng)的子狀態(tài)的所有可選擇的策略kF[I,j]:=min{f[i-1,j1]+x[j1,k]

|

j1表示狀態(tài)j所有可能的子狀態(tài)}15程序代碼實(shí)現(xiàn)16輸入數(shù)據(jù)：2

3

4

05

6

07

8

9

010

00

13

21

9

maxint

maxint

maxint

maxint

maxint

maxintmaxint

0

maxint

maxint

15

3

maxint

maxint

maxint

maxintmaxint

maxint

0

maxint

17

5

maxint

maxint

maxint

maxintmaxint

maxint

maxint

0

24

27

maxint

maxint

maxint

maxint……數(shù)據(jù)結(jié)構(gòu)17A[I,j]=k表示第i階段的第j個(gè)決策點(diǎn)（后繼節(jié)點(diǎn)）是k；D[I,j]=k表示i和j節(jié)點(diǎn)之間的直接聯(lián)邊長(zhǎng)度是k，如果是maxint則表示沒(méi)有直接聯(lián)邊。如果是0則表示節(jié)點(diǎn)本身。程序框架18for

i:=1

to

4

dobeginj:=1;repeatj2:=a[I,j];k:=1;repeatj1:=a[i-1,k];if

d[j1,j2]<>maxint

then

f[I,j2]:=min{f[I,j2],f[i-1,j1]+d[j1,j2]}inc(k);until

a[i-1,k]=0;inc(j);until

a[I,j]=0;end;一些關(guān)鍵的要素191、階段每個(gè)階段的處理是相同的。2、狀態(tài)每個(gè)抽象化的節(jié)點(diǎn)所共有的特性值。3、決策所選擇的處理。分析動(dòng)態(tài)規(guī)劃201、何時(shí)可考慮動(dòng)態(tài)規(guī)劃2、階段、狀態(tài)、決策如何提煉3、如何抽象出狀態(tài)轉(zhuǎn)移方程問(wèn)題2：數(shù)字三角形21下圖所示為一個(gè)數(shù)字三角形，其中三角形中的數(shù)值為不超過(guò)

100的整數(shù)，現(xiàn)規(guī)定從最頂層往下走到底層，每一步可沿左斜線向下或右斜線向下走。73

88

1

02

7

4

44

5

2

6

5

假設(shè)三角形行數(shù)<=100，編程計(jì)算從最頂層走到最底層的一

條路徑，使得沿著該路徑所經(jīng)過(guò)的數(shù)字之和最大，輸出最大值。輸入和輸出22trigon.in738810274445265trigon.out30為什么可用動(dòng)態(tài)規(guī)劃

7

38

81027444526523算法設(shè)計(jì)241、階段就是行號(hào)2、狀態(tài)就是每行上的某個(gè)數(shù)字（位置號(hào)表示）3、決策就是向右（還是向左）的走法。狀態(tài)轉(zhuǎn)移方程25若用f[I,j]表示起點(diǎn)到i階段第j個(gè)數(shù)字的最優(yōu)解，用j1表示j對(duì)應(yīng)的子狀態(tài)，x[j1,k]表示j1子狀態(tài)變換到j(luò)狀態(tài)中的第k個(gè)決策所產(chǎn)生的決策效應(yīng)，則可寫(xiě)出狀態(tài)轉(zhuǎn)移方程如下：f[I,j]=max{f[i-1,j1]+x[j1,k]|j1和k最多取二個(gè)值}結(jié)合數(shù)據(jù)結(jié)構(gòu)調(diào)整方程26根據(jù)輸入數(shù)據(jù)特點(diǎn)，考慮用a[I,j]保存第i行第j個(gè)位置上的數(shù)字，那么前面方程中j1可取的值為j-1和j，所以狀態(tài)轉(zhuǎn)移方程可細(xì)化為：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，初始化時(shí)f[1,1]=7。寫(xiě)出核心程序段27fillchar(f,sizeof(f),0);f[1,1]:=a[1,1];for

i:=2

to

n

dofor

j:=1

to

I

do{枚舉階段}{枚舉狀態(tài)}{枚舉決策}for

k:=j-1tojdo

if

f[I,j]<f[i-1,k]+a[I,j]

then

f[I,j]:=f[i-1,k]+a[I,j];這樣最后求得的f[n,n]是否是本問(wèn)題的最優(yōu)解？28問(wèn)題3：彩石運(yùn)輸29阿強(qiáng)是一個(gè)汽車運(yùn)輸工，他正在給一項(xiàng)裝飾工程運(yùn)輸所需的彩色石頭。這些石頭的顏色各異，價(jià)格也各不相同。有一天阿強(qiáng)突發(fā)奇想，他想在一堆彩石中有選擇地把彩石裝上他的卡車，使得卡車上裝載的石頭總價(jià)值是所有裝載方案中最大的。現(xiàn)在有一堆彩石堆放在阿強(qiáng)面前，他知道任何兩塊石頭的顏色都是不同的，但兩塊顏色不同的石頭的重量和價(jià)格可能相同。

阿強(qiáng)的卡車總共可裝載的重量是W，而且他知道總的彩石的塊數(shù)，請(qǐng)你幫助阿強(qiáng)確定一個(gè)方案，滿足阿強(qiáng)的奇想。

輸入文件stone.in的第一行是二個(gè)整數(shù)，依次表示卡車的載重量W和總的彩石塊數(shù)n，下面共有n行，每行包含二個(gè)用空格分隔的整數(shù)，依次表示某種顏色彩石的重量和價(jià)值。

輸出文件stone.out只包含一行一個(gè)整數(shù)，表示卡車最終裝載彩石的最大總價(jià)值。輸入輸出30stone.in30

520

5010

3015

445

144

13stone.out88問(wèn)題分析311、有些選手會(huì)陷入二種錯(cuò)誤的貪心算法中2、為什么可用動(dòng)態(tài)規(guī)劃3、3個(gè)要素的分析（1）階段（2）狀態(tài)（3）決策提煉出狀態(tài)轉(zhuǎn)移方程32用w[i]保存第i種彩石的重量，用p[i]表示它的價(jià)值，用j表示狀態(tài)，則狀態(tài)轉(zhuǎn)移方程如下：f[I,j]=max{f[i-1,j-w[i]]+p[i],f[i-1,j]}核心程序代碼33fillchar(f,sizeof(f),0);for

i:=1

to

n

dofor

j:=1

to

w

dobeginf[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]);問(wèn)題4：joy的工具箱34Joy是一位非常出色的汽車維修工，而且他的創(chuàng)業(yè)能力也很強(qiáng)，這不，最近他成立了自己的汽車維修110公司，一旦汽車在半

途拋錨，只要一個(gè)電話，joy就會(huì)立刻帶著他的工具箱趕到事故地點(diǎn)，為駕駛員朋友維修汽車，由于搶修及時(shí)以及維修技術(shù)高，汽車維修110公司的生意越來(lái)越紅火。

但joy是一個(gè)追求無(wú)止境的人，在生意越做越大的同時(shí)，他又動(dòng)開(kāi)了新腦筋。他發(fā)現(xiàn)無(wú)論維修工具箱買得如何大，肯定不能把他公司里所有的維修工具裝進(jìn)去，100％的故障排除率不僅需要精湛的維修技術(shù)，如何選擇并把最為合適的維修工具裝入工具箱，并把工具箱帶到故障現(xiàn)場(chǎng)，也是一個(gè)非常重要的技巧。由于工具眾多，joy無(wú)法根據(jù)駕駛員報(bào)告的故障現(xiàn)象確定最為合適的一些工具，作為朋友的你決定通過(guò)程序來(lái)幫助joy選擇最為合適的工具轉(zhuǎn)入到工具箱中。

當(dāng)然，joy會(huì)事先告訴你一些必要的信息。比如，他的每個(gè)工具都是不同的，工具箱的總體積，joy還會(huì)告訴你他根據(jù)故障特點(diǎn)給每個(gè)工具合適程度的效率分?jǐn)?shù)，你的程序必須能確定哪些工具被裝入工具箱，并輸出總的最大效率分。35輸入文件joy.in第一行包含二個(gè)整數(shù)v和n，分別表示工具箱總體積和所有可供選擇的工具的數(shù)量。下面共有n行，每行有二個(gè)用空格分隔的整數(shù)，依次分別表示每個(gè)工具的體積大小和joy給定的效率分。

輸出文件joy.out包含一個(gè)整數(shù)，表示在工具箱有限的空間內(nèi)，所裝入的所有工具的效率分?jǐn)?shù)的最大值。36輸入和輸出37joy.in23

511

209

1910

157

148

15joy.out39關(guān)鍵要素分析381、階段2、狀態(tài)3、決策分析狀態(tài)轉(zhuǎn)移方程39F[I,j]表示前i個(gè)工具選擇部分裝入占用容量為j的工具箱中的最大效率分：f[i,j]:=max{f[i-1,j-v1[i]]+p[i]

|}核心程序段40fillchar(f,sizeof(f),0);for

i:=1

to

n

dofor

j:=1

to

v

dobeginf[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]);動(dòng)態(tài)規(guī)劃的應(yīng)用（問(wèn)題5）41導(dǎo)彈攔截。某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(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)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)？輸入和輸出42missile.in389

207

155

300

299

170

158

65missile.out6（最多能攔截的導(dǎo)彈數(shù)）2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）順推求解431、用f[i]表示從第1枚導(dǎo)彈到第i枚導(dǎo)彈這個(gè)子問(wèn)題的最優(yōu)解（包含這枚導(dǎo)彈的決策序列），a[j]表示第j枚導(dǎo)彈的高度。2、開(kāi)始時(shí)所有的f[i]都初始化為13、i從2開(kāi)始直到n進(jìn)行順推計(jì)算所有的f[i]4、最后輸出最大的f[i]某個(gè)階段i的f[i]求解441、f[i]的子問(wèn)題是哪些？2、f[i]子問(wèn)題的最優(yōu)解保存在哪里？3、如何根據(jù)子問(wèn)題的最優(yōu)解推算父問(wèn)題的最優(yōu)解？狀態(tài)轉(zhuǎn)移方程45F[i]=max{f[j]+1

|

必須滿足的是所有的a[j]都必須不小于a[i]}核心程序段46fillchar(f,sizeof(f),1);best:=1;for

i:=2

to

n

dobeginfor

j:=1

toi-1

doif

(a[j]>=a[i])

and

(f[j]+1>f[i])

then

f[i]:=f[j]+1;if

best<f[i]

then

best:=f[i];end;write(best);逆推求解47如何進(jìn)行？問(wèn)題6：乘積最大48

在一次數(shù)學(xué)智力競(jìng)賽中，主持人給所有參加活動(dòng)的選手出了一道題目：設(shè)有一個(gè)長(zhǎng)度為N的數(shù)字串，要求選手使用M個(gè)乘號(hào)將它分成M＋1部分，求出一種分法，使得這M+1個(gè)部分的乘積最大。同時(shí)，為了幫助選手能夠理解題意，主持人還舉了如下一個(gè)例子：有一個(gè)數(shù)字串：312，當(dāng)N=3,M=1時(shí)有二種分法：（1）3×12＝36；（2）31×2＝62這時(shí)，符合題意要求的結(jié)果是：31×2＝62?，F(xiàn)在要求設(shè)計(jì)一個(gè)程序，以求得正確的答案。輸入文件product.in第一行包含二個(gè)整數(shù)，分別表示N，M（2<=N<=10，1<=M<=5），第二行是一個(gè)長(zhǎng)度為N的數(shù)字串。輸出文件product.out包含一行一個(gè)自然數(shù)，表示求得的最大乘積。輸入和輸出49product.in4

21231product.out62算法分析501、本來(lái)用搜索也可2、n，m擴(kuò)大時(shí)，必須用動(dòng)態(tài)規(guī)劃3、用f[I,j]表示在前i個(gè)數(shù)字中插入j個(gè)乘號(hào)可以獲得的最大值，那么f[n,m]就是問(wèn)題的最優(yōu)解。特殊到一般抽象出轉(zhuǎn)移方程511、顯然f[I,j]這個(gè)最優(yōu)解肯定是在下列情形中產(chǎn)生的：f[j,j-1]*Aj+1…Aif[j+1,j-1]*Aj+2…Ai……f[i-1,j-1]*Ai2、提煉出初步的轉(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ù)。52勾畫(huà)出初步的代碼53For

i:=1

to

n

doFor

j:=0

to

m

doIfj<=i-1

thenFor

i1:=j

toi-1

doIf

f[I,j]<f[i1,j-1]*num(a[i1+1]…a[i]);*開(kāi)始時(shí)所有的f[I,j]初始化為0思考541、有沒(méi)有發(fā)現(xiàn)算法中的漏洞？2、分析邊界、確定遞推初始值中完善算法完善后的算法55所有的f[I,j]初始化為0；for

i:=1

ton-m

dof[I,0]:=num(a[1]…a[i]);For

i:=2

to

n

doFor

j:=1

to

m

doIfj<=i-1

thenFor

i1:=j

toi-1

doIf

f[I,j]<f[i1,j-1]*num(a[i1+1]…a[i]);注意的細(xì)節(jié)56實(shí)際編程時(shí)還須使用高精度算法，由于這里著重介紹動(dòng)態(tài)規(guī)劃，故本過(guò)程省略。問(wèn)題7：校慶100周年57在柯中建校100周年之際，學(xué)校決定舉辦校慶活動(dòng)，發(fā)出校慶通告和邀請(qǐng)后，學(xué)校收到了k多的祝賀條幅，在把這些條幅掛起來(lái)的時(shí)候，學(xué)校負(fù)責(zé)人要考慮到祝賀單位和個(gè)人的知名度和發(fā)送祝賀的先后順序，覺(jué)得有必要統(tǒng)籌地安排位置來(lái)掛這些條幅。在柯中校門口的正面，有一座氣勢(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è)位置上的效果打了分。最終希望掛條幅的效果分到達(dá)最大。輸入文件aniversary.in第一行包含二個(gè)空格分隔的整數(shù)k和n，分別表示總條幅數(shù)量和總的可掛條幅的數(shù)量。下面一共有k行，每行有n個(gè)空格分隔的整數(shù)，輸入文件第i+1行第j列的整數(shù)表示編號(hào)為i的條幅掛在編號(hào)為j的位置上的效果分（在－50到50之間）。

輸出文件aniversary.out包含一行一個(gè)整數(shù)，表示可能獲得的最大的效果分。58輸入和輸出59aniversary.in3

57

23

-5

-24

165

21

-4

10

23-21

5

-4

-20

20aniversary.out53三要素分析601、橫幅作為階段I2、前i個(gè)橫幅放置所占的前j個(gè)位置作為狀態(tài)3、決策就是第i個(gè)橫幅放置在前j個(gè)位置的哪個(gè)位置上狀態(tài)轉(zhuǎn)移方程61用ans[I,j]表示前i個(gè)橫幅放入前j個(gè)位置，并且第i個(gè)橫幅放置于第j個(gè)位置上的最優(yōu)解。Ans[I,j]=max{ans[i-1,t]+a[I,j]

|

i<=j<=n-(k-i),i-1<=t<=j-1

}