動(dòng)態(tài)規(guī)劃在信息學(xué)奧林匹克競(jìng)賽中的應(yīng)用

1、動(dòng)態(tài)規(guī)劃在信息學(xué)奧林匹克競(jìng)賽中的應(yīng)用 一.動(dòng)態(tài)規(guī)劃含義: 在現(xiàn)實(shí)生活中,有一類活動(dòng)的過(guò)程,由于它的特殊性,可將過(guò)程分成若干個(gè)互相聯(lián)系的階段,在它的每一階段都要做出決策,從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果.因此,各個(gè)階段決策確定后,組成一個(gè)決策序列,因而也就確定了整個(gè)過(guò)程的一條活動(dòng)路線.這種把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程,就稱為多階段決策過(guò)程,這種問(wèn)題稱為多階段決策問(wèn)題. 在多階段決策問(wèn)題中,各個(gè)階段采取的決策,一般來(lái)說(shuō)是和時(shí)間有關(guān)的,決策依賴于當(dāng)前狀態(tài),又隨即引起狀態(tài)的轉(zhuǎn)移,一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的,故有動(dòng)態(tài)的含義,我們稱這種解決多階段決策最優(yōu)化的過(guò)程為動(dòng)態(tài)

2、規(guī)劃. 二.動(dòng)態(tài)規(guī)劃特征 動(dòng)態(tài)規(guī)劃的顯著特征是:無(wú)后效性,有邊界條件,且一般劃分為很明顯的階段. 動(dòng)態(tài)規(guī)劃一般還存在一條或多條狀態(tài)轉(zhuǎn)移方程. 三.例題 1. Catcher防衛(wèi)導(dǎo)彈 (GDOI98) 題目講得很麻煩,歸根結(jié)底就是求一整串?dāng)?shù)中的最長(zhǎng)不上升序列 這道題目一開(kāi)始我使用回溯算法,大概可以拿到1/3的分吧,后來(lái)發(fā)現(xiàn)這其實(shí)是動(dòng)態(tài)規(guī)劃算法中最基礎(chǔ)的題目,用一個(gè)二維數(shù)組C1.Max,1.2來(lái)建立動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程(注:C1.Max,1表示當(dāng)前狀態(tài)最多可擊落的導(dǎo)彈數(shù),C1.Max,2表示當(dāng)前狀態(tài)的前繼標(biāo)志):Ci=MaxCj+1,(j=i+1.n),然后程序也就不難實(shí)現(xiàn)了. 示范程序: pro

3、gram catcher_hh; var f:text; i,j,k,max,n,num:integer; a:array 1.4000 of integer; 導(dǎo)彈高度數(shù)組 c:array 1.4000,1.2 of integer; 動(dòng)態(tài)規(guī)劃數(shù)組 procedure readfile; begin assign(f,catcher.dat); reset(f); readln(f,num); for i:=1 to num do readln(f,ai); end; procedure work; begin fillchar(c,sizeof(c),0); cnum,1:=1; 清空數(shù)組

