《动态规划》PPT课件.ppt

第第3 3章章 动态规划动态规划 理解动态规划算法的概念。 掌握动态规划算法的基本要素 (1) 最优子结构性质 (2) 重叠子问题性质 掌握设计动态规划算法的步骤。 (1) 找出最优解的性质，并刻划其结构特征。 (2) 递归地定义最优值。 (3) 以自底向上的方式计算出最优值。 (4) 根据计算最优值时得到的信息，构造最优解。 学习要点: 2 (1) 矩阵连乘问题； (2) 最长公共子序列； (3) 最大子段和; (4) 凸多边形最优三角剖分； (5) 多边形游戏； (6) 图像压缩； (7) 电路布线； (8) 流水作业调度； (9) 背包问题； (10) 最优二叉搜索树。 通过应用范例学习动态规划算法设计策略 3 动态规划基本步骤动态规划基本步骤 n 找出最优解的性质，并刻划其结构特征。 n 递归地定义最优值。 n 以自底向上的方式计算出最优值。 n 根据计算最优值时得到的信息，构造最优解。 n 13是动态规划算法最基本的步骤, n 若需要最优解, 则必须执行步骤4 4 完全加括号的矩阵连乘积完全加括号的矩阵连乘积 n 完全加括号的矩阵连乘积可递归地定义为： n 单个矩阵是完全加括号的； n 矩阵连乘积A是完全加括号的，则A可表示为2个完 全加括号的矩阵连乘积B和C的乘积并加括号，即 A=(BC) n 设有四个矩阵A, B, C, D，总共有五种完全加括号的方式 : (A(BC)D) (A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D)5 完全加括号的矩阵连乘积完全加括号的矩阵连乘积 n 设有四个矩阵A, B, C, D，它们的维数分别是： A=5010, B=1040, C=4030, D=305 n 矩阵A和B可乘的条件是: 矩阵A的列数等于矩阵B的行数. n 设A是pq的矩阵, B是qr的矩阵, 则乘积是pr的矩阵;计 算量是pqr. n 上述5种完全加括号方式的计算工作量为: (A(BC)D), (A(B(CD), (AB)(CD), (AB)C)D), (A(BC)D) 16000, 10500, 36000, 87500, 34500 BC: 104030 = 12000, (BC)D: 10305 = 1500, (A(BC)D): 50105 = 25006 示例 7 示例 8 矩阵连乘问题矩阵连乘问题 n定义：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘 的，i=1,2,n-1。考察这n个矩阵的连乘积A1A2An。 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有 许多不同的计算次序。这种计算次序可以用加括号的方 式来确定。 n若一个矩阵连乘积的计算次序完全确定，也就是说该连 乘积已完全加括号，则可以依此次序反复调用2个矩阵 相乘的标准算法计算出矩阵连乘积 9 算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题： (A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下： 矩阵连乘问题矩阵连乘问题 n 给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的， i=1，2，n-1。如何确定计算矩阵连乘积的计算次序 ，使得依此次序计算矩阵连乘积需要的数乘次数最少？ n 穷举法：列举出所有可能的计算次序，并计算出每一种 计算次序相应需要的数乘次数，从中找出一种数乘次数 最少的计算次序。 10 矩阵连乘问题矩阵连乘问题 n 穷举法 n 动态规划 q 将矩阵连乘积AiAi+1Aj 简记为Ai:j, 这里ij; q 考察计算Ai:n的最优计算次序。 n设这个计算次序在矩阵Ak和Ak+1之间将矩阵 链断开，1k 0) return mij; if (i = j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 计算最优值计算最优值 n 由于在所考虑的子问题空间中，总共有(mn)个不同的子问题 ，用动态规划算法自底向上地计算最优值能提高算法的效率。 01234. n 000000 0 10 20 30 40 m0 i j 29 void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 计算最优值计算最优值 0123456 yiBDCABA 0xi0000000 1A0000111 2B0111122 3C0112222 4B0112233 5D0122233 6A0122334 7B0122344 i j 30 n 由数组b构造最长公共子序列 void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutsum) sum=thissum; besti=i; Bestj=j; return sum; n 算法有3重循环，复杂性为O(n3)。 34 1. 一个简单算法 n一个简单算法： int MaxSum(int n, int *a, int for(i=1;isum) sum=thi ssum; besti=i; Bestj=j; return sum; n算法有3重循环，复杂性为O(n3)。 n由于有： n算法可作如下改进： int MaxSum(int n, int *a, int for(i=1;isum) s um=thissum; b esti=i; b estj=j; n改进后的算法复杂性为O(n2) 。 35 2. 分治方法求解 n 从问题的解的结构可以看出，它适合于用分治策略求解： q如果将所给的序列a1:n分为长度相等的两段a1:n/1和 an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大子 段和有三种情形： a1:n的最大子段和与a1:n/2的最大子段和相同； a1:n的最大子段和与an/2+1:n的最大子段和相同 ； a1:n的最大子段和为下面的形式。 1 n n/2ij s1s2 36 2. 分治方法求解 int MaxSubSum(int a , int left, int right) int sum=0; if (left=right)sum=aleft0?aleft:0; elseint center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int rightsum=MaxSubSum(a,center+1,right); int s1=0;leftsum=0; for (int i=center;i=left;i-) leftsum+=ai; if (leftsums1) s1=leftsum; int s2=0;rightsum=0; for (int i=center+1;is2) s2=rightsum; sum=s1+s2; if (sum0时bj=bj-1+aj，否则bj=aj。 n 则计算bj的动态规划递归式bj=maxbj-1+aj，aj，1jn。 123456 ai-211-413-5-2 b(初值=0)-2117201513 sum01111202020 38 3. 动态规划方法求解 n 据此，可设计出求最大子段和的动态规划算法如下： int MaxSum(int n, int a) int sum=0; /sum是bj(1jn)的最大值 int b=0; for (int i=1;i0) b+=ai; else b=ai; if (bsum) sum=b; return sum; n 显然该算法的计算时间为O(n)。 123456 ai-211-413-5-2 b(初值=0)-2117201513 sum01111202020 39 4. 算法的推广 n 最大矩阵和问题，略 n 最大m子段和问题，略 40 流水作业调度流水作业调度 n n个作业1，2，n要在由2台机器M1和M2组成的流水线 上完成加工。 n 每个作业加工的顺序都是先在M1上加工，然后在M2上加工。 n M1和M2加工作业i所需的时间分别为ai和bi。 n 流水作业调度问题要求确定这n个作业的最优加工顺序，使得 从第一个作业在机器M1上开始加工，到最后一个作业在机器 M2上加工完成所需的时间最少。 123456 A2571052 B3841134 41 流水作业调度流水作业调度 n 直观上，一个最优调度应使机器M1没有空闲时间， 且机器M2的空闲时间最少。在一般情况下，机器 M2上会有机器空闲和作业积压2种情况。 n 设全部作业的集合为N=1，2，n。S N是 N的作业子集。 q 在一般情况下，机器M1开始加工S中作业时，机器M2还 在加工其它作业，要等时间t后才可利用。 q 将这种情况下完成S中作业所需的最短时间记为 T(S,t)。 n 流水作业调度问题的最优值为T(N,0)。 42 n 设是所给n个流水作业的一个最优调度，它所需的加工 时间为 a(1) +T。 q 其中T是在机器M2的等待时间为b(1)时，安排作 业(2)， (n)所需的时间。 n 记S=N-(1)，则有T=T(S, b(1) )。 流水作业调度流水作业调度 (1 ) (2 ) (3 ) (n ) A a (1) a (2) a (3) a (n) B b (1) b (2) b (3) b (n) 43 A B a (1) b (1) (1)S=N-(1) T=T(S, b(1) ) T 44 流水作业调度流水作业调度 n 由流水作业调度问题的最优子结构性质可知， n 推广到一般情形下,有: M1 M2 45 流水作业调度流水作业调度 n 推广到一般情形下,有: 46 JohnsonJohnson不等式不等式 对递归式的深入分析表明，算法可进一步得到简化。 n 设是作业集S在机器M2的等待时间为t时的任一最优调 度。若(1)=i, (2)=j。则由动态规划递归式可得: T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S- i,j,tij) 47 JohnsonJohnson不等式不等式 对递归式的深入分析表明，算法可进一步得到简化。 n 设是作业集S在机器M2的等待时间为t时的任一最优调 度。若(1)=i, (2)=j。则由动态规划递归式可得: T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S- i,j,tij) 48 JohnsonJohnson不等式不等式 对递归式的深入分析表明，算法可进一步得到简化。 n 设是作业集S在机器M2的等待时间为t时的任一最优调 度。若(1)=i, (2)=j。则由动态规划递归式可得: T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S- i,j,tij) 如果作业i和j满足minbi,ajminbj,ai， 则称作业i和j满足Johnson不等式。 49 流水作业调度的流水作业调度的JohnsonJohnson法则法则 n 交换作业i和作业j的加工顺序，得到作业集S的另一调度 ，它所需的加工时间为T(S,t)=ai+aj+T(S-i,j,tji) 其中， n 当作业i和j满足Johnson不等式时，有 如果作业i和j满足minbi,ajminbj,ai， 则称作业i和j满足Johnson不等式。 50 n 由此可见当作业i和作业j不满足Johnson不等式时，交 换它们的加工顺序后，不增加加工时间。对于流水作业 调度问题，必存在最优调度 ，使得作业(i)和(i+1)满 足Johnson不等式。进一步还可以证明，调度满足 Johnson法则当且仅当对任意ibi?bi:ai; di.job = aij,无法装入 59 0-10-1背包问题实例分析背包问题实例分析 C=6 123 wi234 vi125 xi101 0123456 10000006 20002555 30000555 j i m23=max(m33,m30+2)=2; m24=max(m34,m31+2)=5; m25=max(m35,m32+2)=5; m26=max(m36,m33+2)=5; m16=max(m26,m24+1)=6; c n 60 n 由0-1背包问题的最优子结构性质，建立计算m(i，j)的 递归式如下: n 算法复杂度分析： q 从m(i，j)的递归式容易看出，算法需要O(nc)计 算时间。当背包容量c很大时，算法需要的计算时间 较多。例如，当c2n时，算法需要(n2n)计算时间 。 0-10-1背包问题背包问题 61 代码分析 #define NUM 100 void knapsack(int v , int w