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

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

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

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

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

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

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

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

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

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

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

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

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

對(duì)于這個(gè)問題，可以考慮從以下一些方面去嘗試：

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

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

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

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