動態(tài)規(guī)劃算法原理及應用

1、動態(tài)規(guī)劃算法 劉興田（浙江工業(yè)大學 計算機學院 軟件工程1205班 201226630512）摘要：動態(tài)規(guī)劃是解決最優(yōu)化問題的基本方法，本文介紹了動態(tài)規(guī)劃的基本思想和基本步驟，并通過幾個實例的分析，研究了利用動態(tài)規(guī)劃設計算法的具體途徑。關鍵詞：動態(tài)規(guī)劃 算法Dynamic Programming Liu xingtian(Zhe Jiang University Of Technology, Computer Science and Technology Campus, Software Engineering 1205 26630512)Abstract: Dynamic Programmi

2、ng is the most effective way to solve the problem of optimization .This dissertation introduce the thinking of Dynamic Programming and the step to using Dynamic Programming ,it also gives some examples to help analysis Dynamic Programming and the specific method to use Dynamic Programming .Key words

3、 : Dynamic Programming , Alsgorithm1.引言 規(guī)劃問題的最終目的就是確定各決策變量的取值，以使目標函數(shù)達到極大或極小。在線性規(guī)劃和非線性規(guī)劃中，決策變量都是以集合的形式被一次性處理的；然而，有時我們也會面對決策變量需分期、分批處理的多階段決策問題。所謂多階段決策問題是指這樣一類活動過程：它可以分解為若干個互相聯(lián)系的階段，在每一階段分別對應著一組可供選取的決策集合；即構成過程的每個階段都需要進行一次決策的決策問題。將各個階段的決策綜合起來構成一個決策序列，稱為一個策略。顯然，由于各個階段選取的決策不同，對應整個過程可以有一系列不同的策略。當過程采取某個具體策略時

4、，相應可以得到一個確定的效果，采取不同的策略，就會得到不同的效果。多階段的決策問題，就是要在所有可能采取的策略中選取一個最優(yōu)的策略，以便得到最佳的效果。動態(tài)規(guī)劃是一種求解多階段決策問題的系統(tǒng)技術，可以說它橫跨整個規(guī)劃領域（線性規(guī)劃和非線性規(guī)劃）。在多階段決策問題中，有些問題對階段的劃分具有明顯的時序性，動態(tài)規(guī)劃的“動態(tài)”二字也由此而得名。動態(tài)規(guī)劃的主要創(chuàng)始人是美國數(shù)學家貝爾曼（Bellman）。20世紀40年代末50年代初，當時在蘭德公司（Rand Corporation）從事研究工作的貝爾曼首先提出了動態(tài)規(guī)劃的概念。1957年貝爾曼發(fā)表了數(shù)篇研究論文，并出版了他的第一部著作動態(tài)規(guī)劃。該著作成

5、為了當時唯一的進一步研究和應用動態(tài)規(guī)劃的理論源泉。在貝爾曼及其助手們致力于發(fā)展和推廣這一技術的同時，其他一些學者也對動態(tài)規(guī)劃的發(fā)展做出了重大的貢獻，其中最值得一提的是愛爾思（Aris）和梅特頓（Mitten）。愛爾思先后于1961年和1964年出版了兩部關于動態(tài)規(guī)劃的著作，并于1964年同尼母霍思爾（Nemhauser）、威爾德（Wild）一道創(chuàng)建了處理分枝、循環(huán)性多階段決策系統(tǒng)的一般性理論。梅特頓提出了許多對動態(tài)規(guī)劃后來發(fā)展有著重要意義的基礎性觀點，并且對明晰動態(tài)規(guī)劃路徑的數(shù)學性質做出了巨大的貢獻。動態(tài)規(guī)劃問世以來，在工程技術、經(jīng)濟管理等社會各個領域都有著廣泛的應用，并且獲得了顯著的效果。在

6、經(jīng)濟管理方面，動態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調度問題、庫存管理問題、排序問題、設備更新問題以及生產(chǎn)過程最優(yōu)控制問題等，是經(jīng)濟管理中一種重要的決策技術。許多規(guī)劃問題用動態(tài)規(guī)劃的方法來處理，常比線性規(guī)劃或非線性規(guī)劃更有效。特別是對于離散的問題，由于解析數(shù)學無法發(fā)揮作用，動態(tài)規(guī)劃便成為了一種非常有用的工具。 動態(tài)規(guī)劃可以按照決策過程的演變是否確定分為確定性動態(tài)規(guī)劃和隨機性動態(tài)規(guī)劃；也可以按照決策變量的取值是否連續(xù)分為連續(xù)性動態(tài)規(guī)劃和離散性動態(tài)規(guī)劃。雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進時

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

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

