動態(tài)規(guī)劃多階段決策問題的求解方法

1、動態(tài)規(guī)劃_多階段決策問題的求解方法1構造狀態(tài)網(wǎng)絡；：一:解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃方法在程序設計中， 有一類活動的過程，由于它的特殊性，可將過程2.根據(jù)狀態(tài)轉移尖系和狀態(tài)轉移方程 建立最優(yōu)值的分成若干個互相聯(lián)系的階段，在它的每一階段都需要做出決策，從而3. 按階段的先后次序計算每個狀態(tài)的最優(yōu)值。使整個過程達到最好 的活動效果。因此各個 階段決策的選取不能任逆向思維法是指從問題目標狀態(tài)出發(fā)倒推回初始意確定，它依賴 于當前面臨的狀態(tài)，又影響以后的發(fā)展。當各個階段 態(tài)的思維方法。動態(tài)規(guī)劃的逆向思 維法的要點可歸納為以決策確定后，就組成一個決策序列，因而也就確定了整個過程的 一條1.分析最優(yōu)

2、值的結構,刻畫其結構特征；活動路線。這種把一個問題看作是一個 前后尖聯(lián)具有鏈狀結構的多2 遞歸地定義最優(yōu)值；階段過程就稱為多階段決策過程，這種問題稱為多階段決策問題。3按自 底向上或自頂向下記憶化的方式計算最優(yōu)在多階段決策問題中，各個階段采取的決策， 一般來說是與時間有尖的，決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉移，一個決策序 列如果原問題可 以分解成幾個本質(zhì)相同、規(guī)模較小的就是在變化的狀態(tài)中產(chǎn)生出來的，故有”動態(tài)”的含 義，我們稱這種就會聯(lián)想到從逆向思維的角度尋求問題的解決。一般解決多階段決策最 優(yōu)化的過程為動態(tài)規(guī)劃方法。策問題多采用動態(tài)規(guī)劃逆向思維方 法解決。二、舉:二： 動態(tài)規(guī)劃最優(yōu)化原

3、理pascal語例說明本文以信息學奧賽用語言一一最優(yōu)化原理是動態(tài) 規(guī)劃的基礎。任何一個問題，如果失去了這言為編程個最優(yōu)化原理的支持，就不可能用 動態(tài)規(guī)劃方法計算。這個“最優(yōu)化說明，其他編程語言編寫方法相同，語句類似。原 理”如果用數(shù)學化一點的語言來描述的話，就是:假設為了解決某：一：問題描述一優(yōu) 化問題，需要依次作出n個決策D1，D2, , Dn,如若這個決策設有N個不相同的整數(shù)組成的數(shù)列，記為：序列是最優(yōu)的，對于任何一個整數(shù)k，1 v k v n，不論前面k個決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當前狀態(tài)，即 ()且？ ？ al a2 an aiajij以后的決策Dk+1，D

4、k+2 Dn也是最優(yōu)的。作為整個過程的 最優(yōu) 例如 3，18，7，14，10，12, 23, 41，16, 24策略具有這樣的性質(zhì)：即無論過去的狀態(tài) 和決策如何，對以前的決策 若存在i1<i2 <ie且有ai1<ai2 <aie則 稱為長度序列。如上例中3,18,23,24就是一個長度為4的不下也有3，7，10，12，16, 24長度為6的不下降序列。程序>»»»»若an-1<an則存在長度為2的不下降序列an-1 , an。begink:=j;l:=aj,2; (2)若an-1>an則存在長度為1的不下降序列a

