動態規劃

出自 MBA智库百科(https://wiki.mbalib.com/)

動態規劃(dynamic programming)

　　動態規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題逐個求解，創立瞭解決這類過程優化問題的新方法——動態規劃。

　　在現實生活中，有一類活動的過程，由於它的特殊性，可將過程分成若幹個互相聯繫的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。因此各個階段決策的選取不能任意確定，它依賴於當前面臨的狀態，又影響以後的發展。當各個階段決策確定後，就組成一個決策序列，因而也就確定了整個過程的一條活動路線。這種把一個問題看做是一個前後關聯具有鏈狀結構的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策最優化問題。每個階段中，都求出本階段的各個初始狀態到過程終點的最短路徑和最短距離，當逆序倒推到過程起點時，便得到了全過程的最短路徑及最短距離，同時附帶得到了一組最優結果。

　　動態規划算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。動態規划算法與分治法類似，其基本思想也是將待求解問題分解成若幹個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重覆計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重覆計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。具體的動態規划算法多種多樣，但它們具有相同的填表格式。

　　多階段決策問題中，各個階段採取的決策，一般來說是與時間有關的，決策依賴於當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，故有“動態”的含義，稱這種解決多階段決策最優化問題的方法為動態規劃方法。

　　動態規劃程式設計是對解最優化問題的一種途徑、一種方法，而不是一種特殊演算法。不象前面所述的那些搜索或數值計算那樣，具有一個標準的數學表達式和明確清晰的解題方法。動態規劃程式設計往往是針對一種最優化問題，由於各種問題的性質不同，確定最優解的條件也互不相同，因而動態規劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態規劃，可以解決各類最優化問題。因此在學習時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創造性的技巧去求解。根據上例分析和動態規劃的基本概念，可以得到動態規劃的基本模型如下：

• (1)確定問題的決策對象。
• (2)對決策過程劃分階段。
• (3)對各階段確定狀態變數。
• (4)根據狀態變數確定費用函數和目標函數。
• (5)建立各階段狀態變數的轉移過程，確定狀態轉移方程。

　　動態規劃發展的早期階段，從簡單邏輯出發給出了所謂最優性原理，然後在最優策略存在的前提下導出基本方程，再由這個方程求解最優策略。後來在動態規劃的應用過程中發現，最優性原理不是對任何決策過程普遍成立，它與基本方程不是無條件等價，二者之間也不存在任何確定的蘊含關係。基本方程在動態規劃中起著更為本質的作用。

　　對於初始狀態，策略是最優策略的充要條件是對於任意的k,,有

　　若是最優策略，則對於任意的k,1<k<n，它的子策略對於由x₁和確定的以為起點的第k到n後部子過程而言，也是最優策略。

　　上述推論稱為最優化原理，它給出了最優策略的必要條件，通常略述為：不論過去的狀態和決策如何，對於前面的決策形成的當前的狀態而言，餘下的各個決策必定構成最優策略。

　　根據基本定理的推論可以得到動態規劃的基本方程：

　　(1)

　　其中f_{n + 1}(x_{n + 1}) = δ(x_{n + 1})是決策過程的終端條件，δ為一個已知函數。當x_{n + 1}只取固定的狀態時稱固定終端；當x_{n + 1}可在終端集合X_{n + 1}中變動時稱自由終端。最終要求的最優指標函數滿足(2)式：

　　(2)

　　(1)式是一個遞歸公式，如果目標狀態確定，當然可以直接利用該公式遞歸求出最優值（這種遞歸方法將在後文介紹，稱作備忘錄法），但是一般在實際應用中我們通常將該遞歸公式改為遞推公式求解，這樣一般效率會更高一些。

　　任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動態規劃也並不是萬能的。適用動態規劃的問題必須滿足最優化原理和無後效性。

• 1.最優化原理（最優子結構性質）
  • 最優化原理可這樣闡述：一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最優策略。簡而言之，一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。
• 2.無後向性
  • 將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策，而只能通過當前的這個狀態。換句話說，每個狀態都是過去歷史的一個完整總結。這就是無後向性，又稱為無後效性。
• 3.子問題的重疊性
  • 動態規劃將原來具有指數級複雜度的搜索演算法改進成了具有多項式時間的演算法。其中的關鍵在於解決冗餘，這是動態規划算法的根本目的。

　　動態規劃實質上是一種以空間換時間的技術，它在實現的過程中，不得不存儲產生過程中的各種狀態，所以它的空間複雜度要大於其它的演算法。

　　在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態規劃方法比用其它方法求解更為方便。

動態規劃應用的歷史事件

• 1956年，C·龐特裡雅金提出了最優控制的極大值原理，1957年R·貝爾曼創立了動態規劃方法，這些方法首先提出了用目標函數指標來設計控制系統的思想，並能解訣非線性和時變系統的設計問題。
• 1969年,Merton對在完全市場中,服票價格過程服從擴散過程,股票無紅利,投資者也無非資本利得且效用函數為常數相對風險厭惡、常數絕對風險厭惡等嚴格條件下,將動態規劃方法運用於最優投資與消費選擇策略的求解,給出了連續時間下兩類資產的最優投資與消費問題的解決辦法。
• 1969,1971年,Merton最早將動態規劃方法運用到最優投資與消費問題的求解,以後的許多學者都運用了此方法。
• 1973年,Johnson等人把動態規劃方法和模擬技術結合起來使用,確定聯台運用系統的工程規模取得了成功。
• 1974年HuPpe產,採用動態規劃方法來規劃氣田的生產。
• 1982年,曾賽星、李壽聲採用動態規劃方法確定內蒙古河套灌區各種作物的灌水定額及灌水次數。
• 1988年黃強把模糊動態規劃方法用於求解水電站水庫長期優化調度問題，較隨機動態規劃法簡便，計算速度快。
• 1989年，曾賽星、李壽聲等針對內蒙古河套灌區永聯試區的具體情況，運用大系統分解協調方法建立了灌區優化灌溉制度及地面水、地下水聯合運用的譜系模型，模型中第一層子系統優化採用動態規劃方法確定各種作物的灌溉制度。
• 1989年,曾樹星等在內蒙古河套地區水資源優化調度中,採用動態規劃方法確定各種作物的灌水定額及灌水次數。
• 1991年，林學鈦等人在對河南平頂山市地表水與地下水的聯合管理研究中，運用動態規劃方法對白龜山水庫進行了優化調度。

　　應用動態規劃解決問題，在有了基本的思路之後，一般來說，演算法實現是比較好考慮的。但有時也會遇到一些問題，而使演算法難以實現。動態規劃思想設計的演算法從整體上來看基本都是按照得出的遞推關係式進行遞推，這種遞推相對於電腦來說，只要設計得當，效率往往是比較高的，這樣在時間上溢出的可能性不大，而相反地，動態規劃需要很大的空間以存儲中間產生的結果，這樣可以使包含同一個子問題的所有問題共用一個子問題解，從而體現動態規劃的優越性，但這是以犧牲空間為代價的，為了有效地訪問已有結果，數據也不易壓縮存儲，因而空間矛盾是比較突出的。另一方面，動態規劃的高時效性往往要通過大的測試數據體現出來（以與搜索作比較），因而，對於大規模的問題如何在基本不影響運行速度的條件下，解決空間溢出的問題，是動態規劃解決問題時一個普遍會遇到的問題。

　　對於這個問題，可以考慮從以下一些方面去嘗試：

　　一個思考方向是儘可能少占用空間。如從結點的數據結構上考慮，僅僅存儲必不可少的內容，以及數據存儲範圍上精打細算(按位存儲、壓縮存儲等)。當然這要因問題而異，進行分析。另外，在實現動態規劃時，一個我們經常採用的方法是用一個與結點數一樣多的數組來存儲每一步的決策，這對於倒推求得一種實現最優解的方法是十分方便的，而且處理速度也有一些提高。但是在記憶體空間緊張的情況下，我們就應該抓住問題的主要矛盾。省去這個存儲決策的數組，而改成在從最優解逐級倒推時，再計算一次，選擇某個可能達到這個值的上一階段的狀態，直到推出結果為止。這樣做，在程式編寫上比上一種做法稍微多花一點時間，運行的時效也可能會有一些(但往往很小)的下降，但卻換來了很多的空間。因而這種思想在處理某些問題時，是很有意義的。

　　但有時，即使採用這樣的方法也會發現空間溢出的問題。這時就要分析，這些保留下來的數據是否有必要同時存在於記憶體之中。因為有很多問題，動態規劃遞推在處理後面的內容時，前面比較遠處的內容實際上是用不著的。對於這類問題，在已經確信不會再被使用的數據上覆蓋數據，從而使空間得以重覆利用，如果能有效地使用這一手段，對於相當大規模的問題，空間也不至於溢出（為了求出最優方案，保留每一步的決策仍是必要的，這同樣需要空間）。

　　一般地說，這種方法可以通過兩種思路來實現：一種是遞推結果僅使用Data1和Data2這樣兩個數組，每次將Data1作為上一階段，推得Data2數組，然後，將Data2通過複製覆蓋到Data1之上，如此反覆，即可推得最終結果。這種做法有一個局限性，就是對於遞推與前面若幹階段相關的問題，這種做法就比較麻煩；而且，每遞推一級，就需要複製很多的內容，與前面多個階段相關的問題影響更大。另外一種實現方法是，對於一個可能與前N個階段相關的問題，建立數組Data[0..N]，其中各項為最近N各階段的保存數據。這樣不採用這種記憶體節約方式時對於階段k的訪問只要對應成對數組Data中下標為kmod(N+1)的單元的訪問就可以了。這種處理方法對於程式修改的代碼很少，速度幾乎不受影響，而且需要保留不同的階段數也都能很容易實現。

　　當採用以上方法仍無法解決記憶體問題時，也可以採用對記憶體的動態申請來使絕大多數情況能有效出解。而且，使用動態記憶體還有一點好處，就是在重覆使用記憶體而進行交換時，可以只對指針進行交換，而不複製數據，這在實踐中也是十分有效的。]