[工学]c_c++动态规划与递推教程.pptVIP

动 态 规 划 本章介绍最优化问题的一种算法设计方法——动态规划。对于这一方法，在数据结构中，求图的关键路径时曾使用过这一方法。它的基本思想是：①段化；②自顶向下的分析；③从底向上的计算。这种方法的正确性建立在最优性原理上。 5.1 最优性原理 例如，假定对贪婪法中的背包问题加上一些限制，xi 仅限于取值 0 和 1 ，即在约束 条件 考察本节开始提出的0/1背包问题，用KNAP(1，j，Y)表示问题在约束条件 下使目标 极大。 且满足约束条件： 5.2 一些简单例子 简单地说，动态规划解题的过程分为三步：①段化；②自顶向下的分析，测试问题本身是否满足最优化原理；③从底向上的计算，实现动态规划过程。 例5.1 数塔。 设有一三角形的数塔，如图5.2所示。求一自顶到塔底的路径，且该路径上结点的值的和最大。 例5.2 中国象棋马。 在 m×n 的棋盘上的 P 点处有一中国象棋的马，而另一点 Q 为马的家，约定 Q 在 P 的右边，见图5.5(a) (假定 m=n=5)。试求马从 P 到 Q 的所有通路数。 例5.3 最小代价子母树。 设有 n 堆沙子(n≥2)排成一排。每堆沙子的质量由向量 W 给出。现在要将 n 堆沙子归并成一堆。规则是：每次只能将相邻的两堆沙子堆成一堆，经过 n-1 次归并之后成为一堆。其总代价为进行过程中新产生的沙堆的质量之和。这个代价最小的归并树为最小代价子母树。如图5.6(a)、(b)描述了一实例的两种归并方法。 分析： 当n=2时，仅有一种归并方法； 当n=3时，有2种归并方法(如图5.7)。 从图5.7可以看出(a)的总代价=20+28；(b)的总代价=15+28。最后一次归并的代价为原始3堆沙子的总质量。因此，总的代价的大小取决于第一次归并的代价，(b)优于(a)； 当n=4时，有 5 种归并方法。如图5.8。 最小归并是 (b)。从递推角度看，5 种方法可以分为 3 类： 第1类，(a)、(b)。基本方法是先归并前3 堆，再归并最后一堆。由于最后都是第4堆，所以归并前3堆时不同的方法将决定归并的优劣。而 n =3 时，图5.7中(b)优于(a)。因此，n=4时，(b)优于(a)； 第2类，(d)、(e)。基本方法是先归并后3堆，再归并第1堆。由于最后都是第1堆，所以，归并后3堆时不同的方法将决定归并的优劣。因此，n =4 时，(d) 优于(e)； 第3类，仅有一种方法(c)。分别归并相邻两堆，再归并成1堆。 定义 f(i,j) 表示从第i堆到第j堆沙子的归并的最小代价，g(i,j) 表示第i堆到第j堆沙子的质量和。于是： f (1,4)=min{f(1,3), f(1,2)+f(3,4),f(2,4)}+g(1,4) 而 f (1,3)=min{f (1,2), f (2,3)}+g (1,3) f (1,2)=g(1,2); f (3,4)=g(3,4); f (2,3)=g(2,3) f (2,4)=min{f (2,3), f (3,4)}+g(2,4) 一般地： f (1,n)=min{f (1,n-1),f (1,2)+f(3,n),f(1,3)+f(4,n), …,f (2,n)}+g(1,n) 算法5.1 procedure mincpt(w); /w[1..n]：n堆沙子的质量序列； g[1..n ;1..n]∶g[i, j]= w[k]； f [1..n ;1..n]∶f [i , j] 表示第 i 层从第 j 个位置开始 i 堆沙子的最小归并代价，并约定 f [1,i] = 0/ begin 计算g[i,j]=g[j,i]= w[k]，1≤i≤n, 1≤j≤n; f [i,j]  0,1≤i≤n,1≤j≤n； for i  2 to n do /i 表层次，也是归并沙子的堆数/ for j 1 to n-i+1 do /j表示归并沙子的起始位置/ begin min  f [i-1 ,j]; for k  i-1 step–1 until 1 do if min f [k ,j]+f [i-k，j+k] then min  f [k ,j]+f [i-k ,j+k]; f [i,j]  g [j ,i+j-1]+min; end; return (f [n ,1]); endp;