20100319動(dòng)態(tài)程序設(shè)初步

1、動(dòng)態(tài)程序設(shè)計(jì)1動(dòng)態(tài)程序設(shè)計(jì)動(dòng)態(tài)規(guī)劃是解決多階段決策最優(yōu)化問(wèn)題的一種思想方法。所謂“動(dòng)態(tài)”，指的是在問(wèn)題的多階段決策中，按某一順序，根據(jù)每一步所選決策的不同，將隨即引起狀態(tài)的轉(zhuǎn)移，最終在變化的狀態(tài)中產(chǎn)生一個(gè)決策序列。動(dòng)態(tài)規(guī)劃就是為了使產(chǎn)生的決策序列在符合某種條件下達(dá)到最優(yōu)。 動(dòng)態(tài)程序設(shè)計(jì)是一種重要的程序設(shè)計(jì)思想，具有廣泛的應(yīng)用價(jià)值。使用動(dòng)態(tài)規(guī)劃思想來(lái)設(shè)計(jì)算法，對(duì)于不少問(wèn)題往往具有高時(shí)效，因而，對(duì)于能夠使用動(dòng)態(tài)程序設(shè)計(jì)思想來(lái)解決的問(wèn)題，使用動(dòng)態(tài)規(guī)劃是比較明智的選擇。2基本原理1、多階段最優(yōu)化決策：即由初始狀態(tài)開(kāi)始，通過(guò)對(duì)中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整

2、個(gè)過(guò)程的一條最優(yōu)的活動(dòng)路線。3帶權(quán)有向的多段圖 上一階段的狀態(tài)下一階段的狀態(tài)決策4概念狀態(tài)（State）：表示事物的性質(zhì)，是描述“動(dòng)態(tài)規(guī)劃”中的“單元”的量。亦是每一階段求解過(guò)程的出發(fā)點(diǎn)。階段（Stage）：階段是一些性質(zhì)相近，可以同時(shí)處理的狀態(tài)集合，或者說(shuō)，階段只是標(biāo)識(shí)那些處理方法相同、處理順序無(wú)關(guān)的狀態(tài)。決策（Decision）：每個(gè)階段做出的某種選擇性的行動(dòng)，是程序所需要完成的選擇。狀態(tài)轉(zhuǎn)移方程：是前一個(gè)階段的狀態(tài)轉(zhuǎn)移到后一個(gè)的狀態(tài)的演變規(guī)律，是關(guān)于兩個(gè)相鄰階段狀態(tài)變化的方程，是“動(dòng)態(tài)規(guī)劃”的中心。設(shè) fk(i)k階段狀態(tài)i的最優(yōu)權(quán)值，即初始狀態(tài)至狀態(tài)i的最優(yōu)代價(jià) fk+1(i)=min

3、xk(j)+u(i,j) 5基本概念階段和狀態(tài) 1、階段k：將所給問(wèn)題的過(guò)程，按時(shí)間或空間特征分解成若干相互聯(lián)系的階段，以便按次序去求每階段的解。設(shè)階段變量為k。階段是問(wèn)題的屬性。多階段決策問(wèn)題中通常存在著若干個(gè)階段。在一般情況下，階段是和時(shí)間有關(guān)的，但是在很多問(wèn)題中，階段和時(shí)間并無(wú)直接關(guān)系。從階段的定義中，可以看出階段的兩個(gè)特點(diǎn)，一是“相互聯(lián)系”，二是“次序”。階段之間相互聯(lián)系的方式是通過(guò)狀態(tài)和狀態(tài)轉(zhuǎn)移體現(xiàn)的。 2、狀態(tài)Sk：各階段開(kāi)始時(shí)的客觀條件叫做狀態(tài)。描述各階段狀態(tài)的變量稱為狀態(tài)變量，常用sk表示第k階段的狀態(tài)變量，狀態(tài)變量sk的取值集合稱為狀態(tài)集合，用Sk表示。狀態(tài)是階段的屬性。每個(gè)

4、階段通常包含若干個(gè)狀態(tài)，用以描述問(wèn)題發(fā)展到這個(gè)階段時(shí)所處在的一種客觀情況。每個(gè)階段的狀態(tài)都是由以前階段的狀態(tài)以某種方式“變化”而來(lái)，這種“變化”稱為狀態(tài)轉(zhuǎn)移。狀態(tài)轉(zhuǎn)移是導(dǎo)出狀態(tài)的途徑，也是聯(lián)系各階段的途徑。 應(yīng)用動(dòng)態(tài)程序設(shè)計(jì)方法的一個(gè)重要條件。那就是將各階段按照一定的次序排列好之后，對(duì)于階段i的狀態(tài)只能由階段i+1的狀態(tài)通過(guò)狀態(tài)轉(zhuǎn)移方程得來(lái)，與其它狀態(tài)沒(méi)有關(guān)系，尤其是與未發(fā)生的狀態(tài)沒(méi)有關(guān)系。換句話說(shuō)，每個(gè)狀態(tài)都是“過(guò)去歷史的一個(gè)完整總結(jié)”。這就是無(wú)后效性。6決策和策略1、決策uk(sk)：當(dāng)各段的狀態(tài)取定以后，就可以做出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。表示決策的變量稱為決

