- 注册时间
- 2004-8-29
- 最后登录
- 1970-1-1
|
发表于 2004-9-12 10:20:00
|
显示全部楼层
>> 动态规划
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都要做出决策，从而使整个过程达到最好的活动效果。因此，各个阶段决策确定后，组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程，就称为多阶段决策过程，这种问题称为多阶段决策问题。
在多阶段决策问题中，各个阶段采取的决策。一般来说是和时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有"动态"的含义，我们称这种解决多阶段决策最优化的过程为动态规划。
动态规划特征：
动态规划的显著特征是:无后效性，有边界条件，且一般划分为很明显的阶段。
动态规划一般还存在一条或多条状态转移方程。
例题 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);
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>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.
>> 标号算法
标号法是一种最佳算法，多用于求图的最短路问题。
一、标号法的概念：
所谓标号，是指与图的每一个顶点相对应的一个数字。标号法可以说是动态规划，它采用顺推的方法，对图的每一边检测一次，没有重复的回溯搜索，因此标号法是一种最佳算法。
二、标号法的算法流程：
现有一图G，求从起点Vs到终点Ve的最短距离。 设：
Sum(j)───顶点Vj的标号，代表的是Vs到Vj的最短距离。
Vj已标味着Vs到Vj的最短路以及这条路径的长度已求出。
M(i,j)───Vi到Vj的非负长度。
H(j)───顶点Vj的前趋结点。 标号法的算法流程如下：
sum（s）←0
↓
Vs进入队列L
↓
-----→移出队列L的队首Vk←-----
| ↓ |
| Vk是不是Ve------------------|---→计算结束打印路径
| N∣ Y |
| ↓ |
| 由Vk扩展出结点Vj |
| （Vk与Vj之间相连） |
| Sj←Sum(k)+M(k，j) |
| ↓ |
| Sj小于Sum（j） |
| | |
| Y | N |
| | -------------------------
| |
| ↓
| Sum（j）←Sj
| H（j）← Vk
| Vj加入队列L并对队列L按Sum值由小到大排序
| ↓
---------------
注意：1.只有两个顶点间的距离为非负时，才可用标号法。 2.只有队列的首结点是目标结点时，才可停止计算。否则得出的不一定是最优解。
例题解析：
1.相邻项序列(GDOI97第四题)
问题描述：
对于一个N*N(<=100)的正整数矩阵M，存在从M[A1，B1] 开始到M[A2，B2]结束的相邻项序列.两个项M[I，J]和M[K，L]相邻的件是指满足如下情况之一：
(1)I=K+-1和J=L
(2)I=K和J=L+-1。
任务：从文件中输入矩阵M，再读入K(K<=4)组M[A1，B1]和M[A2，B2]的值。对于每一组M[A1，B1]和M[A2，B2]，求一相邻项序列，使得相邻项之差的绝对值之和为最小。
输入格式：
4 ───N
1 9 6 12 ───每行N个数据，共N行
8 7 3 5
5 9 11 11
7 3 2 6
2 ───K
4 1 1 4 ───表示A1,B1和A2,B2的值，共K行 2 2 3 4
输出格式：
1 17 ───第一组数据相邻项之差的绝对值之和的最小值是17
7 5 8 7 9 6 12───第一组数据的相邻项序列
2 4
7 9 11 11
解析：本题若将相邻的两个数看作是两个顶点，两个数之差的绝对值作为权，则问题转化成求两个顶点的最短路问题。 设：Sum[I,J]为从起点Vs到结点M[I,J]的最短距离。 H[I,J]记录结点M[I,J]的前趋结点。 L为记录待扩展的结点的队列。 鉴于数组进行排序时速度较慢，所以用链表作为记录结点的队列的类型，适于排序。
参考程序：
Program gdoi974;
const fang:array [1..4,1..2] of integer =((-1,0),(0,-1),(1,0),(0,1));
{上下左右四个方向}
type
{定义POINT类型,其中X,Y为结点在矩阵中的坐标,NEXT为队列中的后继结点}
point=^note;
note=record
x,y:byte;
next:point;
end;
var
sum:Array [1..100,1..100] of integer;
m:Array [1..100,1..100] of integer;
h:Array [1..100,1..100,1..2] of byte;
f1,f2:text;
a,b,x1,y1,x2,y2,n,k,zz:integer;
procedure print;
var
a,b,x,y,x3,y3:integer;
c:array [1..100] of integer;
flag:boolean;
begin
flag:=true; a:=1; c[a]:=m[x2,y2];
x:=x2; y:=y2;
while flag do
begin
a:=a+1; x3:=x; y3:=y;
x:=h[x3,y3,1]; y:=h[x3,y3,2];
c[a]:=m[x,y];
if (x=x1) and (y=y1) then flag:=false;
end; {求出整条路径，放入数组C中}
writeln (f2,zz,' ',sum[x2,y2]);
for b:=a downto 1 do
write (f2,c,' '); {打印结果}
writeln (f2);
end;
procedure add(x,y,i:integer;var l:point);
var
e,f,g:point;
a,b,c:integer;
flag:boolean;
begin
new (e);
e^.x:=x; e^.y:=y;
if i=0 then l^.next:=e {加入队列}
else begin
f:=l; g:=f^.next; flag:=true;
for a:=1 to i do
begin
if sum[g^.x,g^.y]>sum[x,y] then begin
e^.next:=g; f^.next:=e; flag:=false; a:=i; {加入队列}
end;
f:=f^.next; g:=f^.next;
end;
if flag then f^.next:=e; {加入队列}
end;
end;
procedure try(xz,yz:byte);
var
a,b,c,sj,x,y,x1,y1:integer;
e,l,v:point;
flag:boolean;
begin
fillchar (sum,sizeof (sum),255); {置Sum值为-1}
sum[xz,yz]:=0;{置起点Sum值为0}
flag:=true;
new (e); e^.x:=xz; e^.y:=yz;
new (l); l^.next:=e; {起点进入队列}
c:=1; {现在队列结点个数}
while flag do
begin
v:=l^.next; dispose (l); {取出首结点V}
l:=v; c:=c-1;{指针下移一位，结点个数减一}
x:=v^.x; y:=v^.y;
if (x=x2) and (y=y2) then flag:=false; {若为目标结点，则结束计算}
if flag then
begin
for a:=1 to 4 do {向四个方向扩展}
begin
x1:=x+fang[a,1];
y1:=y+fang[a,2];
if (x1>0) and (x1<=n) and (y1>0) and (y1<=n) then
begin
sj:=sum[x,y]+abs (m[x,y]-m[x1,y1]);
if (sj < sum[x1,y1]) or (sum[x1,y1]=-1) then
begin
sum[x1,y1]:=sj;
h[x1,y1,1]:=x; h[x1,y1,2]:=y;{记录路径}
add(x1,y1,c,l); {将新扩展出来的结点进入队列}
c:=c+1; {结点个数加一}
end;
end;
end;
end;
end;
print;{打印结果}
end;
Begin
assign (f1,'gdoi974.dat');
assign (f2,'gdoi974.out');
reset (f1); rewrite (f2);
readln (f1,n);
for a:=1 to n do
begin
for b:=1 to n do
read (f1,m[a,b]);
readln (f1);
end; {读入数组}
readln (f1,k);
for a:=1 to k do
begin
zz:=a;
readln (F1,x1,y1,x2,y2); {读入任务}
try(x1,y1);
end;
close(f1);
close(f2);
End.
[此贴子已经被作者于2004-9-12 10:22:14编辑过]
|
|
楼主