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

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

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

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

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

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