5、n-1或anend; 3( 一般若從ai開始，此時最長不下降序列應該按下列方法求出：ifl>0 then在ai+1 , ai+2 , an中，找出一個比ai大的且最長的不下降序begin >作為它的后繼。4(為算法上的需要，定義一個數(shù)組:ai,2:=l+1;a:array1.3of in teger; ai,3:=k; ai,1表不 a*e nc* 同丘表不從i位置到達n的最長不下降序列長度end; ai,3表示從i位置開始最長不下降序列的 下一個位置amax:=a1,2;初始化:for i:=1 to n do l:=1; ()begin readai,1 ;ai,2:=1 ;a

6、i,3=0for j:=2 to n-1 doend; if ai,2>amax the n下面給出求最長不下降序列的算法:beginfor i:=n-1 dow nto 1 do amax:=ai,2;beg in l:=i; end;I:=1 ;k:=0; ()writelnamax:3; for j:=i+1 to n do while loO do if aj,1>ai,1and aj,2>l then begin k:=j;l:=aj,2end; beginif l>0 then ()write al,1:3;begin l:=al,3; ai,2:=l+1;

7、 end;ai,3:=k; end.end : 23:運行結果end; 6下面找出最長不下降序列，并排序列:3 7 10 12 23 41多階段決策問題典型 題目很多，篇幅限制，在amax:=a1,2;l:=1;此不一一舉例。三、動態(tài)規(guī)劃解題的好 處及注意事項：一:動態(tài)規(guī)劃解題的好處for j:=2 to do動態(tài)規(guī)劃的最大優(yōu)勢在于它具有極高的效率5而且動態(tài)規(guī)劃還if ai,2>amax thenbegin有其他的優(yōu)勢，例如：動態(tài)規(guī)劃可以得出一系列解，算法清晰簡便，程amax:=ai,2;序易編、易調(diào)，等等。動態(tài)規(guī)劃是研究一類最優(yōu)化問題的方法，在經(jīng)l：=i；濟、工程技術、企業(yè)管理、工農(nóng)業(yè)

8、生產(chǎn)及軍事等領域中都有廣泛 的應(end;用。近年來，在ACM/ICPC中，使用動態(tài)規(guī)劃或部分應用動態(tài)規(guī)劃)最長不下降序列長度為amax,2)思維求解的題不僅常見，而且形式也多種多 樣。而在與此相近的各類信息學競賽中，應用動態(tài)規(guī)劃解題已經(jīng)成為一種趨勢，這和動態(tài)規(guī)序列whileloO dobegin劃的優(yōu)勢不無尖系。() write al,1:3;:二:動態(tài)規(guī)劃解題的注意事項1 (動態(tài)規(guī)劃它只適于解決一定條件的最優(yōu)策略問題，利用動態(tài)l：=al,3;規(guī)劃解題，階段的劃分是尖鍵，必須依 據(jù)題意分析，尋求合理的劃分end;()階段子問題方法。而每個子問題是 個比原問題簡單得多的優(yōu)化：三：參考程序問題。

9、而且每個子問題的求解中，均利用它的一個后部子問題的最 （）program buxiajia ngin put,output;優(yōu)化結果，直到最后一個子問題所得最優(yōu)解，它就是原問題的最優(yōu)解。const n=10; 2 （應指出，動態(tài)規(guī)劃是考察求解多階段決策問題的途徑和方法，vara:array1. n,1 .3of in teger;但它不像線性規(guī)劃那樣，具有一個標準的數(shù)學表達式和明確定義的一組規(guī)劃。因此我們在學習時，除了要對基本概念和方法正確理解 i,k,l,j,amax:i nteger; 夕卜，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)begin造性的技巧去求解。for i=1 to n do 3.動態(tài)規(guī)劃是運籌學 的一個分 支。許多隱式圖上的算法，例如求begin單源最短路徑的Dijkstra算法、廣度優(yōu)先搜索 算法，都滲透著動態(tài)規(guī)（）readai,1;劃的思想。還有許多數(shù)學問題，表面上看起來與動態(tài)規(guī)劃風馬牛不ai,2:=1;相及，但是其求解思想與動態(tài)規(guī)劃是完全一致的。ai,3:=0;end;for i:=n-1 dow nto 1 dob