《第3章 动态规划》由会员分享，可在线阅读，更多相关《第3章 动态规划（80页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析第三章 动态规划,安吉尧,2,学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。,3,通过应用范例学习动态规划算法设计策略：（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏； （6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。,4,引言,动态规划算法与分治法类似，
2、其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,Those who cannot remember the past are doomed to repeat it.George Santayana, The life of Reason, Book I: Introduction and Reason in Common Sense (1905),5,动态规
3、划基本步骤,找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。,6,3.1 矩阵连乘问题,给定n个矩阵A1,A2,.,An，其中Ai与Ai+1是可乘的，i=1,2,.,n-1。考察这n个矩阵的连乘积A1A2.An。由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；矩阵连乘积A是完
4、全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。设有四个矩阵A,B,C,D，它们的维数分别是：A=5010，B=1040，C=4030，D=305总共有五种完全加括号的方式：(A(BC)D) (A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D)其数乘次数分别为：16000, 10500, 36000, 87500, 34500,7,穷举搜索法,问题描述：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算
5、次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下： 也就是说，P(n)是随n的增长成指数增长的。,8,动态规划法1.分析最优解的结构,下面我们考虑用动态规划求解。预处理：将矩阵连乘积AiAi+1.Aj简记为Ai:j，这里ij。考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为（AiAi+1. Ak）（Ak+1
6、Ak+2. Aj ）。计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量。分析最优解的结构特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,9,2.建立递归关系,设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n。当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n。当ij时，mi,j=mi,k+mk+1,j+pi-1pkpj，这里A
7、i的维数为pi-1pi。可以递归地定义mi,j为： k的位置只有j-i种可能。,10,3.计算最优值,对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。,11,算法描述,算法描述：void MatrixChain(int *p，int n，int *m，int *
8、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;,12,示例,13,具体步骤1,14,具体步骤2,15,具体步骤3,16,4.构造最优解,算法描述?复杂性分析：算法MatrixChain的主要
9、计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。算法TraceBack的复杂性？,17,具体步骤4,18,3.2 动态规划算法的基本要素,从计算矩阵连乘积最优计算次序的动态规划算法可以看出，该算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。从一般意义上讲，问题的这两个重要性质是该问题可以用动态规划算法求解的基本要素。本节着重介绍：最优子结构重叠子问题备忘录方法此外，本节最后对动态规划算法与备忘录方法的适用条件作了简单介绍。,19,一、最优子
10、结构,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,20,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多
11、次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,21,三、备忘录方法,备忘录方法的控制结构与直接递归方法(Page.54)的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。int MemoizedMatrixChain(int n, int *m, int *s) for (int i=1;i=n;i+) for (in
12、t j=i;j 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 j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj;if (t u) u = t; sij = k;mij = u;return u;算法复杂性：T(n)=O(n3),22,关于动态规划算法和备忘录方法的适用条件,综上所述，矩阵连乘积的最优计算次序问题可用自顶向
13、下的备忘录方法或自底向上的动态规划算法在O(n3)计算时间内求解。这两个算法都利用了子问题重叠性质。总共有(n2)个不同的子问题，对每个子问题两种算法都只解一次并记录答案。当再次遇到该子问题时，简单地取用已得到的答案，节省了计算量，提高了算法的效率。适用条件：一般来说，当一个问题的所有子问题都至少要解一次时，用动态规划算法比用备忘录方法好。此时，动态规划算法没有任何多余的计算，还可以利用其规则的表格存取方式来减少在动态规划算法中的计算时间和空间需求。当子问题空间中部分子问题可以不必求解时，易用备忘录方法则较为有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题。,23,课堂练习,
14、A1=6020，A2=2050，A3=5025，A4=2515，请确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。,24,3.3 最长公共子序列,概述：若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。问题：给定2个序列X=x1,x2,xm和Y=y1,y
15、2,yn，找出X和Y的最长公共子序列。,25,课堂练习,请找出下列两个序列的最长公共子序列X=A，B，C，B，D，A，BY=B，D，C，A，B，A注：请把你的思路详细描述之。,26,1,最长公共子序列的结构,设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。若xmyn且zkxm，则Z是Xm-1和Y的最长公共子序列。若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,
