【概述】

動態規劃：解決多階段決策問題的一種方法。實際上就是一種排除重復計算的算法，更具體的說，動態規劃就是用空間換取時間。

多階段決策問題：若一類問題的求解過程可分為若干個互相聯系的階段，在每一個階段都需作出決策，并影響到下一個階段的決策。這類問題的解決，就是要在可以選擇的那些策略間，選一個最優策略，使在預定的標準下達到最好的效果。

階段：將所給求解問題的過程恰當地分成若干個相互聯系的階段，以便于求解，過程不同，階段數就可能不同，描述階段的變量稱“階段變量”。

狀態：描述事物的性質，不同事物有不同的性質，因而用不同的狀態來刻畫。對問題的求解狀態的描述是分階段的。描述狀態的量稱“狀態變量”

決策：一個階段的狀態給定以后，從該狀態演變到下一階段某個狀態的選擇性操作。描述決策的變量稱決策變量。決策變量的范圍稱“允許決策集合”。

無后效性：我們要求狀態具有下面的性質：如果給定某一階段的狀態，則在這一階段以后過程的發展不受這階段以前各段狀態的影響，所有各階段都確定時，整個過程也就確定了。換句話說，過程的每一次實現可以用一個狀態序列表示，這個性質稱為“無后效性”。

策略：由每個階段的決策組成的序列稱為策略。對于每一個實際的多階段決策過程，可供選取的策略有一定的范圍限制，這個范圍稱“允許策略集合”。允許策略集合中達到最優效果的策略稱“最優策略”。

狀態轉移方程：用數學公式描述與階段相關的狀態間的演變規律。是本階段的狀態往往是上一階段狀態和上一階段決策的結果。如果給定了第K階段的狀態Sk以及決策uk(Sk)，則第K+1階段的狀態Sk+1也就完全確定。

【最優性原理】

不論初始狀態和第一步決策是什么，余下的決策相對于前一次決策所產生的新狀態，構成一個最優決策序列。

最優決策序列的子序列，一定是局部最優決策子序列。

包含非局部最優的決策子序列，一定不是最優決策序列。

【無后效性原則】

某階段的狀態一旦確定，則此后過程的演變不再受此前各狀態及決策的影響。

當前狀態是此前歷史的一個完整的總結，此前的歷史只能通過當前的狀態去影響過程未來的演變。

【指導思想】

在做每一步決策時，列出各種可能的局部解。

依據某種判定條件，舍棄那些肯定不能得到最優解的局部解。

以每一步都是最優的來保證全局是最優的。

【基本特征】

問題具有多階段決策的特點。

每一階段都有相應的“狀態”與之對應。

每一階段都面臨一個決策，選擇不同的決策將會導致下一階段不同的狀態。

每一階段的最優解問題可以遞歸地歸結為下一階段各個可能狀態的最優解問題，各子問題與原問題具有完全相同的結構。

【一般解題步驟】

判斷問題是否具有最優子結構性質，若不具備則不能用動態規劃

把問題分成若干個子問題（分階段）

建立狀態轉移方程（遞推公式）

找出邊界條件

將已知邊界值帶入方程

遞推求解

【問題分類】

背包問題：點擊這里

線性 DP：點擊這里

區間 DP：點擊這里

狀壓 DP：點擊這里

數位 DP：點擊這里

樹型 DP：點擊這里

?

總結

以上是生活随笔為你收集整理的动态规划 —— 动态规划概述的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。