荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: 一个初中生写的关于动态的文章
发信站: 荔园晨风BBS站 (Sun Aug 1 22:44:16 2004), 站内信件
动态规划在信息学奥林匹克竞赛中的应用
一.动态规划含义:
在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系
的阶段,在它的每一阶段都要做出决策,从而使整个过程达到最好的活动效果. 因此,
各个阶段决策确定后,组成一个决策序列,因而也就确定了整个过程的一条活动路线.
这种把一个问题看作是一个前后关联具有链状结构的多阶段过程,就称为多阶段决策
过程,这种问题称为多阶段决策问题.
在多阶段决策问题中,各个阶段采取的决策,一般来说是和时间有关的,决策依赖于
当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故
有"动态"的含义,我们称这种解决多阶段决策最优化的过程为动态规划.
二.动态规划特征
动态规划的显著特征是:无后效性,有边界条件,且一般划分为很明显的阶段.
动态规划一般还存在一条或多条状态转移方程.
三.例题
1. Catcher防卫导弹 (GDOI'98)
题目讲得很麻烦,归根结底就是求一整串数中的最长不上升序列
这道题目一开始我使用回溯算法,大概可以拿到1/3的分吧,后来发现这其实是动态
规划算法中最基础的题目,用一个二维数组C[1..Max,1..2]来建立动态规划状态转移
方程(注:C[1..Max,1]表示当前状态最多可击落的导弹数,C[1..Max,2]表示当前状态
的前继标志):Ci=Max {C[j]+1,(j=i+1..n)},然后程序也就不难实现了.
示范程序:
program catcher_hh;
var
f:text;
i,j,k,max,n,num:integer;
a:array [1..4000] of integer; {导弹高度数组}
c:array [1..4000,1..2] of integer; {动态规划数组}
procedure readfile;
begin
assign(f,'catcher.dat'); reset(f);
readln(f,num);
for i:=1 to num do
readln(f,a[i]);
end;
procedure work;
begin
fillchar(c,sizeof(c),0); c[num,1]:=1; {清空数组,赋初值}
{开始进行动态规划}
for i:=num-1 downto 1 do
begin
n:=0; max:=1;
for j:=i+1 to num do
if (a[i]>a[j]) and (max<1+c[j,1])
then begin n:=j; max:=1+c[j,1]; end;
c[i,1]:=max; c[i,2]:=n;
end;
writeln; writeln('Max : ',max); {打印最大值}
max:=0; n:=0;
for i:=1 to num do
if c[i,1]>max then begin max:=c[i,1]; n:=i; end;
{返回寻找路径}
repeat
writeln(n,' '); n:=c[n,2];
until n=0;
end;
begin
readfile; work;
end.
2. Perform巡回演出 (GDKOI'2000)
题目描述:
Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典
音乐的目的,乐团指挥L.Y.M准备在到达 Harp市之前先在周围一些小城市作一段时间
的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市
,最后才到达目的地Harp 市(乐团可多次在同一城市演出).
由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时
间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表
.
输入:
输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=100
0)开始,音乐家们要在这n 个城市作巡回演出,城市用1..n标号,其中1是起点Flute市
,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的
航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n
-1行是从城市2到其他城市(1,3,4...n) 的航班,如此下去.
每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整
数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有
航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票
是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的
场景结束.
输出:
对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵
达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,
输出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
初看这道题,很容易便可以想到动态规划,因为第x天在第y个地方的最优值只与第x
-1天有关,符合动态规划的无后效性原则,即只与上一个状态相关联,而某一天x航班
价格不难求出S=C[(x-1) mod m +1].我们用天数和地点来规划用一个数组A[1..1000
,1..10]来存储,A[i,j]表示第i天到达第j个城市的最优值,C[i,j,l]表示i城市与j城
市间第l天航班价格,则A[i,j]=Min{A[i-1,l]+C[l,j,i] (l=1..n且C[l,j,i]<>0)},动
态规划方程一出,尽可以放怀大笑了.
示范程序:
program perform_hh;
var
f,fout:text;
p,l,i,j,n,k:integer;
a:array [1..1000,1..10] of integer; {动态规划数组}
c:array [1..10,1..10] of record {航班价格数组}
num:integer;
t:array [1..30] of integer;
end;
e:array [1..1000] of integer;
procedure work;
begin
{人工赋第一天各城市最优值}
for i:=1 to n do
begin
if c[1,i].t[1]<>0
then a[1,i]:=c[1,i].t[1];
end;
for i:=2 to k do
begin
for j:=1 to n do
begin
for l:=1 to n do
begin
if (j<>l)
and (c[l,j].t[(i-1) mod c[l,j].num+1]<>0) {判断存在航班}
and ((a[i,j]=0) or (a[i-1,l]+c[l,j].t[(i-1) mod c[l,j].num+1]<a[i,j]))
{判断比当前解优}
then a[i,j]:=a[i-1,l]+c[l,j].t[(i-1) mod c[l,j].num+1]; {赋值}
end;
end;
end;
e[p]:=a[k,n]; {第p个场景的最优值}
end;
procedure readfile; {读文件}
begin
assign(f,'PERFORM.DAT'); reset(f);
assign(fout,'PERFORM.OUT'); rewrite(fout);
readln(f,n,k); p:=0;
while (n<>0) and (k<>0) do
begin
p:=p+1;
fillchar(c,sizeof(c),0);
fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
for j:=1 to i-1 do
begin
read(f,c[i,j].num);
for l:=1 to c[i,j].num do
read(f,c[i,j].t[l]);
end;
for j:=i+1 to n do
begin
read(f,c[i,j].num);
for l:=1 to c[i,j].num do
read(f,c[i,j].t[l]);
end;
end;
work;
readln(f,n,k);
end;
{输出各个场景的解}
for i:=1 to p-1 do
writeln(fout,e[i]);
write(fout,e[p]);
close(f);
close(fout);
end;
begin
readfile;
end.
四.小结
动态规划与穷举法相比,大大减少了计算量,丰富了计算结果,不仅求出了当前状态
到目标状态的最优值,而且同时求出了到中间状态的最优值,这对于很多实际问题来说
是很有用的.这几年,动态规划已在各省市信息学奥林匹克竞赛中占据相当重要的地位
,每年省赛8道题目中一般有2~3道题目属于动态规划,动态规划相比一般穷举也存在
一定缺点:空间占据过多,但对于空间需求量不大的题目来说,动态规划无疑是最佳方
法!
五.课后题目
1. m个人抄n本书,每本书页数已知,每个人(第一个人除外)都必须从上一个人抄的
最后一本书的下一本抄起(书必须整本整本的抄),求一种分配方法,使抄书页数最多的
人抄书页数尽可能少. (GDOI''99 Books).
2. 有一字符串有多种编码方式可供人选择，将这个字符串进行编码，使求得得编
码长度最短。 （GDKOI'2000 Compress)
3. Canada境内有自西向东的一系列城市：Halifax,Hamilton,Montelia,Vancouve
r...，各个城市之间可能有航班相连，也可能没有，现要求从最西的城市出发，自
西向东到达最东的城市，再返回最西的城市，除最西城市外，其他每个城市只能访问
一次，求最多能访问多少个城市．
(汕头市聿怀中学初三 黄皓 E-mail: junglyhh@163.net（Write to me Soon!) }
--
灬 灬 灬灬 灬灬 灬 灬 ════════════════════╗╮
╭╯ 灬 灬▂╱ ＿灬灬ジ ヾ 灬╰╗
║ 灬◢◢ "▔ 灬╱ 灵台无计逃神矢 风雨如磐暗故园 ▁ 灬|"|║
║ ◤, |,╱_ ◣◣ 寄意寒星荃不察 我以我血荐轩辕▕心▏ ◣|║
║ _,|\▄/ \▌◥ ▔ヾ◥◥|║
╚═ "\▌| ▔ | | /" ════════════════════════╯
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.7.236]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店