動态規劃 --- 算法思想介紹

一.動态規劃的基本概念

動态規劃在五種算法設計方法中難度最大，它建立在最優原則的基礎上.采用動态規劃方法，可以高效地解決許多用貪婪算法或分治法無法解決的問題.動态規劃(dynamic programming)屬運籌學中的規劃論分支，是求解決策過程最優化的數學方法.20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，逐個求解，創立了解決這類過程優化問題的新方法——​​動态規劃​​.

二.動态規劃的适用條件

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

1.最優化原理（最優子結構性質） 一個最優化政策具有這樣的性質，不論過去狀态和決策如何，對前面的決策所形成的狀态而言，餘下的諸決策必須構成最優政策.一個最優化政策的子政策總是最優的.一個問題滿足最優化原理又稱其具有最優子結構性質.

如圖，若路線I和J是A到C的最優路徑，則根據最優化原理，路線J必是從B到C的最優路線. 反證法證明：假設有另一路徑J'是B到C的最優路徑，則A到C的路線取I和J'比I和J更優，沖突.進而證明J'必是B到C的最優路徑. 最優化原理是動态規劃的基礎，任何問題，如果失去了最優化原理的支援，就不可能用動态規劃方法計算.哪些問題滿足最優化原理？ 動态規劃的最優化理在其名額函數的可分離性和單調性中得到展現.根據最優化原理導出的動态規劃基本方程是解決一切動态規劃問題的基本方法.

2.無後向性 将各階段按照一定的次序排列好之後，對于某個給定的階段狀态，它以前各階段的狀态無法直接影響它未來的決策，而隻能通過目前的這個狀态.換句話說，每個狀态都是過去曆史的一個完整總結.這就是無後向性，又稱為無後效性.如果用前面的記号來描述無後向性，就是：對于确定的xk，無論p1,k-1如何，最優子政策pkn*是唯一确定的，這種性質稱為無後向性.

3.子問題的重疊性 動态規劃将一些具有指數級複雜度的搜尋算法改進成了具有多項式時間的算法.其中的關鍵在于解決備援，這是動态規劃算法的根本目的.動态規劃實質上是一種以空間換時間的技術，在實作中往往存儲各種狀态，故空間複雜度大于其它的算法.例如Bitonic旅行路線問題：動态規劃的時間複雜度為O(n2)，搜尋算法的時間複雜度為O(n!) ，但從空間複雜度來看，動态規劃算法為O(n2)，而搜尋算法為O(n) .選擇動态規劃算法是因為動态規劃算法在空間上可以承受，而搜尋算法在時間上卻無法承受，是以我們舍空間而取時間

動态規劃算法與分治法類似，其基本思想也是将待求解問題分解成若幹個子問題.但是經分解得到的子問題往往不是互相獨立的.不同子問題的數目常常隻有多項式量級.在用分治法求解時，有些子問題被重複計算了許多次.

如果能夠儲存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重複計算，進而得到多項式時間算法.

設原問題的規模為n，當子問題樹中的子問題總數是n的超多項式函數，而不同的子問題數隻是n的多項式函數時，動态規劃法顯得特别有意義，此時動态規劃法具有線性時間複雜性.是以，能夠用動态規劃解決的問題還有一個顯著特征：子問題的重疊性.這個性質并不是動态規劃适用的必要條件，但是如果該性質無法滿足，動态規劃算法同其他算法相比就不具備優勢.

三.動态規劃的基本思想:

前面介紹了動态規劃理論，稱為标準動态規劃，因為它具有明顯的階段劃分和狀态轉移特征.這是在研究多階段決策問題時推導出來的，具有嚴格的數學形式，适合用于理論上的分析.在實際應用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段法反而麻煩.一般來說，隻要該問題可以劃分成規模更小的子問題，并且原問題的最優解中包含了子問題的最優解（即滿足最優子化原理），則可以考慮用動态規劃解決.

動态規劃的實質是分治思想和解決備援，是以，動态規劃是一種将問題執行個體分解為更小的、相似的子問題，并存儲子問題的解而避免計算重複的子問題，以解決最優化問題的算法政策. 動态規劃法與分治法和貪心法類似，它們都是将問題執行個體歸納為更小的、相似的子問題，并通過求解子問題産生一個全局最優解.其中貪心法的目前選擇可能要依賴已經作出的所有選擇，但不依賴于有待于做出的選擇和子問題.是以貪心法自頂向下，一步一步地作出貪心選擇；

而分治法中的各個子問題是獨立的 (即不包含公共的子子問題)，是以一旦遞歸地求出各子問題的解後，便可自下而上地将子問題的解合并成問題的解.但不足的是，如果目前選擇可能要依賴子問題的解時，則難以通過局部的貪心政策達到全局最優解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重複地解公共的子問題.

動态規劃法用于最優化問題，這類問題會有多種可能的解，而動态規劃找出其中最優值的解.若存在若幹個取最優值的解的話，它隻取其中的一個.該方法通過求解局部子問題的解達到全局最優解.與分治法和貪心法不同的是，動态規劃允許這些子問題不獨立，(各子問題可包含公共的子子問題) ，該方法對每一個子問題隻解一次，并儲存結果，避免每次碰到時都要重複計算.

動态規劃法所針對的問題的特征：對應的子問題樹中的子問題呈現大量的重複.關鍵：對于重複出現的子問題，隻在第一次遇到時加以求解，并把答案儲存起來，以後再遇到時不必重新求解. 實際應用當中經常不顯式地按照上面步驟設計動态規劃，而是按以下幾個步驟進行：

• 分析最優解的性質，并刻劃其結構特征.
• 遞歸地定義最優值.
• 以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計算出最優值.
• 根據計算最優值時得到的資訊，構造一最優解.

步驟(1)--(3)是基本步驟.在隻需要求出最優值的情形，步驟(4)可以省略.若需要求出問題的一個最優解，則必須執行步驟(4).此時，需要利用在步驟(3)中計算最優值時記錄的許多資訊.