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

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

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

多階段決策問題中，各個階段采取的決策，一般來說是與時間有關(guān)的，決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義，稱這種解決多階段決策最優(yōu)化問題的方法為動態(tài)規(guī)劃方法。

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

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

任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動態(tài)規(guī)劃也并不是萬能的。適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。

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

動態(tài)規(guī)劃實質(zhì)上是一種以空間換時間的技術(shù)，它在實現(xiàn)的過程中，不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以它的空間復雜度要大于其它的算法。

在經(jīng)濟管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。

動態(tài)規(guī)劃應(yīng)用的歷史事件

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

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

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

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

但有時，即使采用這樣的方法也會發(fā)現(xiàn)空間溢出的問題。這時就要分析，這些保留下來的數(shù)據(jù)是否有必要同時存在于內(nèi)存之中。因為有很多問題，動態(tài)規(guī)劃遞推在處理后面的內(nèi)容時，前面比較遠處的內(nèi)容實際上是用不著的。對于這類問題，在已經(jīng)確信不會再被使用的數(shù)據(jù)上覆蓋數(shù)據(jù)，從而使空間得以重復利用，如果能有效地使用這一手段，對于相當大規(guī)模的問題，空間也不至于溢出（為了求出最優(yōu)方案，保留每一步的決策仍是必要的，這同樣需要空間）。

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

當采用以上方法仍無法解決內(nèi)存問題時，也可以采用對內(nèi)存的動態(tài)申請來使絕大多數(shù)情況能有效出解。而且，使用動態(tài)內(nèi)存還有一點好處，就是在重復使用內(nèi)存而進行交換時，可以只對指針進行交換，而不復制數(shù)據(jù)，這在實踐中也是十分有效的。]