4、,賦初值 開(kāi)始進(jìn)行動(dòng)態(tài)規(guī)劃 for i:=num-1 downto 1 do begin n:=0; max:=1; for j:=i+1 to num do if (aiaj) and (maxmax then begin max:=ci,1; n:=i; end; 返回尋找路徑 repeat writeln(n, ); n:=cn,2; until n=0; end; begin readfile; work; end. 2. Perform巡回演出 (GDKOI2000) 題目描述: Flute市的Phlharmoniker樂(lè)團(tuán)2000年準(zhǔn)備到Harp市做一次大型演出,本著普及古典音樂(lè)的

5、目的,樂(lè)團(tuán)指揮L.Y.M準(zhǔn)備在到達(dá)Harp市之前先在周圍一些小城市作一段時(shí)間的巡回演出,此后的幾天里,音樂(lè)家們將每天搭乘一個(gè)航班從一個(gè)城市飛到另一個(gè)城市,最后才到達(dá)目的地Harp市(樂(lè)團(tuán)可多次在同一城市演出). 由于航線的費(fèi)用和班次每天都在變,城市和城市之間都有一份循環(huán)的航班表,每一時(shí)間,每一方向,航班表循環(huán)的周期都可能不同.現(xiàn)要求尋找一張花費(fèi)費(fèi)用最小的演出表. 輸入: 輸入文件包括若干個(gè)場(chǎng)景.每個(gè)場(chǎng)景的描述由一對(duì)整數(shù)n(2=n=10)和k(1=k=1000)開(kāi)始,音樂(lè)家們要在這n個(gè)城市作巡回演出,城市用1.n標(biāo)號(hào),其中1是起點(diǎn)Flute市,n是終點(diǎn)Harp市,接下來(lái)有n*(n-1)份航班表,

6、一份航班表一行,描述每對(duì)城市之間的航線和價(jià)格,第一組n-1份航班表對(duì)應(yīng)從城市1到其他城市(2,3,.n)的航班,接下的n-1行是從城市2到其他城市(1,3,4.n)的航班,如此下去. 每份航班又一個(gè)整數(shù)d(1=d=30)開(kāi)始,表示航班表循環(huán)的周期,接下來(lái)的d個(gè)非負(fù)整數(shù)表示1,2.d天對(duì)應(yīng)的兩個(gè)城市的航班的價(jià)格,價(jià)格為零表示那天兩個(gè)城市之間沒(méi)有航班.例如3 75 0 80表示第一天機(jī)票價(jià)格是75KOI,第二天沒(méi)有航班,第三天的機(jī)票是80KOI,然后循環(huán):第四天又是75KOI,第五天沒(méi)有航班,如此循環(huán).輸入文件由n=k=0的場(chǎng)景結(jié)束. 輸出: 對(duì)每個(gè)場(chǎng)景如果樂(lè)團(tuán)可能從城市1出發(fā),每天都要飛往另一個(gè)

7、城市,最后(經(jīng)過(guò)k天)抵達(dá)城市n,則輸出這k個(gè)航班價(jià)格之和的最小值.如果不可能存在這樣的巡回演出路線,輸出0. 樣例輸入: 3 6 2 130 150 3 75 0 80 7 120 110 0 100 110 120 0 4 60 70 60 50 3 0 135 140 2 70 80 2 3 2 0 70 1 80 0 0 樣例輸出: 460 0 初看這道題,很容易便可以想到動(dòng)態(tài)規(guī)劃,因?yàn)榈趚天在第y個(gè)地方的最優(yōu)值只與第x-1天有關(guān),符合動(dòng)態(tài)規(guī)劃的無(wú)后效性原則,即只與上一個(gè)狀態(tài)相關(guān)聯(lián),而某一天x航班價(jià)格不難求出S=C(x-1) mod m +1.我們用天數(shù)和地點(diǎn)來(lái)規(guī)劃用一個(gè)數(shù)組A1.10

8、00,1.10來(lái)存儲(chǔ),Ai,j表示第i天到達(dá)第j個(gè)城市的最優(yōu)值,Ci,j,l表示i城市與j城市間第l天航班價(jià)格,則Ai,j=MinAi-1,l+Cl,j,i (l=1.n且Cl,j,i0),動(dòng)態(tài)規(guī)劃方程一出,盡可以放懷大笑了. 示范程序: program perform_hh; var f,fout:text; p,l,i,j,n,k:integer; a:array 1.1000,1.10 of integer; 動(dòng)態(tài)規(guī)劃數(shù)組 c:array 1.10,1.10 of record 航班價(jià)格數(shù)組 num:integer; t:array 1.30 of integer; end; e:arr

9、ay 1.1000 of integer; procedure work; begin 人工賦第一天各城市最優(yōu)值 for i:=1 to n do begin if c1,i.t10 then a1,i:=c1,i.t1; end; for i:=2 to k do begin for j:=1 to n do begin for l:=1 to n do begin if (jl) and (cl,j.t(i-1) mod cl,j.num+10) 判斷存在航班 and (ai,j=0) or (ai-1,l+cl,j.t(i-1) mod cl,j.num+1ai,j) 判斷比當(dāng)前解優(yōu) t

10、hen ai,j:=ai-1,l+cl,j.t(i-1) mod cl,j.num+1; 賦值 end; end; end; ep:=ak,n; 第p個(gè)場(chǎng)景的最優(yōu)值 end; procedure readfile; 讀文件 begin assign(f,PERFORM.DAT); reset(f); assign(fout,PERFORM.OUT); rewrite(fout); readln(f,n,k); p:=0; while (n0) and (k0) do begin p:=p+1; fillchar(c,sizeof(c),0); fillchar(a,sizeof(a),0);

