有關動態(tài)規(guī)劃的一篇小論文

1、動態(tài)規(guī)劃Dynamic Programmingby Starfish【摘要】本文介紹了動態(tài)規(guī)劃的基本思想和基本步驟,通過實例研究了利用動態(tài)規(guī)劃設計算法的具體途徑,討論了動態(tài)規(guī)劃的一些實現(xiàn)技巧,并將動態(tài)規(guī)劃和其他一些算法作了比較,最后還簡單介紹了動態(tài)規(guī)劃的數(shù)學理論基礎和當前最新的研究成果。(說明:這是我中學時候寫的一篇小論文,因為公式和圖比較多,為了能在bbs上貼出來做了不少刪節(jié)【目錄】一。引言二。動態(tài)規(guī)劃的基本思想三。動態(tài)規(guī)劃算法的基本步驟四。動態(tài)規(guī)劃的適用條件五。動態(tài)規(guī)劃的實例分析六。動態(tài)規(guī)劃的技巧階段的劃分和狀態(tài)的表示七。動態(tài)規(guī)劃實現(xiàn)中的問題八。動態(tài)規(guī)劃與其他算法的比較九。動態(tài)規(guī)劃的理論模

2、型一。引言化原理(principle of optimality,把多階段過程轉化為一系列單階段問題,逐個求解,創(chuàng)立了解決這類過程優(yōu)化問題的新方法動態(tài)規(guī)劃。1957年出版了他的名著Dynamic Programming,這是該領域的第一本著作。動態(tài)規(guī)劃問世以來,在經濟管理、生產調度、工程技術和最優(yōu)控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題,用動態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題,但是一些與時間無關的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃,只要人為地引進時間因素,把它視為多階段決策過程,也可以用動

3、態(tài)規(guī)劃方法方便地求解。二。動態(tài)規(guī)劃的基本思想一般來說,只要問題可以劃分成規(guī)模更小的子問題,并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解(即滿足最優(yōu)子化原理,則可以考慮用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃的實質是分治思想和解決冗余,因此,動態(tài)規(guī)劃是一種將問題實例分解為更小的、相似的子問題,并存儲子問題的解而避免計算重復的子問題,以解決最優(yōu)化問題的算法策略。由此可知,動態(tài)規(guī)劃法與分治法和貪心法類似,它們都是將問題實例歸納為更小的、相似的子問題,并通過求解子問題產生一個全局最優(yōu)解。其中貪心法的當前選擇可能要依賴已經作出的所有選擇,但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下,一步一步地作出貪心選擇;而分治

4、法中的各個子問題是獨立的(即不包含公共的子子問題,因此一旦遞歸地求出各子問題的解后,便可自下而上地將子問題的解合并成問題的解。但不足的是,如果當前選擇可能要依賴子問題的解時,則難以通過局部的貪心策略達到全局最優(yōu)解;如果各子問題是不獨立的,則分治法要做許多不必要的工作,重復地解公共的子問題。解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應用于最優(yōu)化問題,這類問題會有多種可能的解,每個解都有一個值,而動態(tài)規(guī)劃找出其中最優(yōu)(最大或最小值的解。若存在若干個取最優(yōu)值的解的話,它只取其中的一個。在求解過程中,該方法也是通過求解局部子問題的解達到全局最優(yōu)解,但與分治法和貪心法不同的是,動態(tài)規(guī)劃允許這些子問題不

5、獨立,(亦即各子問題可包含公共的子子問題也允許其通過自身子問題的解作出選擇,該方法對每一個子問題只解一次,并將結果保存起來,避免每次碰到時都要重復計算。因此,動態(tài)規(guī)劃法所針對的問題有一個顯著的特征,即它所對應的子問題樹中的子問題呈現(xiàn)大量的重復。動態(tài)規(guī)劃法的關鍵就在于,對于重復出現(xiàn)的子問題,只在第一次遇到時加以求解,并把答案保存起來,讓以后再遇到時直接引用,不必重新求解。三。動態(tài)規(guī)劃算法的基本步驟設計一個標準的動態(tài)規(guī)劃算法,通?？砂匆韵聨讉€步驟進行:1。劃分階段:按照問題的時間或空間特征,把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的(即無后向性,否則問題就無法用動態(tài)規(guī)劃求解

6、。2。選擇狀態(tài):將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當然,狀態(tài)的選擇要滿足無后效性。確定決策并寫出狀態(tài)轉移方程:之所以把這兩步放在一起,是因為決策和狀態(tài)轉移有著天然的聯(lián)系,狀態(tài)轉移就是根據(jù)上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。所以,如果我們確定了決策,狀態(tài)轉移方程也就寫出來了。但事實上,我們常常是反過來做,根據(jù)相鄰兩段的各狀態(tài)之間的關系來確定決策。3。寫出規(guī)劃方程(包括邊界條件:動態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達式。一般說來,只要階段、狀態(tài)、決策和狀態(tài)轉移確定了,這一步還是比較簡單的。動態(tài)規(guī)劃的主要難點在于理論上的設計,一旦設計完成,實現(xiàn)部分就會非常簡單

7、。根據(jù)動態(tài)規(guī)劃的基本方程可以直接遞歸計算最優(yōu)值,但是一般將其改為遞推計算,實現(xiàn)的大體上的框架如下:標準動態(tài)規(guī)劃的基本框架對fn+1(xn+1初始化; 處理邊界條件for k n downto 1 dofor 每一個xkXk dofor 每一個ukUk(xkdo fk(xk 一個極值或-xk+1 Tk(xk,uk 狀態(tài)轉移方程t (fk+1(xk+1, vk(xk,uk基本方程(9式if t比fk(xk更優(yōu)then fk(xk t 計算fk(xk的最優(yōu)值t 一個極值或-for 每一個x1X1do if f1(x1比t更優(yōu)then t f1(x1 按照10式求出最優(yōu)指標輸出t;但是,實際應用當中經

8、常不顯式地按照上面步驟設計動態(tài)規(guī)劃,而是按以下幾個步驟進行:1。分析最優(yōu)解的性質,并刻劃其結構特征。2。遞歸地定義最優(yōu)值。3。以自底向上的方式或自頂向下的記憶化方法(備忘錄法計算出最優(yōu)值。4。根據(jù)計算最優(yōu)值時得到的信息,構造一個最優(yōu)解。步驟(1-(3是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形,步驟(4 可以省略,若需要求出問題的一個最優(yōu)解,則必須執(zhí)行步驟(4。此時,在步驟(3中計算最優(yōu)值時,通常需記錄更多的信息,以便在步驟(4中,根據(jù)所記錄的信息,快速地構造出一個最優(yōu)解。四。動態(tài)規(guī)劃的適用條件任何思想方法都有一定的局限性,超出了特定條件,它就失去了作用。同樣,動態(tài)規(guī)劃也并不是萬能的。適

9、用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。1.最優(yōu)化原理(最優(yōu)子結構性質最優(yōu)化原理可這樣闡述:一個最優(yōu)化策略具有這樣的性質,不論過去狀態(tài)和決策如何,對前面的決策所形成的狀態(tài)而言,余下的諸決策必須構成最優(yōu)策略。簡而言之,一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結構性質。例如圖2中,若路線I和J是A到C的最優(yōu)路徑,則根據(jù)最優(yōu)化原理,路線J必是從B到C的最優(yōu)路線。這可用反證法證明:假設有另一路徑J'是B到C的最優(yōu)路徑,則A到C 的路線取I和J'比I和J更優(yōu),矛盾。從而證明J'必是B到C的最優(yōu)路徑。最優(yōu)化原理是動態(tài)規(guī)劃的基礎,任何問題,如果失

10、去了最優(yōu)化原理的支持,就不可能用動態(tài)規(guī)劃方法計算。動態(tài)規(guī)劃的最優(yōu)化理在其指標函數(shù)的可分離性和單調性中得到體現(xiàn)。根據(jù)最優(yōu)化原理導出的動態(tài)規(guī)劃基本方程是解決一切動態(tài)規(guī)劃問題的基本方法。2.無后向性將各階段按照一定的次序排列好之后,對于某個給定的階段狀態(tài),它以前各階段的狀態(tài)無法直接影響它未來的決策,而只能通過當前的這個狀態(tài)。換句話說,每個狀態(tài)都是過去歷史的一個完整總結。這就是無后向性,又稱為無后效性。有些問題乍一看好像有后向性,但如果按照某種合理的方式重新劃分階段,就可以發(fā)現(xiàn)其本質上是無后向性的,所以關鍵是階段的合理劃分,這一點將在動態(tài)規(guī)劃的技巧中詳細闡述。3.子問題的重疊性動態(tài)規(guī)劃可以將原來具有指

11、數(shù)級復雜度的搜索算法改進成具有多項式時間的算法。其中的關鍵在于解決冗余,這是動態(tài)規(guī)劃算法的根本目的。動態(tài)規(guī)劃實質上是一種以空間換時間的技術,它在實現(xiàn)的過程中,不得不存儲產生過程中的各種狀態(tài),所以它的空間復雜度要大于其它的算法。以Bitonic旅行路線問題為例,這個問題也可以用搜索算法來解決。動態(tài)規(guī)劃的時間復雜度為O(n2,搜索算法的時間復雜度為O(n! ,但從空間復雜度來看,動態(tài)規(guī)劃算法為O(n2,而搜索算法為O(n,搜索算法反而優(yōu)于動態(tài)規(guī)劃算法。選擇動態(tài)規(guī)劃算法是因為動態(tài)規(guī)劃算法在空間上可以承受,而搜索算法在時間上卻無法承受,所以我們舍空間而取時間。設原問題的規(guī)模為n,容易看出,當子問題樹中

12、的子問題總數(shù)是n的超多項式函數(shù),而不同的子問題數(shù)只是n的多項式函數(shù)時,動態(tài)規(guī)劃法顯得特別有意義,此時動態(tài)規(guī)劃法具有線性時間復雜性。所以,能夠用動態(tài)規(guī)劃解決的問題還有一個顯著特征:子問題的重疊性。這個性質并不是動態(tài)規(guī)劃適用的必要條件,但是如果該性質無法滿足,動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢。五。動態(tài)規(guī)劃的實例分析(因為圖較多,略六。動態(tài)規(guī)劃的技巧階段的劃分和狀態(tài)的表示在動態(tài)規(guī)劃的設計過程中,階段的劃分和狀態(tài)的表示是非常重要的兩步,這兩步會直接影響該問題的計算復雜性,有時候階段劃分或狀態(tài)表示的不合理還會使得動態(tài)規(guī)劃法不適用。(下面的幾個例子圖較多,這里從略有很多的多階段決策問題都有著不止一種

13、的階段劃分方法,因而往往就有不止一種的規(guī)劃方法。有時各種方法所產生的效果是差不多的,但更多的時候,就像我們的例子一樣,兩種方法會在某個方面有些區(qū)別。所以,在用動態(tài)規(guī)劃解題的時候,可以多想一想是否有其它的解法。對于不同的解法,要注意比較,好的算法好在哪里,差一點的算法差在哪里。從各種不同算法的比較中,我們可以更深刻地領會動態(tài)規(guī)劃的構思技巧。七。動態(tài)規(guī)劃實現(xiàn)中的問題應用動態(tài)規(guī)劃解決問題,在有了基本的思路之后,一般來說,算法實現(xiàn)是比較好考慮的。但有時也會遇到一些問題,而使算法難以實現(xiàn)。動態(tài)規(guī)劃思想設計的算法從整體上來看基本都是按照得出的遞推關系式進行遞推,這種遞推相對于計算機來說,只要設計得當,效率

14、往往是比較高的,這樣在時間上溢出的可能性不大,而相反地,動態(tài)規(guī)劃需要很大的空間以存儲中間產生的結果,這樣可以使包含同一個子問題的所有問題共用一個子問題解,從而體現(xiàn)動態(tài)規(guī)劃的優(yōu)越性,但這是以犧牲空間為代價的,為了有效地訪問已有結果,數(shù)據(jù)也不易壓縮存儲,因而空間矛盾是比較突出的。另一方面,動態(tài)規(guī)劃的高時效性往往要通過大的測試數(shù)據(jù)體現(xiàn)出來(以與搜索作比較,因而,對于大規(guī)模的問題如何在基本不影響運行速度的條件下,解決空間溢出的問題,是動態(tài)規(guī)劃解決問題時一個普遍會遇到的問題。對于這個問題,可以考慮從以下一些方面去嘗試:一個思考方向是盡可能少占用空間。如從結點的數(shù)據(jù)結構上考慮,僅僅存儲必不可少的內容,以及

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

16、用這樣的方法也會發(fā)現(xiàn)空間溢出的問題.這時就要分析,這些保留 下來的數(shù)據(jù)是否有必要同時存在于內存之中.因為有很多問題,動態(tài)規(guī)劃遞推在處 理后面的內容時,前面比較遠處的內容實際上是用不著的.對于這類問題,在已經 確信不會再被使用的數(shù)據(jù)上覆蓋數(shù)據(jù),從而使空間得以重復利用,如果能有效地使 用這一手段,對于相當大規(guī)模的問題,空間也不至于溢出(為了求出最優(yōu)方案,保 留每一步的決策仍是必要的,這同樣需要空間 . 一般地說,這種方法可以通過兩種思路來實現(xiàn):一種是遞推結果僅使用 Data1 和 Data2 這樣兩個數(shù)組,每次將 Data1 作為上一階段,推得 Data2 數(shù)組,然后,將 Data2 通過復制覆蓋

17、到 Data1 之上,如此反復,即可推得最終結果.這種做法有一個 局限性,就是對于遞推與前面若干階段相關的問題,這種做法就比較麻煩;而且, 每遞推一級,就需要復制很多的內容,與前面多個階段相關的問題影響更大.另外 一種實現(xiàn)方法是,對于一個可能與前 N 個階段相關的問題,建立數(shù)組 Data0.N, 其中各項為最近 N 各階段的保存數(shù)據(jù).這樣不采用這種內存節(jié)約方式時對于階段 k 的 訪問只要對應成對數(shù)組 Data 中下標為 k mod (N+1的單元的訪問就可以了.這種處 理方法對于程序修改的代碼很少,速度幾乎不受影響,而且需要保留不同的階段數(shù) 也都能很容易實現(xiàn). 當采用以上方法仍無法解決內存問題時,也可以采用對內存的動態(tài)申請來使絕大多 數(shù)情況能有效出解.而且,使用動態(tài)內存還有一點好處,就是在重復使用內存而進 行交換時,可以只對指針進行交換,而不復制數(shù)據(jù),這在實踐中也是十分有效的. 八.動態(tài)規(guī)劃與其他算法的比較 動態(tài)規(guī)劃與其說是一種算法,不如說是一種算法設計的策略,他的基本思想體現(xiàn)于 許多其它算法之中.下面我們通過比較動態(tài)規(guī)劃和其他的一些算法之間的相互聯(lián)系 ,來深入理解動態(tài)規(guī)劃的基本思想. 1.動態(tài)規(guī)劃與靜態(tài)規(guī)劃某些情況下可以相互轉化 2.動態(tài)規(guī)劃