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

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

2、劃.二動態(tài)規(guī)劃特征動態(tài)規(guī)劃的顯著特征是：無后效性，有邊界條件，且一般劃分為很明顯的階段.動態(tài)規(guī)劃一般還存在一條或多條狀態(tài)轉(zhuǎn)移方程三例題1.Catcher 防衛(wèi)導(dǎo)彈(GDOI98)題目講得很麻煩，歸根結(jié)底就是求一整串?dāng)?shù)中的最長不上升序列這道題目一開始我使用回溯算法，大概可以拿到1/3的分吧，后來發(fā)現(xiàn)這其實是動態(tài)規(guī)劃算法中最基礎(chǔ)的題目 用一個二維數(shù)組 C1.Max,1.2來建立動態(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), 然后程序也就不難實現(xiàn)了 .示范程序：program catche

3、r_hh;varf: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;動態(tài)規(guī)劃數(shù)組procedure readfile;beginassign(f,catcher.dat); reset(f);readln(f,num);for i:=1 to num doreadln(f,ai);end;procedure work;beginfillchar(c,sizeof(c),0); cnum,1:=1;清空數(shù)組，賦初值開始進(jìn)行動態(tài)規(guī)劃for i:=num-1 dow

4、nto 1 dobeginn:=0; max:=1;for j:=i+1 to num doif (aiaj) and (maxmax then begin max:=ci,1; n:=i; end;返回尋找路徑repeatwriteln(n, ); n:=cn,2;until n=0;end;beginreadfile; work;end.2.Perform 巡回演出(GDKOI2000)題目描述:Flute市的Phlharmoniker樂團(tuán)2000年準(zhǔn)備到Harp市做一次大型演出，本著普及古典音樂的目的，樂團(tuán)指揮 L.Y.M準(zhǔn)備在到達(dá)Harp市之前先在周圍一些小城市作一段時間的巡回演出，此

5、后的幾天里，音樂家們將每天搭乘一個航班從一個城市飛到另一個城市，最后才到達(dá)目的地 Harp市(樂團(tuán)可多次在同一城市演出).由于航線的費用和班次每天都在變，城市和城市之間都有一份循環(huán)的航班表，每一時間，每一方向，航班表循環(huán)的周期都可能不同.現(xiàn)要求尋找一張花費費用最小的演岀表.輸入：輸入文件包括若干個場景.每個場景的描述由一對整數(shù) n(2=n=10)和k(1=k=1000)開始，音樂家們要在這n 個城市作巡回演出，城市用1.n標(biāo)號，其中1是起點Flute市,n是終點Harp市，接下來有n*(n-1)份航班表，一份航班表 一行，描述每對城市之間的航線和價格，第一組n-1份航班表對應(yīng)從城市1到其他城市

6、(2,3,.n)的航班，接下的n-1行 是從城市2到其他城市(1,3,4.n)的航班，如此下去.每份航班又一個整數(shù) d(1=d=30)開始，表示航班表循環(huán)的周期，接下來的d個非負(fù)整數(shù)表示1,2.d天對應(yīng)的 兩個城市的航班的價格，價格為零表示那天兩個城市之間沒有航班 例如3 75 0 80表示第一天機(jī)票價格是 75KOI,第 二天沒有航班，第三天的機(jī)票是 80KOI,然后循環(huán)：第四天又是75KOI,第五天沒有航班，如此循環(huán).輸入文件由n=k=0 的場景結(jié)束.輸岀：對每個場景如果樂團(tuán)可能從城市1出發(fā)，每天都要飛往另一個城市，最后(經(jīng)過k天)抵達(dá)城市n,則輸出這k個航班價格之和的最小值.如果不可能存

7、在這樣的巡回演出路線，輸出0.樣例輸入：3 62130 150375 0 807 120 110 0 100 110 120 0460 70 60 503 0 135 1402 70 802 32 0 701 800 0樣例輸出：4600初看這道題，很容易便可以想到動態(tài)規(guī)劃，因為第x天在第y個地方的最優(yōu)值只與第x-1天有關(guān)，符合動態(tài)規(guī)劃的無后效性原則，即只與上一個狀態(tài)相關(guān)聯(lián)，而某一天x航班價格不難求出S=C(x-1) mod m +1.我們用天數(shù)和地點 來規(guī)劃用一個數(shù)組 A1.1000,1.10來存儲，Ai,j表示第i天到達(dá)第j個城市的最優(yōu)值，Ci,j,l表示i城市與j城市間第 l天航班價格，

8、則Ai,j=MinAi-1,l+Cl,j,i (l=1.n 且Cl,j,i0),動態(tài)規(guī)劃方程一出，盡可以放懷大笑了 .示范程序：program perform_hh;varf,fout:text;p,l,i,j,n,k:integer;a:array 1.1000,1.10 of integer; 動態(tài)規(guī)劃數(shù)組c:array 1.10,1.10 of record 航班價格數(shù)組num:integer;t:array 1.30 of integer;end;e:array 1.1000 of integer;procedure work;begin人工賦第一天各城市最優(yōu)值for i:=1 to

9、n dobeginif c1,i.t10then a1,i:=c1,i.t1;end;for i:=2 to k dobeginfor j:=1 to n dobeginfor l:=1 to n dobeginif (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)then ai,j:=ai-1,l+cl,j.t(i-1) mod cl,j.num+1;賦值end;end;end;ep:=ak,n; 第p個場景的最優(yōu)值end;pro

10、cedure readfile; 讀文件beginassign(f,PERFORM.DA T); reset(f);assign(fout,PERFORM.OUT); rewrite(fout);readln(f,n,k); p:=0;while (n0) and (k0) dobeginp:=p+1;fillchar(c,sizeof(c),0); fillchar(a,sizeof(a),0);for i:=1 to n dobeginfor j:=1 to i-1 dobeginread(f,ci,j.num);for l:=1 to ci,j.num doread(f,ci,j.tl)

11、;end;for j:=i+1 to n dobeginread(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;輸岀各個場景的解for i:=1 to p-1 dowriteln(fout,ei); write(fout,ep);close(f);close(fout);end;beginreadfile;end.四小結(jié)動態(tài)規(guī)劃與窮舉法相比，大大減少了計算量，豐富了計算結(jié)果，不僅求岀了當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)值，而且同時求出了到中間狀態(tài)的最優(yōu)值，這對于很多實際問題來說是很有用

12、的.這幾年,動態(tài)規(guī)劃已在各省市信息學(xué)奧林匹克競賽中占據(jù)相當(dāng)重要的地位，每年省賽8道題目中一般有23道題目屬于動態(tài)規(guī)劃，動態(tài)規(guī)劃相比一般窮舉也存 在一定缺點：空間占據(jù)過多，但對于空間需求量不大的題目來說，動態(tài)規(guī)劃無疑是最佳方法！ 五課后題目1.m個人抄n本書，每本書頁數(shù)已知，每個人(第一個人除外)都必須從上一個人抄的最后一本書的下一本抄起(書必須整本整本的抄),求一種分配方法，使抄書頁數(shù)最多的人抄書頁數(shù)盡可能少.(GDOI99 Books).2.有一字符串有多種編碼方式可供人選擇，將這個字符串進(jìn)行編碼，使求得得編碼長度最短。(GDKOI2000外，其他每個城市只能訪問一次，求最多能訪問多少個城市.沁園春雪山舞銀蛇,原馳蠟象,欲與天公試比Compress)3. Canada境內(nèi)有自西向東的一系列城市：Halifax,Hamilton,Montelia,Vanc