9、的是，動態(tài)規(guī)劃允許這些子問題不獨立，也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結果保存起來，避免每次碰到時都要重復計算。 因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應的子問題樹中的子問題呈現(xiàn)大量的重復。動態(tài)規(guī)劃法的關鍵就在于，對于重復出現(xiàn)的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。3.動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的數(shù)學描述離不開它的一些基本概念與符號，因此有必要在介紹多階段決策過程的數(shù)學描述的基礎上，系統(tǒng)地介紹動態(tài)規(guī)劃的一些基本概念。3.1多階段決策問題如果一類活動過程可以分為若干個互相聯(lián)系的階段，在每一個階

10、段都需作出決策，一個階段的決策確定以后，常常影響到下一個階段的決策，從而就完全確定了一個過程的活動路線，則稱它為多階段決策問題。各個階段的決策構成一個決策序列，稱為一個策略。每一個階段都有若干個決策可供選擇，因而就有許多策略供我們選取，對應于一個策略可以確定活動的效果，這個效果可以用數(shù)量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個最優(yōu)策略，使在預定的標準下達到最好的效果.3.2動態(tài)規(guī)劃問題中的術語階段：把所給求解問題的過程恰當?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便于求解，過程不同，階段數(shù)就可能不同描述階段的變量稱為階段變量。在多數(shù)情況下，階段變量是離散的，用

11、k表示。此外，也有階段變量是連續(xù)的情形。如果過程可以在任何時刻作出決策，且在任意兩個不同的時刻之間允許有無窮多個決策時，階段變量就是連續(xù)的。狀態(tài)：狀態(tài)表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉移，也稱為不可控因素。在上面的例子中狀態(tài)就是某階段的出發(fā)位置，它既是該階段某路的起點，同時又是前一階段某支路的終點。過程的狀態(tài)通?？梢杂靡粋€或一組數(shù)來描述，稱為狀態(tài)變量。一般，狀態(tài)是離散的，但有時為了方便也將狀態(tài)取成連續(xù)的。當然，在現(xiàn)實生活中，由于變量形式的限制，所有的狀態(tài)都是離散的，但從分析的觀點，有時將狀態(tài)作為連續(xù)的處理將會有很大的好處。此外，狀態(tài)可以有多個分量(多維情形)，因

12、而用向量來代表；而且在每個階段的狀態(tài)維數(shù)可以不同。無后效性：我們要求狀態(tài)具有下面的性質：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時，整個過程也就確定了。換句話說，過程的每一次實現(xiàn)可以用一個狀態(tài)序列表示，在前面的例子中每階段的狀態(tài)是該線路的始點，確定了這些點的序列，整個線路也就完全確定。從某一階段以后的線路開始，當這段的始點給定時，不受以前線路（所通過的點）的影響。狀態(tài)的這個性質意味著過程的歷史只能通過當前的狀態(tài)去影響它的未來的發(fā)展，這個性質稱為無后效性。決策：一個階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個狀態(tài)的一種選擇（行動）稱為決策

13、。在最優(yōu)控制中，也稱為控制。在許多間題中，決策可以自然而然地表示為一個數(shù)或一組數(shù)。不同的決策對應著不同的數(shù)值。描述決策的變量稱決策變量，因狀態(tài)滿足無后效性，故在每個階段選擇決策時只需考慮當前的狀態(tài)而無須考慮過程的歷史。決策變量的范圍稱為允許決策集合。策略：由每個階段的決策組成的序列稱為策略。對于每一個實際的多階段決策過程，可供選取的策略有一定的范圍限制，這個范圍稱為允許策略集合。允許策略集合中達到最優(yōu)效果的策略稱為最優(yōu)策略。給定k階段狀態(tài)變量x(k)的值后，如果這一階段的決策變量一經(jīng)確定，第k+1階段的狀態(tài)變量x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變

