動(dòng)態(tài)規(guī)劃的特點(diǎn)及其應(yīng)用

1、IOI2000集訓(xùn)隊(duì)論文動(dòng)態(tài)規(guī)劃的特點(diǎn)及其應(yīng)用張辰第1頁(yè)共30頁(yè)動(dòng)態(tài)規(guī)劃的特點(diǎn)及其應(yīng)用安徽張辰目錄(點(diǎn)擊進(jìn)入)【關(guān)鍵詞】【摘要】【正文】1動(dòng)態(tài)規(guī)劃的本質(zhì)1.1多階段決策問(wèn)題1.2階段與狀態(tài)1.3決策和策略1.4最優(yōu)化原理與無(wú)后效性1.5最優(yōu)指標(biāo)函數(shù)和規(guī)劃方程2動(dòng)態(tài)規(guī)劃的設(shè)計(jì)與實(shí)現(xiàn)2.1動(dòng)態(tài)規(guī)劃的多樣性2.2動(dòng)態(tài)規(guī)劃的模式性2.3動(dòng)態(tài)規(guī)劃的技巧性3動(dòng)態(tài)規(guī)劃與一些算法的比較3.1動(dòng)態(tài)規(guī)劃與遞推3.2動(dòng)態(tài)規(guī)劃與搜索3.3動(dòng)態(tài)規(guī)劃與網(wǎng)絡(luò)流4結(jié)語(yǔ)

2、【附錄：部分試題與源程序】1.“花店櫥窗布置問(wèn)題”試題2.“釘子與小球”試題3.例2“花店櫥窗布置問(wèn)題”方法1的源程序4.例2“花店櫥窗布置問(wèn)題”方法2的源程序5.例3“街道問(wèn)題”的擴(kuò)展6.例4“mod4最優(yōu)路徑問(wèn)題”的源程序7.例5“釘子與小球”的源程序8.例6的源程序“N個(gè)人的街道問(wèn)題”【參考文獻(xiàn)】IOI2000集訓(xùn)隊(duì)論文動(dòng)態(tài)規(guī)劃的特點(diǎn)及其應(yīng)用張辰第3頁(yè)共30頁(yè)[例1]多段圖中的最短路徑問(wèn)題：在下圖中找出從A1到D1的最短路徑。仔細(xì)

3、觀察這個(gè)圖不難發(fā)現(xiàn)，它有一個(gè)特點(diǎn)。我們將圖中的點(diǎn)分為四類(lèi)（圖中的A、B、C、D），那么圖中所有的邊都處于相鄰的兩類(lèi)點(diǎn)之間，并且都從前一類(lèi)點(diǎn)指向后一類(lèi)點(diǎn)。這樣，圖中的邊就被分成了三類(lèi)（A?B、B?C、C?D）。我們需要從每一類(lèi)中選出一條邊來(lái)，組成從A1到D1的一條路徑，并且這條路徑是所有這樣的路徑中的最短者。從上面的這個(gè)例子中，我們可以大概地了解到什么是多階段決策問(wèn)題。更精確的定義如下：多階段決策過(guò)程，是指這樣的一類(lèi)特殊的活動(dòng)過(guò)程，問(wèn)題可

4、以按時(shí)間順序分解成若干相互聯(lián)系的階段，在每一個(gè)階段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列[1]。要使整個(gè)活動(dòng)的總體效果達(dá)到最優(yōu)的問(wèn)題，稱(chēng)為多階段決策問(wèn)題多階段決策問(wèn)題。從上述的定義中，我們可以明顯地看出，這類(lèi)問(wèn)題有兩個(gè)要素。一個(gè)是階段，一個(gè)是決策。1.2階段與狀態(tài)階段：階段：將所給問(wèn)題的過(guò)程，按時(shí)間或空間特征分解成若干相互聯(lián)系的階段，以便按次序去求每階段的解。常用字母k表示階段變量。[1]階段是問(wèn)題的屬性。多階段決策問(wèn)題中通常存在著

5、若干個(gè)階段，如上面的例子，就有A、B、C、D這四個(gè)階段。在一般情況下，階段是和時(shí)間有關(guān)的；但是在很多問(wèn)題（我的感覺(jué)，特別是信息學(xué)問(wèn)題）中，階段和時(shí)間是無(wú)關(guān)的。從階段的定義中，可以看出階段的兩個(gè)特點(diǎn)，一是“相互聯(lián)系”，二是“次序”。階段之間是怎樣相互聯(lián)系的？就是通過(guò)狀態(tài)和狀態(tài)轉(zhuǎn)移。狀態(tài)：狀態(tài)：各階段開(kāi)始時(shí)的客觀條件叫做狀態(tài)。描述各階段狀態(tài)的變量稱(chēng)為狀態(tài)變量，常用sk表示第k階段的狀態(tài)變量，狀態(tài)變量sk的取值集合稱(chēng)為狀態(tài)集合，用Sk表示。[