动规-路径.ppt

如下图所示为一个数字三角形,请编程计算从顶到底的某处的一条路径,使该路径所经过的数字总和最大。(只要求输出总和)
规定:
⑴一步可沿左斜线向下或右斜线向下走;
⑵图形行数小于等于100;
⑶三角形中的数字为0,1,…,99;
输入:右下图数据应以如下所示格式输入
5(行数)
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出:30
数字三角形
力芍辅崎赣韶邦车宁糙奈耕猖柄晒窗磨顺矿诉瞒须祝药杖齿漾宵厌么辟碟动规-路径动规-路径
按照三角形的行进行阶段划分,若行数为n,则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段各点到第n行的最大和,再依次求出第n-2 阶段、第n-3 阶段…第1阶段各点至第n行的最大和。
设f[i,j]为从第i阶段中的第j个点至第n行的最大和;
由于f[i,j]只和第i+1阶段的状态和本阶段的点有关系,符合无后效性原则;在每一个阶段都要求出这个阶段的各个点到第n行的最大和,也符合最优化原则。因此可以用动态规划的方法来求解,以走到每一行时所在的位置作为状态,决策就是向左下走或向右下走。其状态转移方程可以写为:
f[i,j]=max{ a[i,j]+f[i+1,j] , a[i,j]+f[i+1,j+1] }
(i=1,2,3,4,…,n-1, 1<=j<=i)
f[n,j]=a[n,j](1<=j<=n){初始状态}
    最后,f[1,1]即为所求。
劳颤钓眼计底噬驻爹按锻街恒俱客神橡狙煮眨翘缴械磺烫博蛆销迪淌骗诡动规-路径动规-路径
var
n,i,j:integer;
a:array[1..100,1..100] of integer;
f:array[1..100,1..100] of integer;
begin
readln(n);
for i:=1 to n do
for j:=1 to i do read(a[i,j]);
for i:=1 to n do f[n,i]:=a[n,i];
for i:=n-1 downto 1 do
for j:=1 to i do
if f[i+1,j]>f[i+1,j+1] then f[i,j]:=f[i+1,j]+a[i,j]
else f[i,j]:=f[i+1,j+1]+a[i,j];

writeln(f[1,1]);
end.
阶段
状态
决策
状态转移方程
4
5
2
6
5
7
12
10
10
20
13
10
23
21
30
位蓄蔡补座赦钓韦砾昨烙猴睬客堆滤感室劳椒宽池缉卸袜壁悼蓝胞屋迟澄动规-路径动规-路径
下图所示是城市道路示意图。每条边上的数字为该段街道的长度。求从A到B地(只允许往右和往上走)的最短路径长度。
1 3 2 3
2 2 1 4
2 3 4 5
2 3 1 2
2 3 2
1 4 2
2 1 1
2 2 3
3 3 4
A(0,0)
B(3,4)
街道最短路径
牟萝悍腮氰馁玲披券拖抿减橙乃题峨腾铂缺中暴澳蓄峡领冰屹综易骑捅辊动规-路径动规-路径
我们以图中的对角线行来划分阶段,共m+n个阶段。设d[i,j]表示点(0,0)到点(i,j)的最短路径长度,v[i,j]表示点(i-1,j)到点(i,j)的竖向距离,h[i,j]表示点(i,j-1)到点(i,j)的横向距离,则
d[i,j]=min{ d[i-1,j] +v[i,j] , d[i,j-1] +h[i,j] }
1 3 2 3
2 2 1 4
2 3 4 5
2 3 1 2
2 3 2
1 4 2
2 1 1
2 2 3
3 3 4
A(0,0)
B(3,4)
2
5
7
1
4
6
9
3
5
6
10
7
6
8
13
8
8
9
11
0
教印沫思例否秀夫彝微身丹础权殖仙诬距楔伪膜腻及苟涂集臣孜捡友内蕉动规-路径动规-路径
var
i,j,k,t,m,n:integer;
h,v:array[0..100,0..100] of integer;
d:array[0..100,0..100] of longint;
function min(x,y:integer):longint;
begin
if x>y then min:=y
else min:=x;
end;
begin
readln(m,n);{m+1行,n+1列}
for i:=0 to m do{东西向}
begin
for j:=1 to n do read(h[i,j]);
readln
end;
for i:=1 to