垃圾回收站

　　　　　　　　　　　　　我对动态规划算法的教学

　　　　　　　　　　　　　　　　　　　广东肇庆中学 胡德林

　　全国青少年信息学奥林匹克联赛（NOIP）是一项面向全国青少年的信息学竞赛和普及活动，旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀的计算机人才。
　　竞赛分两轮进行：初试和复试。初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。复试形式为上机，侧重考察学生对问题的分析理解能力，数学抽象能力，驾驭编程语言的能力和编程技巧、想象力和创造性等。
复试的题型和形式向全国信息学奥赛（NOI）靠拢，全部为上机编程题。在《联赛大纲》的试题的知识范围中，要求参赛选手掌握的算法处理有初等算法，排序算法，查找算法，回溯算法，离散数学知识的应用，分治思想，模拟法，贪心法，简单搜索算法（深度优先、广度优先、以及搜索中的剪枝），动态规划的思想及基本算法。本人曾对近几年的复赛题目进行过分析，发现解题所用的算法多为模拟法、贪心法、搜索算法和动态规划算法等。因此，本人在近两年的奥赛辅导中，对上面提到的四种算法可谓”情有独钟”。下面谈谈本人对动态规划算法教学的一些做法。
　　一、温故而知”新”， 发现问题
　　首先，列出一道学生可以用搜索算法解决的题目，让学生编程解题，一方面让学生熟习用搜索算法来解题，另一方面让学生知道搜索算法的缺点–算法效率低。题目如下：
　　[例1]如下所示为一个数字三角形：
　　7
　　3 8
　　8 1 0
　　2 7 4 4
　　4 5 2 6 5
　　请编一个程序计算从顶至底的某一条路径，使该路径所经过的数字的总和最大。
　　●每一步可沿直线向下或右斜线向下走；
　　●1<=三角形行数<=100；
　　●三角形中的数字为整数0，1，…，99。
　　输入：输入文件第一行为一个自然数，表示数字三角形的行数n(1<=n<=100)，接下来的n行表示一个数字三角形。
　　输出：输出文件仅有一行包含一个整数（表示要求的最大总和）。
　　学生用搜索算法编写上述题目的程序后，师生共同对程序进行了测试。首先是程序的正确性测试，绝大部分同学的程序是正确的；然后对正确程序的数据规模进行测试，记录下程序对不同数据规模(n值)运行所需要的时间，如下表：
　　数据规模n <=23 24 25 26 27 28 29 30 …
　　所需时间(秒) <=1 1 3 6 13 28 60 122 …
　　从上表可以看出，当n大于25时，运行所需时间就超过1秒，并且随着n的增长，所需时间随指数增长，所以，即使用”快”的计算进行测试，也是不能解决问题的。题目的数据规模(n值)是100，而程序只能解决n<24的数据规模(竞赛时要求对所有的测试数据都要在1秒钟以内出结果)。因此，我们需要寻找更好设计算法。
　　二、分析原因，知识迁移
　　现在的计算机每秒运行指令在1千万条以上，上面题目最多只有几千个数据，为什么要运行那么长时间呢？由于用学生熟悉的搜索算法编程不能完全解决问题，遇到了自以为能解决的问题但不能解决。因此，他们乐意与老师一道分析问题的原因，以寻找更好的算法。下面是某学生解题的一个算法：
　　FUNCTION MAXS(I,J:INTEGER):INTEGER;
　　 VAR
　　 X,Y:INTEGER;
　　BEGIN
　　 IF I=N THEN MAXS:=A[I,J]
　　 ELSE BEGIN
　　X:=MAXS(I+1,J);
　　Y:=MAXS(I+1,J+1);
　　IF X>Y THEN MAXS:=X+A[I,J]
ELSE MAXS:=Y+A[I,J];
　　　 END;
　　　 END;
　　我们分析上面算法，算法进行了很多重复的运算，例如第三行的第二个数，在计算第二行第一个数时调用计算了一次，计算第二行第二个数时又调用计算了一次，共调用计算了2次。同样道理，得出各行数据调用运算的次数如下：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
… … … … … … …
　　上面的调用运算次数实际上是一个杨辉三角。我们编写了一个简单的程序，计算出运算次数与n的关系如下表。
　　数据规模n 1 2 3 4 5 10 20 30 40 50 100
　　运算次数 1 3 7 15 31 1023 106 109 1012 1015 1030
　　从上表可以看出，搜索算法的时间复杂度随指数增长(这个分析同时也引导学生学会怎样估算时间复杂度)。这也和我们测试程序的时间复杂度相吻合，所以原算法超时。
　　如果我们说明一个数组B，把第一次计算过的数结果保存起来，在计算的每一步，先进行判断，看下面的数是否计算过（是否等于-1），若计算过则直接调用数组B的值，只有未计算过时才进行计算，　　并把计算结果同时保存到数组B，以让其它计算时便用。算法MAXS修改如下：
　　FUNCTION MAXS(I,J:INTEGER):INTEGER;
　　 BEGIN
IF I=N THEN BEGIN MAXS:=A[I,J];B[I,J]:=A[I,J] END
ELSE BEGIN
IF B[I+1,J]=-1 THEN B[I+1,J]:=MAXS(I+1,J);
IF B[I+1,J+1]=-1 THEN B[I+1,J+1]:=MAXS(I+1,J+1);
IF B[I+1,J]>B[I+1,J+1] THEN
B[I,J]:=B[I+1,J]+A[I,J]
ELSE B[I,J]:=B[I+1,J+1]+A[I,J];
MAXS:=B[I,J];
END;
END;
　　我们对稍作修改的程序重新进行数据规模进行的测试，记录下程序对不同数据规模(n值)运行所需要的时间，如下表：
　　数据规模n <=23 24 25 50 100 200 500 1000 …
　　所需时间(秒) <=1 <=1 <1 <=1 <=1 <=1 <=1 <=1 …
　　根据运行结果，学生会惊奇地发现：对原算法只是稍作修改，运行时间即产生这么大的差别。这么好的算法，学生当然乐意接受。
　　三、总结规律，发现新算法
　　分析上面的算法，我们发现：算法的MAXS函数只是在计算B数组各个元素的值，并且从最后一行起向上计算，直到计算到B[1,1]，就是我们要求的结果。因此算法变成自底向上计算数组B各元素的值。　　算法变成如下：
　　FUNCTION MAXS(I,J:INTEGER):INTEGER;
VAR
I,J:INTEGER;
BEGIN
FOR J:=1 TO N DO B[N,J]:=A[N,J];
FOR I:=N-1 DOWNTO 1 DO
FOR J:=1 TO I DO
IF B[I+1,J]>B[I+1,J+1] THEN
B[I,J]:=B[I+1,J]+A[I,J]
ELSE
B[I,J]:=B[I+1,J+1]+A[I,J];
MAXS:=B[1,1];
END;
　　这个算法就是动态规划算法，其时间复杂度是O(n2)，如果问题的规模N=1000，用动态规划计算比用搜索计算相同问题的N=20还要快。
　　四、巩固练习，掌握步骤
　　给出另一道可用动态规划算法解决的题目，让学生完成，作为巩固练习，题目是”拦截导弹”问题(略)。然后，师生共同寻找出下面使用动态规划算法求解问题的解题步骤。
　　设计一个动态规划算法，通常可按以下几个步骤进行：
　　（1）把问题划分为若干个阶段，分析各阶段最优解的性质，并刻划其结构特征。
　　（2）递归地定义最优值或总结出各计算阶段最优值的表达式。
　　（3）以自底向上的方式或自顶向下的方式记忆计算出各阶段的最优解。
　　五、列举反例，会用算法
　　动态规划的时间复杂虽然很优秀、很好用，但并不是所有的问题都能用动态规划解决的，例如下面两问题：
　　[例2]在数字三角形问题中，三角形中的数字为-100至100的整数。请编一个程序计算从顶至底的某一条路径，使该路径所经过的数字的总和最接近0。
　　[例3]求下图中从A点到B点的最短路径（可向右走也可左走）。

　　例2因为不是求最大值，也不是求最小值，不符合最优原则，所以不能使用动态规划的思想来求解。例3因为计算中间的数据时不但要考虑左边的点的数据，还的要考虑右边的点的数据，不符合无后效性原则，所以也不能使用动态规划的思想来求解。
由以上两例子可以总结出满足动态规划的问题必需满足两个特征：一是最优原则，二是无后效性。
动态规划算法是学生较难掌握的一种算法，但学生一但掌握了该算法，将受用无穷。并且，用动态规划算法编程求解的题目，对所有的测试数据一般都能通过。因此，教师在辅导时除与学生一齐发现算法，总结规律外，还要多给一些习题让学生编程求解，使学生能熟练地用动态规划的思想解决多种不同的问题。

参考文献：
1、信息学奥林匹克网站：http://www.noi.cn/；
2、曹文主编，《全国青少年信息学奥林匹克联赛培训教材(中学高级本)》；
3、郭嵩山主编，《广东省青少年信息学(计算机)奥林匹克竞赛资料集》。