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

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

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

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

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

5、n-1或anend; 3( 一般若從ai開始，此時(shí)最長(zhǎng)不下降序列應(yīng)該按下列方法求出：ifl>0 then在ai+1 , ai+2 , an中，找出一個(gè)比ai大的且最長(zhǎng)的不下降序begin >作為它的后繼。4(為算法上的需要，定義一個(gè)數(shù)組:ai,2:=l+1;a:array1.3of in teger; ai,3:=k; ai,1表不 a*e nc* 同丘表不從i位置到達(dá)n的最長(zhǎng)不下降序列長(zhǎng)度end; ai,3表示從i位置開始最長(zhǎng)不下降序列的 下一個(gè)位置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下面給出求最長(zhǎng)不下降序列的算法: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:運(yùn)行結(jié)果end; 6下面找出最長(zhǎng)不下降序列，并排序列:3 7 10 12 23 41多階段決策問題典型 題目很多，篇幅限制，在amax:=a1,2;l:=1;此不一一舉例。三、動(dòng)態(tài)規(guī)劃解題的好 處及注意事項(xiàng)：一:動(dòng)態(tài)規(guī)劃解題的好處for j:=2 to do動(dòng)態(tài)規(guī)劃的最大優(yōu)勢(shì)在于它具有極高的效率5而且動(dòng)態(tài)規(guī)劃還if ai,2>amax thenbegin有其他的優(yōu)勢(shì)，例如：動(dòng)態(tài)規(guī)劃可以得出一系列解，算法清晰簡(jiǎn)便，程amax:=ai,2;序易編、易調(diào)，等等。動(dòng)態(tài)規(guī)劃是研究一類最優(yōu)化問題的方法，在經(jīng)l：=i；濟(jì)、工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)

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

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