14、化而變化，那么可以把這一關系看成(x(k)，u(k)與x(k+1)確定的對應關系，用x(k+1)=Tk(x(k),u(k)表示。這是從k階段到k+1階段的狀態(tài)轉移規(guī)律，稱為狀態(tài)轉移方程。最優(yōu)性原理: 作為整個過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余下的子策略必然構成“最優(yōu)子策略”。4.動態(tài)規(guī)劃求解的基本步驟動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優(yōu)的活動路線)。如圖所示。動態(tài)規(guī)劃的設計都有著一定的模式，一般要經(jīng)歷以下幾個步驟。初始狀態(tài)決策決策

15、決策結束狀態(tài) 動態(tài)規(guī)劃決策過程示意圖(1)劃分階段：，按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。 (2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當然，狀態(tài)的選擇要滿足無后效性。 (3)確定決策并寫出狀態(tài)轉移方程：因為決策和狀態(tài)轉移有著天然的聯(lián)系，狀態(tài)轉移就是根據(jù)上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉移方程也就可寫出。但事實上常常是反過來做，根據(jù)相鄰兩段各狀態(tài)之間的關系來確定決策。 (4)尋找邊界條件：給出的狀態(tài)轉移方程是一個遞推式，需要一

16、個遞推的終止條件或邊界條件。 (5)程序設計實現(xiàn)：動態(tài)規(guī)劃的主要難點在于理論上的設計，一旦設計完成，實現(xiàn)部分就會非常簡單。根據(jù)上述動態(tài)規(guī)劃設計的步驟，可得到大體解題框架如圖所示。 動態(tài)規(guī)劃設計的一般模式圖 上述提供了動態(tài)規(guī)劃方法的一般模式，對于簡單的動態(tài)規(guī)劃問題，可以按部就班地進行動態(tài)規(guī)劃的設計。下面，給出一個利用動態(tài)規(guī)劃方法求解的典型例子。 上圖示出了一個數(shù)字三角形寶塔。數(shù)字三角形中的數(shù)字為不超過100的整數(shù)。現(xiàn)規(guī)定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。 任務一：假設三角形行數(shù)10，鍵盤輸入一個確定的整數(shù)值M，編程確定是否存在一條路徑，使得沿著該路徑所經(jīng)過的數(shù)字的總和恰為M

17、，若存在則給出所有路徑，若不存在，則輸出“NOAnswer!”字樣。 任務二：假設三角形行數(shù)100，編程求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經(jīng)過的數(shù)字的總和最大，輸出最大值。輸人數(shù)據(jù)：由文件輸入數(shù)據(jù)，任務一中文件第一行是三角形的行數(shù)N和整數(shù)值M。以后的N行分別是從最頂層到最底層的每一層中的數(shù)字。任務二中文件數(shù)據(jù)格式同任務一，只是第一行中沒有整數(shù)值M。在例子中任務二的文件數(shù)據(jù)表示如下： 輸入：5 7 輸出： 輸出路徑和最大值 3 8 7 或“No Answer!”字樣。 8 1 0 38 2 7 7 4 810 4 5 2 6 5 2744圖3 數(shù)字三角形 45265【分析】對于這

18、一問題，很容易想到用枚舉的方法去解決，即列舉出所有路徑并記錄每一條路徑所經(jīng)過的數(shù)字總和。然后判斷數(shù)字總和是否等于給定的整數(shù)值M或尋找出最大的數(shù)字總和，這一想法很直觀，而且對于任務一，由于數(shù)字三角形的行數(shù)不大(10)，因此其枚舉量不是很大，應該能夠實現(xiàn)。但對于任務二，如果用枚舉的方法，當三角形的行數(shù)等于100時，其枚舉量之大是可想而知的，顯然，枚舉法對于任務二的求解并不適用。其實，只要對對任務二稍加分析，就可以得出一個結論： 如果得到一條由頂至底的某處的一條最佳路徑，那么對于該路徑上的每一個中間點來說，由頂至該中間點的路徑所經(jīng)過的數(shù)字和也為最大。因此該問題是一個典型的多階段決策最優(yōu)化的問題。算法

19、設計與分析如下： 對于任務一，合理地確認枚舉的方法，可以優(yōu)化問題的解法。由于從塔頂?shù)降讓用看味贾挥袃煞N走法，即左或右。設“0”表示左，“1”表示右，對于層數(shù)為N的數(shù)字塔，從頂?shù)降椎囊环N走法可用一個N-1位的二進制數(shù)表示。如例中二進制數(shù)字串1011，其對應的路徑應該是：8146。這樣就可以用一個Nl位的二進制數(shù)來模擬走法和確定解的范圍。窮舉出從0到2n-1個十進制數(shù)所對應的N-1位二進制串對應的路徑中的數(shù)字總和，判定其是否等于M而求得問題的解。 對于任務二，采用動態(tài)規(guī)劃中的順推解法。按三角形的行劃分階段，若行數(shù)為n，則可把問題看做一個n-1個階段的決策問題。從始點出發(fā)，依順向求出第一階段、第二階

