动态规划1.doc

动态规划(1)
伍先军  整理
例1 数塔
1．问题描述
设有一个三角形的数塔，顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，可以向左走，也可以向右走。如图10一1所示。

从根13出发，向左走到达11，再向右走到达7，再向左走到达14，再向左走到达7。由于7是最底层，无路可走。此时，我们找到一条从根结点开始到达底层的路径：
13—11—7—14—7
路径上结点中数字的和称为路径的值，如上面路径的值为13+11+7+14+7= 52。
同时，从图10一1中我们看到除上述路径外，还存在其他的路径，如
13—11—12—14—13
其路径的值为13＋11＋12＋14＋13＝63。
问题：当三角形数塔给出之后，找出一条路径，使路径的值最大。若这样的路径存在多条，任意给出一条即可。
2．算法分析
1．贪心法往往得不到最优解
贪心法求解的过程如下。
（1）从根13出发，在左、右两个通路中找出一个大者作为前进的方向，由于11＞8，所以选择11，即从13一11。
（2）再从11出发。在左、右两个通路中找出一个大者作为前进的方向，由于12＞7，所以选择12，因此得到通路13一11一12。
（3）再从12出发。在左、右两个通路中找出一个大者作为前进的方向，由于14＞6，所以选择14，因此得到通路13一11一12一14。
（4）再从14出发。在左、右两个通路中找出一个大者作为前进的方向，由于13＞7，所以选择13，最后得到的路径为13一11一12一14一13。
其路径上的值等于13＋11＋12＋14＋13=63
但是，我们还可以找到另外一条路径13一8一26一15一24，其路径上的值为13+8+26+15+24=86。
　
由此可见，贪心法找到的路径往往不是最优解。
2．穷举法往往是不可能的
穷举法的思想是这样的，先找出所有的路径，再在这些路径上找出值为最大的路径。如图10一2所示，路径的条数有
13一11一6，
13一11一21，
13一8一21，
13一8一40
对应的值分别为：30，45，42，61。找出最大者13一8一40。
但是，当数塔的层次比较大时，路径的条数就非常多，用穷举法求解往往不可能。设数塔的层数为n,路径的条数为P,则P＝2n-1,当层数n＝50时，路径条数P=249≈563万亿。这是一个非常大的数，即使用世界上最快的电子计算机也不能在短时间内计算出来。
3．动态规划求解
对于数塔问题，唯一正确的方法是动态规划。动态规划求解问题的过程可以归纳为两
句话： 自顶向下的分析，自底向上的计算。
如上面的数塔问题，从根结点13出发究竟选择哪一个方向前进将取决于分别从11和8出发，2条子路径上的最大值求出之后才能决定。设x为从11出发到达底的最大路径值，y为从8出发到达底最大路径值。因此
if x＞y then 选择x,且能取得到的最大值为13＋x
else 选择y,且最大值为13＋y
由此可见，从根出发查找路径的问题成为分别从11出发和从8出发查找路径的子问题。 同时查找从11出发的最大路径值的问题转换为从12出发和从7出发的查找路径最大值的子问题。当讨论到倒数第二层时，如数6，由于下面仅有2个结点，此时可以直接比较就选择一个大者作为前进的方向，因此全部求解的过程为
（1）从底层开始，本身数值即为最大值。
（2）倒数第二层的计算，将决定于底层。
（3）最后路径为13一8一26一15一24。
4．数据结构
（1）数据的规范化，为便于用数组表示数塔，我们将三角形的数塔改造为下面的形式。
（2）数组g：array[1..n,1..n,1..3] of integer表示数塔。
G[i,j,1]——表示位置（i，j）结点本身数值。
G[i,j,2]——能取得的最大值。
G[i,j,3]——前进方向，0一向下；1—向右下。
程序清单:
program exp10_1;
const n=5;
var i,j:integer;g:array[1..n,1..n,1..3]of integer;
begin
for i:=1 to n do begin {i表示层次}
for j:=1 to i do begin{j表示列数}
read(g[i,j,1]);{输入g[i,j,1]}
g[i,j,2]:=g[i,j,1];{最大值为