動態(tài)規(guī)劃講義-含matlab算法

《動態(tài)規(guī)劃講義-含matlab算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、動態(tài)規(guī)劃是對最優(yōu)化問題的一種新的算法設計方法。由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的沒計法對不同的問題，有各具特色的表示方式。不存在一種萬能的動態(tài)規(guī)劃算法。但是可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進行討論，學會這一設計方法。多階段決策過程最優(yōu)化問題——動態(tài)規(guī)劃的基本模型在現(xiàn)實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。因此各個階段決策的選取不能任意確定，它依賴于當前面臨的狀態(tài)，又影響以后的發(fā)展。當各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一

2、條活動路線。這種把一個問題看做是一個前后關聯(lián)具有鏈狀結構的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策最優(yōu)化問題?！纠}1】最短路徑問題。圖中給出了一個地圖，地圖中每個頂點代表一個城市，兩個城市間的連線代表道路，連線上的數(shù)值代表道路的長度。現(xiàn)在，想從城市A到達城市E，怎樣走路程最短，最短路程的長度是多少?【分析】把從A到E的全過程分成四個階段，用k表示階段變量，第1階段有一個初始狀態(tài)A，兩條可供選擇的支路ABl、AB2；第2階段有兩個初始狀態(tài)B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路……。用dk(xk，xk+1)表示在第k階段由初始狀態(tài)xk到下階段的初始狀態(tài)x

3、k+1的路徑距離，F(xiàn)k(xk)表示從第k階段的xk到終點E的最短距離，利用倒推方法求解A到E的最短距離。具體計算過程如下：S1：K=4，有：F4(D1)=3，F(xiàn)4(D2)=4，F(xiàn)4(D3)=3S2:K=3，有：F3(C1)=min{d3(C1,D1)+F4(D1),d3(C1,D2)+F4(d2)}=min{8,10}=8F3(C2)=d3(C2,D1)+f4(D1)=5+3=8F3(C3)=d3(C3,D3)+f4(D3)=8+3=11F3(C4)=d3(C4,D3)+f4(D3)=3+3=6S2:K=2，有：F2(B1)=min{d2(B1,C1)+F3(C1),d2(B1,C2)+f

4、3(C2),d2(B1,C3)+F3(C3)}=min{9,12,14}=9F2(m)=min{d2(B2,c2)+f3(C2),d2(B2,C4)+F3(C4)}=min{16,10}=10S4：k=1，有：F1(A)=min{d1(A,B1)+F2(B1),d1(A,B2)+F2(B2)}=min{13,13}=13因此由A點到E點的全過程的最短路徑為A—>B2一>C4—>D3—>E。最短路程長度為13。從以上過程可以看出，每個階段中，都求出本階段的各個初始狀態(tài)到過程終點E的最短路徑和最短距離，當逆序倒推到過程起點A時，便得到了全過程的最短路徑及最短距離，同時附帶得到了一組最優(yōu)結果(即

5、各階段的各狀態(tài)到終點E的最優(yōu)結果)。在上例的多階段決策問題中，各個階段采取的決策，一般來說是與時間有關的，決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義，稱這種解決多階段決策最優(yōu)化問題的方法為動態(tài)規(guī)劃方法。根據(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)化問題的方法，在經(jīng)濟、工程技術、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)

6、及軍事等領域中都有廣泛的應用。近年來，在ACM/ICPC中，使用動態(tài)規(guī)劃(或部分應用動態(tài)規(guī)劃思維)求解的題不僅常見，而且形式也多種多樣。而在與此相近的各類信息學競賽中，應用動態(tài)規(guī)劃解題已經(jīng)成為一種趨勢，這和動態(tài)規(guī)劃的優(yōu)勢不無關系。1、動態(tài)規(guī)劃的常用名詞在學習動態(tài)規(guī)劃之前，先得對下面的名詞有所了解。本書將標準名詞作了一些簡化，便于大家更好的理解。(1)狀態(tài)(smte)對于一個問題，所有可能到達的情況(包括初始情況和目標情況)都稱為這個問題的一個狀態(tài)。(2)狀態(tài)變量(sk)對每個狀態(tài)k關聯(lián)一個狀態(tài)變量sk，它的值表示狀態(tài)k所對應的問題的當前解值。(3)決策(decision)決策是一種選擇，對

7、于每一個狀態(tài)而言，你都可以選擇某一種路線或方法，從而到達下一個狀態(tài)。(4)決策變量(dk)在狀態(tài)k下的決策變量dk的值表示對狀態(tài)k當前所做出的決策。(5)策略策略是一個決策的集合，在我們解決問題的時候，我們將一系列決策記錄下來，就是一個策略，其中滿足某些最優(yōu)條件的策略稱之為最優(yōu)策略。(6)狀態(tài)轉(zhuǎn)移函數(shù)(t)從一個狀態(tài)到另一個狀態(tài)，可以依據(jù)一定的規(guī)則來前進。我們用一個函數(shù)t來描述這樣的規(guī)則，它將狀態(tài)i和決策變量di映射到另