荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: huhaiming (一生只爱她), 信区: Program
标  题: 动态规划
发信站: 荔园晨风BBS站 (Wed May 21 10:24:18 2003), 站内信件

一、动态规划的基本思想:
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许
多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法
与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,
然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解
的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解
得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决
的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,
节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否
被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。
具体的动态规划算法多种多样,但它们具有相同的填表格式。

二、设计动态规划法的步骤:
1、找出最优解的性质,并刻画其结构特征;
2、递归地定义最优值(写出动态规划方程);
3、以自底向上的方式计算出最优值;
4、根据计算最优值时得到的信息,构造一个最优解。
步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤4可以省略
,步骤3中记录的信息也较少;若需要求出问题的一个最优解,则必须执行步骤4,
步骤3中记录的信息必须足够多以便构造最优解。

三、动态规划问题的特征:
动态规划算法的有效性依赖于问题本身所具有的两个重要性质:最优子结构性质和
子问题重叠性质。
1、最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优
子结构性质。
2、重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新
问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,
对每一个子问题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用
这些子问题的解。


四、例题
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<=1000)开始,音乐家们要在这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,
Vancouver...,各个城市之间可能有航班相连,也可能没有,现要求从最西的城市
出发,自西向东到达最东的城市,再返回最西的城市,除最西城市外,其他每个城
市只能访问一次,求最多能访问多少个城市.


--

菩提本无树,明镜亦非台

本来无一物,何处惹尘埃

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店