动态规划基础篇.doc

《动态规划基础篇.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、刖s动态规划算法在近儿年的各级信息学奥林匹克竟赛屮代替了搜索算法的统治地位，成为要想在信息学竞赛中取得好成绩必须掌握的一种算法。然而很多同学学习动态规划时，被它复杂的算法定义以及表示方法弄的晕头转向，不知所以，即便勉强掌握，往往一遇到复朵一点的动态规划，又不知如何下手分析出正确的结果。为了使同学们能熟练、透彻地掌握这种算法。我们通过动态规划准备篇、基础篇、中级篇和鬲级篇共四篇文章来进行一个系统地讲解。希望能对同学们的学习有所帮助。动态规划基础篇一、动态规划的算法思想（1-1）引例1:现有一张地图，各结点代表城市，两结点间连线代表道路

2、，线上数字表示城市间的距离。如图所示，试找出从结点1到结点10的最短路径。解法一：本问题的解决可采用一般的穷举法，即把从结点1至结点10的所有道路列举出来，计算其长度，再进行比较，找出最小的一条。虽然问题能解决，但采用这种方法，当结点数增加，其运算量将成指数级增长，故而效率是很低的。解法二：分析上图可知，各结点的排列特征：（1）可将各结点分为5个阶段；（2）每个阶段上的结点貝跟和邻阶段的结点相连，不会出现跨阶段或同阶段结点札（连的情况，如不会出现结点1与结点4连、结点4与结点5连的情况。（3）除起点1和终点10外，其它各阶段的结点既

3、是上一阶段的终点，乂是下一阶段的起点。例如第三阶段的结点4、5、6,它即是上一阶段结点2、3中某结点的终点，乂是下一阶段结点7、8、9中某结点的起点。所以根据分析划分若干个阶段（如图）划分阶段后我们思考从结点10向结点1逆向來推导：即第五阶段由第四阶段推出，第四阶段由第三阶段推出，…，第二阶段由第一阶段推出。具体的每阶段的推出又时相同的：每个阶段的点与起始点的距离等于与其上一阶段相连的所有点与起始点的距离加上与上一阶段相连的所有点的两点的距离的最小值。此话念起来和当拗口，但是理解起来并不难。举例：我们设f(n)表示最短路径，d(a,

4、b)表示结点a到结点b的f(10)=min{f(7)+d(10,7),f(8)+d(10,8),f(9)+d(10,9)};f(9)=min{f(4)+d(9,4)};f(8)=min{f(5)+d(8,5),f(6)+d(8,6)};f(7)=min{f(5)+d(7,5)};f(6)=min{f(3)+d(6,3)};f(5)=min{f(3)+d(5,3),f(4)+d(5,4)};f(4)=min{f(3)+d(4,3),f(2)+d(4,2)};f(3)=min{f(1)+d(3,1)};f(2)=min{f(1)+d(2

5、,1)};f(1)=0o我们在对其中的某个点具体分析，如第三阶段的结点5,可选择1-2-5和仁3・5这两条路径，后者的费用要小于前者。那么考虑一下，假设在所求的结点1到结点10M短路径中要经过结点5,那我们在结点1到结点5ZI'可会取那条路径呢？显然，无论从结点5出发以后的走法如何，前面选择1-3-5这条路都总是会优J*-1-2-5的。也就是说，当某阶段结点一定时，后面各阶段路线的发展不受这点以前各阶段屮的点(如2,3)的影响。反之，到该点的最优决策也不受该点以后各点的发展影响。现在我们计算最短路径时，该正向思考了，从阶段1开始，往

6、后依次求出结点1到阶段2、3、4、5各结点的最短距离，最终得出答案。在计算过程屮，到某阶段上一结点的决策,只依赖于上一阶段的计算结果，与其它无关。例如，已求得从结点1到结点5的授优值是6,到结点6的最优值是5,那么要求到下一阶段的结点8的最优值，只须比鮫min{6+5,5+5}即可。(1-2)引例2：数字三角形，在下图中求从顶至低某处的一条路径，使该路径所经过的数字的总和最大。(1)每一步可任意走但不能跳跃下一行(2)每一步只能向左下或右下走也不能不能跳跃下一行。738810274445265解：对于第一问很简单，将每行的最人值找出

7、来，再连起来就可以了。这是贪心算法，也可写成一个递推公式：n表示行数，max(n)表示笫n行的最大值，sum(n)=sum(n-1)+max(n);sum(1)=max(1)；对于第二问可不可以用贪心算法呢？答案是否定的。首先贪心有两种，一种是从顶端向左下或右下的两个选择屮选择最人的一个。一种是选择整个数屮最人的，从顶端向这个最人数方向前进。首先这两种贪心都不能保证数字Z和最大，反例请同学们口己给出。其次这两种贪心并不能同时使用，绝大多数二者取其一，所以两种贪心都不算是真正的贪心。那么如何思考呢？其实很简单，我们将每个位置编上号，并

8、J1将所有的路线连上。如图所示，看一看，与上而的多段图是不是类似。所以我们也完全利用上例的解题思路来解决本题。首先我们设data(i,j)^(i,j)ft置的数据，sum(i,j)为到达该点的最大数字和。有如下公式：在n行数字三角形中