算法课件第3章动态规划

《算法课件第3章动态规划》由会员分享，可在线阅读，更多相关《算法课件第3章动态规划（82页珍藏版）》请在金锄头文库上搜索。

1、1,第3章 动态规划,马志强,2,理解动态规划算法的思想 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 （ 1 ）找出最优解的性质，并刻划其结构特征。 （ 2 ）递归地定义最优值。 （ 3 ）以自底向上的方式计算出最优值。 （ 4 ）根据计算最优值时得到的信息，构造最优解。,学习要点,3,通过应用范例学习动态规划算法设计策略。 （1）矩阵连乘问题； （2）最长公共子序列； （3）凸多边形最优三角剖分； （4）0/1背包问题； （5）最优二叉搜索树。,学习要点,4,在50年代, Richard Bellman等人提出了解决多阶段决策问题的“

2、最优性原理”，并创建了最优化问题的一种新的求解方法-动态规划（Dynamic programming）。 1957年， 出版“动态规划”。 优点： 对许多问题，比线性规划或非线性规划更有效。 弱点： （1）得出函数方程后，尚无统一处理方法； （2）维数屏蔽:变量个数（维数）太大时无法解决。,背景,5,背景,典型优化问题：多段图问题 设G=(V,E)是一个赋权有向图，其顶点集V被换分为k2个不想交的子集Vi:1ik，其中，V1和Vk分别只有一个顶点s（源）和一个顶点t（汇），下图中所有(u,v)的始点和终点都在相邻的两个子集Vi和Vi+1中，而且uVi，vVi+1。求由s到t的最短路径。,6,背

3、景,解决优化问题 给定一组约束条件和一个代价函数，在解空间中搜索具有最小或最大代价的优化解 Why动态规划？ 对于一些优化问题，可以将其（递归）分解为若干子问题，但是经分解得到的子问题不是互相独立的。若用分治法来解决这些问题，分解得到的子问题数目太多，有些子问题被重复计算了多次 如果我们能用一个表来记录所有以解决的子问题的答案，在需要时找出已求得的答案，就可以避免大量重复计算,7,矩阵连乘问题,问题定义 输入：n个矩阵A1,A2,An，其中Ai的维数为pi-1pi Ai 和Ai+1是可乘的 输出：连乘积A1A2An 优化目标：最小的计算代价（最优的计算次序） 矩阵乘法的代价：乘法次数 例如，若

4、A 是p q 矩阵，B 是q r 矩阵，则A B 的代价是pqr。 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。,8,矩阵连乘问题,例子1 三个矩阵A1: 10100, A2: 1005，A3: 550 (A1A2)A3 代价：101005105507500 A1(A2A3) 代价：100550101005075000,9,矩阵连乘问题,例子2 设有四个矩阵A,B,C,D，它们的维数分别是： A=5010 B=1040 C=4030 D=305 总共有几种完全加括号的方式？ (A(BC)D) (A(B(CD) (AB)(CD) (A

5、B)C)D) (A(BC)D),10,矩阵连乘问题,例子2 设有四个矩阵A,B,C,D，它们的维数分别是： A=5010 B=1040 C=4030 D=305 总共有五种完全加括号的方式 (A(BC)D) 16000 (A(B(CD) 10500 (AB)(CD) 36000 (AB)C)D) 87500 (A(BC)D) 34500,11,穷举法列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序数为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)

6、(Ak+1An)可以得到关于P(n)的递推式：,矩阵连乘问题,12,矩阵连乘问题,分析最优解结构 将矩阵连乘积AiAi+1Aj，简记为Ai:j 设AiAi+1Aj的最优计算次序在矩阵Ak和Ak+1之间将矩阵链断开: (Ai Ak) (Ak+1 Aj) 总计算量Ai:k的计算量Ak+1: j的计算量+Ai:k和Ak+1:j相乘的计算量,13,特征： 计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。 反证法证明 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。 这种性质称为最优子结构性质 问题的最优子结构性质是该问题可用动态规划算法求解的显著特征,矩阵连乘问

7、题,14,矩阵连乘问题,建立递归关系 计算Ai : j所需的最少乘法次数为m(i, j) 其中Ai是pi-1pi矩阵,15,矩阵连乘问题,时间复杂性 可以证明,int matrixmultiply(i, j) if(i=j) return 0; int u=infinity; for(k=i; kj; k+) int t=matrixmultiply (i, k) + matrixmultiply (k+1, j) + pi-1pkpj; if(tu) u=t; return u; ,16,矩阵连乘问题,计算m(1,4),重叠子问题,17,矩阵连乘问题,对于1ijn不同的有序对(i,j)对应于