5、策變量，常用uk(sk)表示第k階段當(dāng)狀態(tài)為sk時(shí)的決策變量。在實(shí)際問(wèn)題中，決策變量的取值往往限制在一定范圍內(nèi)，我們稱此范圍為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合。顯然有uk(sk) Dk(sk)。 決策是問(wèn)題解的屬性。決策的目的就是“確定下一階段的狀態(tài)”。有了決策，我們可以定義狀態(tài)轉(zhuǎn)移。動(dòng)態(tài)程序設(shè)計(jì)方法中本階段的狀態(tài)往往是上一階段和上一階段的決策結(jié)果，由第k段的狀態(tài)sk和本階段的決策uk確定第k+1段的狀態(tài)sk+1的過(guò)程叫狀態(tài)轉(zhuǎn)移。狀態(tài)轉(zhuǎn)移規(guī)律的形式化表示sk+1=Tk(sk，uk)稱為狀態(tài)轉(zhuǎn)移方程。決策的目的是轉(zhuǎn)移狀態(tài)，狀態(tài)轉(zhuǎn)移的途徑是決策。2、策略pl，

6、n：各段決策確定后，整個(gè)問(wèn)題的決策序列就構(gòu)成一個(gè)策略，用p1，n=u1(s1)，u2(s2)， un(sn)表示。對(duì)每個(gè)實(shí)際問(wèn)題，可供選擇的策略有一定范圍，稱為允許策略集合，記作P1，n，使整個(gè)問(wèn)題達(dá)到最有效果的策略就是最優(yōu)策略。 運(yùn)用動(dòng)態(tài)程序設(shè)計(jì)方法的一個(gè)前提。即這個(gè)過(guò)程的最優(yōu)策略應(yīng)具有這樣的性質(zhì)：無(wú)論初始狀態(tài)及初始決策如何，對(duì)于先前決策所形成的狀態(tài)而言，其以后的所有決策應(yīng)構(gòu)成最優(yōu)策略。這就是最優(yōu)化原理。簡(jiǎn)言之，就是最優(yōu)策略的子策略也是最優(yōu)策略。7狀態(tài)轉(zhuǎn)移方程： （邊界條件）使用動(dòng)態(tài)程序設(shè)計(jì)方法解題的步驟1、確定問(wèn)題的研究對(duì)象，即狀態(tài)。選定的狀態(tài)必須滿足如下兩點(diǎn)：狀態(tài)必須完全描述出事物的性質(zhì)

7、，兩個(gè)不同事物的狀態(tài)是不同的；必須存在狀態(tài)與狀態(tài)之間的“轉(zhuǎn)移方程”，以便我們可以由初始狀態(tài)逐漸轉(zhuǎn)化為目標(biāo)狀態(tài)。由于狀態(tài)是描述事物性質(zhì)的量，所以我們應(yīng)該以上述要求為標(biāo)準(zhǔn)，具體情況具體分析；2、劃分階段，確定階段之間的狀態(tài)轉(zhuǎn)移方程；3、考察此問(wèn)題可否用動(dòng)態(tài)程序設(shè)計(jì)方法解決，即問(wèn)題是否具備最優(yōu)子結(jié)構(gòu)和無(wú)后效性的特征4、如果發(fā)現(xiàn)問(wèn)題目前不能用動(dòng)態(tài)程序設(shè)計(jì)方法解決，則調(diào)整階段的劃分和狀態(tài)的定義，使其具備最優(yōu)子結(jié)構(gòu)和無(wú)后效性的特征。8程序設(shè)計(jì)的一般格式 ；for kn-1 downto 1 do 枚舉階段 for s取遍所有狀態(tài) do for u取遍所有決策 do ；這里是一種從目標(biāo)狀態(tài)往回推的逆序求法，

8、適用于目標(biāo)狀態(tài)確定的問(wèn)題。而很多試題是確定了初始狀態(tài)的。當(dāng)然，對(duì)于初始狀態(tài)確定的問(wèn)題，我們也可以采用從初始狀態(tài)出發(fā)往前推的順序求法。事實(shí)上，這種方法對(duì)我們來(lái)說(shuō)要更為直觀、更易設(shè)計(jì)一些，從而更多地出現(xiàn)在我們的解題過(guò)程中。由于動(dòng)態(tài)程序設(shè)計(jì)方法的模式性比較強(qiáng)，因此應(yīng)該把主要精力放在狀態(tài)定義、階段劃分和狀態(tài)轉(zhuǎn)移方程的設(shè)計(jì)上。一旦這些問(wèn)題解決了，事情成功了一大半。9基本原理最優(yōu)性原理作為整個(gè)過(guò)程的最優(yōu)策略，它滿足：相對(duì)前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。無(wú)后效性原則給定某一階段的狀態(tài)，則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過(guò)程也就確定了

