新聞詳情

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

發(fā)表時間：2021-03-09 16:21

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

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

他們的概念到處都是，我就不多說了，我只說說我對他們的理解：

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

下面舉個例子：

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

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

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

下面在說說我對動態(tài)規(guī)劃的另外一個理解：

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

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

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

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

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

無后效性

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

什么是無后效性呢？

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

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

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

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

三，動態(tài)規(guī)劃解決問題的一般思路。