11、for i:=1 to n do begin for j:=1 to i-1 do begin read(f,ci,j.num); for l:=1 to ci,j.num do read(f,ci,j.tl); end; for j:=i+1 to n do begin read(f,ci,j.num); for l:=1 to ci,j.num do read(f,ci,j.tl); end; end; work; readln(f,n,k); end; 輸出各個(gè)場(chǎng)景的解 for i:=1 to p-1 do writeln(fout,ei); write(fout,ep); close(

12、f); close(fout); end; begin readfile; end. 四.小結(jié) 動(dòng)態(tài)規(guī)劃與窮舉法相比,大大減少了計(jì)算量,豐富了計(jì)算結(jié)果,不僅求出了當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)值,而且同時(shí)求出了到中間狀態(tài)的最優(yōu)值,這對(duì)于很多實(shí)際問(wèn)題來(lái)說(shuō)是很有用的.這幾年,動(dòng)態(tài)規(guī)劃已在各省市信息學(xué)奧林匹克競(jìng)賽中占據(jù)相當(dāng)重要的地位,每年省賽8道題目中一般有23道題目屬于動(dòng)態(tài)規(guī)劃,動(dòng)態(tài)規(guī)劃相比一般窮舉也存在一定缺點(diǎn):空間占據(jù)過(guò)多,但對(duì)于空間需求量不大的題目來(lái)說(shuō),動(dòng)態(tài)規(guī)劃無(wú)疑是最佳方法! 五.課后題目 1. m個(gè)人抄n本書,每本書頁(yè)數(shù)已知,每個(gè)人(第一個(gè)人除外)都必須從上一個(gè)人抄的最后一本書的下一本抄起(書

13、必須整本整本的抄),求一種分配方法,使抄書頁(yè)數(shù)最多的人抄書頁(yè)數(shù)盡可能少. (GDOI99 Books). 2. 有一字符串有多種編碼方式可供人選擇，將這個(gè)字符串進(jìn)行編碼，使求得得編碼長(zhǎng)度最短。（GDKOI2000 Compress) 3. Canada境內(nèi)有自西向東的一系列城市：Halifax,Hamilton,Montelia,Vancouver.，各個(gè)城市之間可能有航班相連，也可能沒(méi)有，現(xiàn)要求從最西的城市出發(fā)，自西向東到達(dá)最東的城市，再返回最西的城市，除最西城市外，其他每個(gè)城市只能訪問(wèn)一次，求最多能訪問(wèn)多少個(gè)城市動(dòng)態(tài)規(guī)劃-航線設(shè)置 問(wèn)題描述:美麗的萊茵河畔,每邊都分布著N個(gè)城市,兩邊的城市

14、都是唯一對(duì)應(yīng)的友好城市,現(xiàn)需要在友好城市開(kāi)通航線以加強(qiáng)往來(lái).但因?yàn)槿R茵河常年大霧,如果開(kāi)設(shè)的航線發(fā)生交叉現(xiàn)象就有可能出現(xiàn)碰船的現(xiàn)象.現(xiàn)在要求近可能多地開(kāi)通航線并且使航線不能相交! 假如你是一個(gè)才華橫溢的設(shè)計(jì)師,該如何設(shè)置友好城市間的航線使的航線數(shù)又最大又不相交呢? 分析:此問(wèn)題可以演化成求最大不下降序列來(lái)完成.源程序如下:program dongtai; 動(dòng)態(tài)規(guī)劃之友好城市航線設(shè)置問(wèn)題var d:array1.1000,1.4 of integer; i,j,k,n,L,p:integer; procedure print(L:integer); 打印結(jié)果 begin writeLn(最多可設(shè)

15、置的航線數(shù)是 : ,k); repeat writeLn(dL,1:4,dL,2:4); 輸出可以設(shè)置航線的友好城市代碼 L:=dL,4 untiL L=0 end;begin writeLn(輸入友好城市對(duì)數(shù): ); readLn(n); writeLn(輸入友好城市對(duì)（友好城市放在同一行:); 輸入 for i:=1 to n do readLn(di,1,di,2); DI，1表示起點(diǎn)，DI，2表示終點(diǎn) for i:=1 to n do begin di,3:=1; DI，3表示可以設(shè)置的航線條數(shù) di,4:=0 DI，4表示后繼，即下一條航線從哪里開(kāi)始設(shè)置，為0表示不能設(shè)置下一條航線

16、end;for i:=n-1 downto 1 do 從倒數(shù)第二個(gè)城市開(kāi)始規(guī)劃 begin L:=0; p:=0; L表示本城市后面可以設(shè)置的航線數(shù)，P表示下條航線從哪個(gè)城市開(kāi)始 for j:=i+1 to n do 找出本城市后面可以設(shè)置的最大航線數(shù)和小條航線到底從哪個(gè)城市開(kāi)始設(shè)置 if (di,2 L) then 如果本城市I的終點(diǎn)小于后面城市的終點(diǎn)（即不相交） 并且此城市后面可以設(shè)置的航線數(shù)大于L begin L:=dj,3; 那么L等于城市J的可以設(shè)置航線數(shù) p:=j P等于可以設(shè)置下條航線的城市代碼 end; if L0 then 如果本城市后面總共可以設(shè)置的航線數(shù)0則 begin di,3:=L+1; 本城市可以設(shè)置的航線數(shù)在下個(gè)城市可以設(shè)置航線數(shù)的基礎(chǔ)上加1 di,4:=p DI，4等于本城市后續(xù)城市的代碼