動(dòng)態(tài)規(guī)劃經(jīng)典教程 ——第一節(jié)動(dòng)態(tài)規(guī)劃基本概念

第一節(jié)動(dòng)態(tài)規(guī)劃基本概念

一，動(dòng)態(tài)規(guī)劃三要素：階段，狀態(tài)，決策。

他們的概念到處都是，我就不多說(shuō)了，我只說(shuō)說(shuō)我對(duì)他們的理解：

如果把動(dòng)態(tài)規(guī)劃的求解過(guò)程看成一個(gè)工廠的生產(chǎn)線，階段就是生產(chǎn)某個(gè)商品的不同的環(huán)節(jié)，狀態(tài)就是工件當(dāng)前的形態(tài)，決策就是對(duì)工件的操作。顯然不同階段是對(duì)產(chǎn)品的一個(gè)前面各個(gè)狀態(tài)的小結(jié)，有一個(gè)個(gè)的小結(jié)構(gòu)成了最終的整個(gè)生產(chǎn)線。每個(gè)狀態(tài)間又有關(guān)聯(lián)（下一個(gè)狀態(tài)是由上一個(gè)狀態(tài)做了某個(gè)決策后產(chǎn)生的）。

下面舉個(gè)例子：

要生產(chǎn)一批雪糕，在這個(gè)過(guò)程中要分好多環(huán)節(jié)：購(gòu)買(mǎi)牛奶，對(duì)牛奶提純處理，放入工廠加工，加工后的商品要包裝，包裝后就去銷(xiāo)售……，這樣沒(méi)個(gè)環(huán)節(jié)就可以看做是一個(gè)階段；產(chǎn)品在不同的時(shí)候有不同的狀態(tài)，剛開(kāi)始時(shí)只是白白的牛奶，進(jìn)入生產(chǎn)后做成了各種造型，從冷凍庫(kù)拿出來(lái)后就變成雪糕（由液態(tài)變成固態(tài)=_=||）。每個(gè)形態(tài)就是一個(gè)狀態(tài)，那從液態(tài)變成固態(tài)經(jīng)過(guò)了冰凍這一操作，這個(gè)操作就是一個(gè)決策。

一個(gè)狀態(tài)經(jīng)過(guò)一個(gè)決策變成了另外一個(gè)狀態(tài)，這個(gè)過(guò)程就是狀態(tài)轉(zhuǎn)移，用來(lái)描述狀態(tài)轉(zhuǎn)移的方程就是狀態(tài)轉(zhuǎn)移方程。

經(jīng)過(guò)這個(gè)例子相信大家對(duì)動(dòng)態(tài)規(guī)劃有所了解了吧。

下面在說(shuō)說(shuō)我對(duì)動(dòng)態(tài)規(guī)劃的另外一個(gè)理解：

用圖論知識(shí)理解動(dòng)態(tài)規(guī)劃：把動(dòng)態(tài)規(guī)劃中的狀態(tài)抽象成一個(gè)點(diǎn)，在有直接關(guān)聯(lián)的狀態(tài)間連一條有向邊，狀態(tài)轉(zhuǎn)移的代價(jià)就是邊上的權(quán)。這樣就形成了一個(gè)有向無(wú)環(huán)圖AOE網(wǎng)（為什么無(wú)環(huán)呢？往下看）。對(duì)這個(gè)圖進(jìn)行拓?fù)渑判?，刪除一個(gè)邊后同時(shí)出現(xiàn)入度為0的狀態(tài)在同一階段。這樣對(duì)圖求最優(yōu)路徑就是動(dòng)態(tài)規(guī)劃問(wèn)題的求解。

二，動(dòng)態(tài)規(guī)劃的適用范圍

動(dòng)態(tài)規(guī)劃用于解決多階段決策最優(yōu)化問(wèn)題，但是不是所有的最優(yōu)化問(wèn)題都可以用動(dòng)態(tài)規(guī)劃解答呢？

一般在題目中出現(xiàn)求最優(yōu)解的問(wèn)題就要考慮動(dòng)態(tài)規(guī)劃了，但是否可以用還要滿足兩個(gè)條件：

最優(yōu)子結(jié)構(gòu)（最優(yōu)化原理）

無(wú)后效性

最優(yōu)化原理在下面的最短路徑問(wèn)題中有詳細(xì)的解答；

什么是無(wú)后效性呢？

就是說(shuō)在狀態(tài)i求解時(shí)用到狀態(tài)j而狀態(tài)j就解有用到狀態(tài)k…..狀態(tài)N。

而求狀態(tài)N時(shí)有用到了狀態(tài)i這樣求解狀態(tài)的過(guò)程形成了環(huán)就沒(méi)法用動(dòng)態(tài)規(guī)劃解答了，這也是上面用圖論理解動(dòng)態(tài)規(guī)劃中形成的圖無(wú)環(huán)的原因。

也就是說(shuō)當(dāng)前狀態(tài)是前面狀態(tài)的完美總結(jié)，現(xiàn)在與過(guò)去無(wú)關(guān)。。。

當(dāng)然，有是換一個(gè)劃分狀態(tài)或階段的方法就滿足無(wú)后效性了，這樣的問(wèn)題仍然可以用動(dòng)態(tài)規(guī)劃解。

三，動(dòng)態(tài)規(guī)劃解決問(wèn)題的一般思路。

拿到多階段決策最優(yōu)化問(wèn)題后，第一步要判斷這個(gè)問(wèn)題是否可以用動(dòng)態(tài)規(guī)劃解決，如果不能就要考慮搜索或貪心了。當(dāng)卻定問(wèn)題可以用動(dòng)態(tài)規(guī)劃后，就要用下面介紹的方法解決問(wèn)題了：

（1）模型匹配法：

最先考慮的就是這個(gè)方法了。挖掘問(wèn)題的本質(zhì)，如果發(fā)現(xiàn)問(wèn)題是自己熟悉的某個(gè)基本的模型，就直接套用，但要小心其中的一些小的變動(dòng)，現(xiàn)在考題辦都是基本模型的變形套用時(shí)要小心條件，三思而后行。這些基本模型在先面的分類(lèi)中將一一介紹。

（2）三要素法

仔細(xì)分析問(wèn)題嘗試著確定動(dòng)態(tài)規(guī)劃的三要素，不同問(wèn)題的卻定方向不同：

先確定階段的問(wèn)題：數(shù)塔問(wèn)題，和走路問(wèn)題（詳見(jiàn)解題報(bào)告）

先確定狀態(tài)的問(wèn)題：大多數(shù)都是先確定狀態(tài)的。

先確定決策的問(wèn)題：背包問(wèn)題。（詳見(jiàn)解題報(bào)告）

一般都是先從比較明顯的地方入手，至于怎么知道哪個(gè)明顯就是經(jīng)驗(yàn)問(wèn)題了，多做題就會(huì)發(fā)現(xiàn)。

（3）尋找規(guī)律法：

這個(gè)方法很簡(jiǎn)單，耐心推幾組數(shù)據(jù)后，看他們的規(guī)律，總結(jié)規(guī)律間的共性，有點(diǎn)貪心的意思。

（4）邊界條件法

找到問(wèn)題的邊界條件，然后考慮邊界條件與它的領(lǐng)接狀態(tài)之間的關(guān)系。這個(gè)方法也很起效。

（5）放寬約束和增加約束

這個(gè)思想是在陳啟鋒的論文里看到的，具體內(nèi)容就是給問(wèn)題增加一些條件或刪除一些條件使問(wèn)題變的清晰。