9、。這個(gè)性質(zhì)意味著過(guò)程的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它的未來(lái)的發(fā)展，這個(gè)性質(zhì)稱為無(wú)后效性。10機(jī)器分配 總公司擁有高效生產(chǎn)設(shè)備M臺(tái)，準(zhǔn)備分給下屬的N個(gè)公司。各分公司若獲得這些設(shè)備，可以為國(guó)家提供一定的盈利。問(wèn)：如何分配這M臺(tái)設(shè)備才能使國(guó)家得到的盈利最大？求出最大盈利值。其中M=15，N=10。分配原則：每個(gè)公司有權(quán)獲得任意數(shù)目的設(shè)備，但總臺(tái)數(shù)不得超過(guò)總設(shè)備數(shù)M。數(shù)據(jù)文件格式為：第一行保存兩個(gè)數(shù)，第一個(gè)數(shù)是設(shè)備臺(tái)數(shù)M，第二個(gè)數(shù)是分公司數(shù)N。接下來(lái)是一個(gè)M*N的矩陣，表明了第I個(gè)公司分配J臺(tái)機(jī)器的盈利。 11分析用機(jī)器數(shù)來(lái)做狀態(tài)，數(shù)組FI，J表示前I個(gè)公司分配J臺(tái)機(jī)器的最大盈利。則狀態(tài)轉(zhuǎn)移方程為:F

10、I，J=MaxFI-1，K + ValueI，J-K (1=I=N,1=J=M,0=K=J )初始值: F(0,0)=0時(shí)間復(fù)雜度O(N*M2)12最長(zhǎng)不下降序列 設(shè)有整數(shù)序列b1,b2,b3,bm，若存在下標(biāo)i1i2i3 in，且bi1bi2bi3 bin，則稱 b1,b2,b3,bm中有長(zhǎng)度為n的不下降序列bi1 , bi2 ,bi3 ,bin 。求序列b1,b2,b3,bm中所有長(zhǎng)度(n)最大不下降子序列輸入：整數(shù)序列。輸出：最大長(zhǎng)度n和所有長(zhǎng)度為n的序列個(gè)數(shù)。13分析（1）設(shè)f(i)為前i個(gè)數(shù)中的最大不下降序列長(zhǎng)度 , 則f(i)=maxf(j)+1 (1=ji=m, bjbi)邊界為

11、F(1)=1(2)設(shè)t(i)為前i個(gè)數(shù)中最長(zhǎng)不下降序列的個(gè)數(shù),則t(i)=t(j) (1=ji=m , bjbi, f(i)=f(j)-1) 初始為t(i)=1當(dāng)f(i)=n時(shí)，將t(i)累加舉例： 1 2 3 4 6 5 8 10 9 f: 1 2 3 4 5 5 6 7 7 t: 1 1 1 1 1 1 2 2 2答案：f=7時(shí)，邊界為t=414read(m)for i:=1 to m do read(bi);f1:=0;for i:=2 to m do begin fi:=1; for j:=1 to i-1 do if (bj=bi) and (fj+1res) res:=fi;wri

12、teln(res);程序15 合唱隊(duì)形【問(wèn)題描述】N位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1, 2, , K，他們的身高分別為T(mén)1, T2, , TK，則他們的身高滿足T1 T2 Ti+1 TK (1iK)。你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。【輸入文件】輸入文件chorus.in的第一行是一個(gè)整數(shù)N（2 N 100），表示同學(xué)的總數(shù)。第一行有n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)Ti（130 Ti 230）是第i位同學(xué)的身高（厘米）?！?/p>

13、輸出文件】輸出文件chorus.out包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列。16算法分析我們按照由左而右和由右而左的順序，將n個(gè)同學(xué)的身高排成數(shù)列。如何分別在這兩個(gè)數(shù)列中尋求遞增的、未必連續(xù)的最長(zhǎng)子序列，就成為問(wèn)題的關(guān)鍵。設(shè)a為身高序列，其中ai為同學(xué)i的身高；b 為由左而右身高遞增的人數(shù)序列，其中 bi為同學(xué)1同學(xué)i間（包括同學(xué)i）身高滿足遞增順序的最多人數(shù)。顯然 bi= bj|同學(xué)j的身高同學(xué)i的身高+1；c為由右而左身高遞增的人數(shù)序列，其中ci為同學(xué)n同學(xué)i間（包括同學(xué)i）身高滿足遞增順序的最多人數(shù)。顯然 ci= cj|同學(xué)j的身高aj)and(bj+1bi) then bi:=bj+1; end;for for i:=n dow