8、不同的子问题。因此，不同子问题的个数最多只有,由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。,18,矩阵连乘问题,动态规划方法计算最优值 自底向上计算（从最简单的算起） 用一个二维表保存已解决问题的答案 每个子问题只计算一次，后面需要的时候直接查找结果,19,计算最优值,m1,5,m1,4,m1,3,m1,2,m2,5,m3,5,m4,5,m2,4,m2,3,m3,4,20,计算最优值,当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n 当ij时，mi,j=mi,k+mk+1,j+p0pkpn,21,用动态规划法求最优解,Matr

9、ixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; ,算法复杂度分析： 算法的主要计算量取决于算法中对r，i和k的

10、3重循环。 循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。 因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。,22,用动态规划法求最优解,Print-Optimal-Parens(i, j,s) IF j=i THEN Print “A”i; ELSE Print “(” Print-Optimal-Parens(i, si, j,s) Print-Optimal-Parens(si, j+1, j,s) Print “)” ,23,用动态规划法求最优解,Print-Optimal-Parens(i, j,s) IF j=i THEN Print “A”i;

11、 ELSE Print “(” Print-Optimal-Parens(i, si, j,s) Print-Optimal-Parens(si, j+1, j,s) Print “)” ,(A1(A2A3)(A4A5)A6),24,动态规划算法的基本要素,适用条件 1.优化子结构(用动态规划算法求解的前提) 当一个问题的优化解包含了子问题的优化解时，我们说这个问题具有优化子结构。 缩小子问题集合，只需那些优化问题中包含的子问题，减低实现复杂性 优化子结构使得我们能自下而上地完成求解过程 证明：首先假设由问题的最优解导出的子问题不是最优的，然后再设法说明这个假设下可构造出比原问题最优解更好的解

12、，从而导致矛盾。,25,动态规划算法的基本要素,适用条件 2.重叠子问题 在问题的求解过程中，很多子问题的解将被多次使用 对每个子问题只解一次，而后将其保存在一个表格中，当再次需要解此问题时，只是简单地用常数时间查一下结果,26,动态规划算法的设计步骤 找出最优解的性质，并刻划其结构特征 递归地定义最优值 以自底向上的方式计算出最优值 根据计算最优值时得到的信息，构造最优解,动态规划算法的基本要素,27,最长公共子序列问题,例 X=A，B，C，B，D，A，B Z=B，C，D，B是的子序列，相应的下标 2,3,5,7。 W=C, A, B, D不是子序列，相应的下标3,6,7,5,定义（子序列）

13、 若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk 是X的子序列是指存在一个严格递增下标序列i1,i2,ik, 使得对于所有j=1,2,k有：zj=xij。,28,最长公共子序列问题,公共子序列 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 例 X=A，B，C，B，D，A，B Y=B，C，D，B，E Z=B, C, D, B是公共子序列,问题（最长公共子序列） 输入：X=x1,x2,xm，Y=y1,y2,yn 输出：Z=X和Y最长公共子序列,29,最长公共子序列问题,优化子结构 设序列X=和Y=的最长公共子序列是Z= 如果 xm=

14、yn zk=xm=yn 是和的最长公共子序列 如果 xmyn 且 zk xm 是和的最长公共子序列 如果 xmyn 且 zk yn 是和的最长公共子序列,30,最长公共子序列问题,找和的最长公共子序列 如果xm=yn 找和的最长公共子序列，在其尾部加上xm 如果xmyn 找和的最长公共子序列 找和的最长公共子序列 取这两个公共序列的较长者,31,子问题的递归结构,Xi=x1,x2,xi；Yj=y1,y2,yj。 用cij记录序列Xi和Yj的最长公共子序列的长度。 当i=0或j=0时，空序列是Xi和Yj的最长公共子序列, Cij=0。,递归表达式,32,最长公共子序列的结构,重叠子问题,c(4,

15、4),c(3,4),c(4,3),c(2,4),c(3,3),c(3,3),c(4,2),总共有(mn)个不同的子问题,33,计算最优值,c3,1,c2,1,c1,1,34,计算最优值,35,计算最优值,算法复杂度分析： 算法的计算时间上界为 O(mn)。 算法所占用的空间显然为 O(n2)。,36,构造最优解,例 X=B，D，C，A，B，A Y=A，B，C，B，D，A，B LCS= B, C, B, A,37,凸多边形最优三角剖分,多边形 n个顶点的多边形P可表示为其顶点序列P=v0, v1, vn-1 内部、边界、外部 凸多边形 边界上或内部任意两点连成的线段都在其内部或边界上,v0,v1,v2,v3,v4,v5,v6,凸多边形最优三角剖分,弦 连接多边形上不相邻顶点vi和vj的线段 三角剖分 将多边形划分为不相交的三角形的弦的集合,v0,v1,v2,v3,v4,v5,v6,凸多边形最优三角剖分,凸多边形的最优三角剖分问题 输入：凸多边形P=v0, v1, vn-1和代价函数w w指定了每个三角形的代价 如