20、段第n1階段中各決策點至始點的最佳路徑，最終求出始點到終點的最佳路徑。 設：fk(Uk)為從第k階段中的點Uk至三角形頂點有一條最佳路徑，該路徑所經(jīng)過的數(shù)字的總和最大，fk(Uk)表示為這個數(shù)字和；由于每一次決策有兩個選擇，或沿左斜線向下，或沿右斜線向下，因此設： Uk1為k-1階段中某點Uk沿左斜線向下的點； Uk2為k-1階段中某點Uk沿右斜線向下的點； dk(Uk1)為k階段中Uk1的數(shù)字；dk(Uk2)為k階段中Uk2的數(shù)字。因而可寫出順推關系式(狀態(tài)轉移方程)為： fk(Uk)=maxfk-1(Uk)+dk(Uk1)，fk-1(Uk)+dk(Uk2)(k=1，2，3，n) f0(U0

21、)0經(jīng)過一次順推，便可分別求出由頂至底N個數(shù)的N條路徑，在這N條路徑所經(jīng)過的N個數(shù)字和中，最大值即為正確答案。5.動態(tài)規(guī)劃的應用實例5.1最短路線問題例1 現(xiàn)有一張地圖，各結點代表城市，兩結點間連線代表道路，線上數(shù)字表示城市間的距離。如圖1所示，試找出從結點A到結點E的最短距離。 我們可以用深度優(yōu)先搜索法來解決此問題，該問題的遞歸式為其中是與v相鄰的節(jié)點的集合，w(v,u)表示從v到u的邊的長度。這個程序的效率如何呢？我們可以看到，每次除了已經(jīng)訪問過的城市外，其他城市都要訪問，所以時間復雜度為O(n!)，這是一個“指數(shù)級”的算法。 首先，我們來觀察一下這個算法。在求從B1到E的最短距離的時候，

22、先求出從C2到E的最短距離；而在求從B2到E的最短距離的時候，又求了一遍從C2到E的最短距離。也就是說，從C2到E的最短距離我們求了兩遍。同樣可以發(fā)現(xiàn)，在求從C1、C2到E的最短距離的過程中，從D1到E的最短距離也被求了兩遍。而在整個程序中，從D1到E的最短距離被求了四遍。如果在求解的過程中，同時將求得的最短距離記錄在案，隨時調用，就可以避免這種情況。于是，可以改進該算法，將每次求出的從v到E的最短距離記錄下來，在算法中遞歸地求MinDistance(v)時先檢查以前是否已經(jīng)求過了MinDistance(v)，如果求過了則不用重新求一遍，只要查找以前的記錄就可以了。這樣，由于所有的點有n個，因

23、此不同的狀態(tài)數(shù)目有n個，該算法的數(shù)量級為O(n)。更進一步，可以將這種遞歸改為遞推，這樣可以減少遞歸調用的開銷。5.2資源分配問題所謂資源分配問題，就是將一定數(shù)量的一種或若干種資源（如原材料、機器設備、資金、勞動力等）恰當?shù)胤峙浣o若干個使用者，以使資源得到最有效地利用。設有m種資源，總量分別為bi（i = 1,2,m），用于生產(chǎn)n種產(chǎn)品，若用xij代表用于生產(chǎn)第j種產(chǎn)品的第i種資源的數(shù)量（j = 1,2,n），則生產(chǎn)第j種產(chǎn)品的收益是其所獲得的各種資源數(shù)量的函數(shù)，即gj = f（x1j,x2j, xmj）。由于總收益是n種產(chǎn)品收益的和，此問題可用如下靜態(tài)模型加以描述： 若是連續(xù)變量，當 = f

24、（, ）是線性函數(shù)時，該模型是線性規(guī)劃模型；當 = f（, ）是非線性函數(shù)時，該模型是非線性規(guī)劃模型。若是離散變量或（和） = f（, ）是離散函數(shù)時，此模型用線性規(guī)劃或非線性規(guī)劃來求解都將是非常麻煩的。然而在此情況下，由于這類問題的特殊結構，可以將它看成為一個多階段決策問題，并利用動態(tài)規(guī)劃的遞推關系來求解。本例只考慮一維資源的分配問題，設狀態(tài)變量表示分配于從第k個階段至過程最終（第N個階段）的資源數(shù)量，即第k個階段初資源的擁有量；決策變量xk表示第k個階段資源的分配量。于是有狀態(tài)轉移律：允許決策集合：最優(yōu)指標函數(shù)（動態(tài)規(guī)劃的逆序遞推關系式）： 利用這一遞推關系式，最后求得的即為所求問題的最大

25、總收益，下面來看一個具體的例子。例2 某公司擬將500萬元的資本投入所屬的甲、乙、丙三個工廠進行技術改造，各工廠獲得投資后年利潤將有相應的增長，增長額如表7-1所示。試確定500萬元資本的分配方案，以使公司總的年利潤增長額最大。表7-1投資額100萬元200萬元300萬元400萬元500萬元甲307090120130乙50100110110110丙4060110120120解：將問題按工廠分為三個階段k=1，2，3，設狀態(tài)變量（）代表從第個工廠到第3個工廠的投資額，決策變量代表第k個工廠的投資額。于是有狀態(tài)轉移率、允許決策集合和遞推關系式： 當時：于是有表7-2，表中表示第三個階段的最優(yōu)決策。