动态规划 (2)优秀PPT.ppt

《动态规划 (2)优秀PPT.ppt》由会员分享，可在线阅读，更多相关《动态规划 (2)优秀PPT.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划(2)1第1页，本讲稿共48页动态规划动态规划学习要点学习要点:理解动态规划算法的概念。理解动态规划算法的概念。掌握动态规划算法的基本要素掌握动态规划算法的基本要素最优子结构性质最优子结构性质重叠子问题性质重叠子问题性质掌握设计动态规划算法的步骤。掌握设计动态规划算法的步骤。找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。递归地定义最优值。递归地定义最优值。以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。2第2页，本讲稿共48页n动态规划算法与分治法类似，其基本思想也是将

2、待动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题求解问题分解成若干个子问题算法总体思想算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=3第3页，本讲稿共48页n但是经分解得到的子问题往往不是互相独立的。不同子问题但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。题被重复计算了许多次。算法总体思想算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T

3、(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)4第4页，本讲稿共48页n如果能够保存已解决的子问题的答案，而在需要时再找出如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。式时间算法

4、。算法总体思想算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)5第5页，本讲稿共48页动态规划基本步骤动态规划基本步骤n找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。n递归地定义最优值。递归地定义最优值。n以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。n根据计算最优值时得到的信息，构造最优解。根

5、据计算最优值时得到的信息，构造最优解。6第6页，本讲稿共48页（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 16000,10500,36000,87500,34500n完全加括号的矩阵连乘积可递归地定义为：完全加括号的矩阵连乘积可递归地定义为：n设有四个矩阵设有四个矩阵 ，它们的维数分别是：，它们的维数分别是：n总共有五种完全加括号的方式总共有五种完全加括号的方式完全加括号的矩阵连乘积完全加括号的矩阵连乘积7第7页，本讲稿共48页矩阵连乘问题矩阵连乘问题n给定给定n n个矩阵个矩阵 ，其中其中 与与 是可乘的，

6、是可乘的，。考察这。考察这n n个矩阵的连乘积个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。的计算次序。这种计算次序可以用加括号的方式来确定。n若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用全加括号，则可以依此次序反复调用2 2个矩阵相乘的标准算法计个矩阵相乘的标准算法计算出矩阵连乘积算出矩阵连乘积8第8页，本讲稿共48页矩阵连乘问题矩阵连乘问题给定给定n n个矩阵

7、个矩阵A A1 1,A,A2 2,A,An n，其中，其中AiAi与与Ai+1Ai+1是可乘的，是可乘的，i=1i=1，2 2，n-1n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。的数乘次数最少。u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计算次列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。序。算法复杂度分析：算法复杂度分析：对于对于n n个矩阵的连乘积，设其不同的计

8、算次序为个矩阵的连乘积，设其不同的计算次序为P(n)P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1(A1.Ak)(Ak+1An)An)可以得到关于可以得到关于P(n)P(n)的递推式如下：的递推式如下：9第9页，本讲稿共48页矩阵连乘问题矩阵连乘问题u穷举法穷举法u动态规划动态规划将矩阵连乘积将矩阵连乘积 简记为简记为Ai:j Ai:j，这里，这里ijij 考察计算考察计算Ai:jAi:j的最优计算次序。设这个计算次序在矩阵的最优计算次序。设这个计算次序在矩阵A Ak k和和A Ak+1k+1之间将

9、矩阵链断开，之间将矩阵链断开，ikjikj，则其相应完全，则其相应完全加括号方式为加括号方式为计算量：计算量：Ai:kAi:k的计算量加上的计算量加上Ak+1:jAk+1:j的计算量，再加上的计算量，再加上Ai:kAi:k和和Ak+1:jAk+1:j相乘的计算量相乘的计算量10第10页，本讲稿共48页n特征：计算特征：计算Ai:jAi:j的最优次序所包含的计算矩阵子的最优次序所包含的计算矩阵子链链 Ai:k Ai:k和和Ak+1:jAk+1:j的次序也是最优的。的次序也是最优的。n矩阵连乘计算次序问题的最优解包含着其子问题的矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子

10、结构性质。问题的最最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显优子结构性质是该问题可用动态规划算法求解的显著特征。著特征。分析最优解的结构分析最优解的结构11第11页，本讲稿共48页建立递归关系建立递归关系n设计算设计算Ai:jAi:j，1ijn1ijn，所需要的最少数乘次数，所需要的最少数乘次数mi,jmi,j，则，则原问题的最优值为原问题的最优值为m1,n m1,n n当当i=ji=j时，时，Ai:j=AiAi:j=Ai，因此，因此，mi,i=0mi,i=0，i=1,2,i=1,2,n,nn当当ijij时，时，n可以递归地定义可以递归地定义mi,

11、jmi,j为：为：这里这里 的维数为的维数为 的位置只有的位置只有 种可能种可能12第12页，本讲稿共48页计算最优值计算最优值n对于对于1ijn1ijn不同的有序对不同的有序对(i,j)(i,j)对应于不同的子问题。因此，不对应于不同的子问题。因此，不同子问题的个数最多只有同子问题的个数最多只有n由此可见，在递归计算时，许多子问题被重复计算多次。这也是由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。该问题可用动态规划算法求解的又一显著特征。n用动态规划算法解此问题，可依据其递归式以自底向上的方式进用动态规划算法解此问题，可依据其递归式以自底向

12、上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法重复计算，最终得到多项式时间的算法13第13页，本讲稿共48页用动态规划法求最优解用动态规划法求最优解void MatrixChain(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

13、+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 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;17第17页，本讲稿共48页最长公共子序列

14、最长公共子序列若给定序列若给定序列X=xX=x1 1,x,x2 2,x,xm m，则另一序列，则另一序列Z=zZ=z1 1,z,z2 2,z,zk k，是，是X X的子序列是指存在一个严格递增下标序列的子序列是指存在一个严格递增下标序列ii1 1,i,i2 2,i,ik k 使得对于所有使得对于所有j=1,2,j=1,2,k,k有：有：z zj j=x=xi ij j。例如，序列例如，序列Z=BZ=B，C C，D D，BB是序列是序列X=AX=A，B B，C C，B B，D D，A A，BB的子的子序列，相应的递增下标序列为序列，相应的递增下标序列为22，3 3，5 5，77。给定给定2 2个

15、序列个序列X X和和Y Y，当另一序列，当另一序列Z Z既是既是X X的子序列又是的子序列又是Y Y的子的子序列时，称序列时，称Z Z是序列是序列X X和和Y Y的公共子序列。的公共子序列。给定给定2 2个序列个序列X=xX=x1 1,x,x2 2,x,xm m 和和Y=yY=y1 1,y,y2 2,y,yn n，找出，找出X X和和Y Y的最长公共子序列。的最长公共子序列。18第18页，本讲稿共48页最长公共子序列的结构最长公共子序列的结构设序列设序列X=xX=x1 1,x,x2 2,x,xm m 和和Y=yY=y1 1,y,y2 2,y,yn n 的最长公共子序列为的最长公共子序列为Z=z

16、Z=z1 1,z,z2 2,z,zk k ，则，则(1)(1)若若x xm m=y=yn n，则，则z zk k=x=xm m=y=yn n，且，且z zk-1k-1是是x xm-1m-1和和y yn-1n-1的最长公共子序列。的最长公共子序列。(2)(2)若若x xm myyn n且且z zk kxxm m，则，则Z Z是是x xm-1m-1和和Y Y的最长公共子序列。的最长公共子序列。(3)(3)若若x xm myyn n且且z zk kyyn n，则，则Z Z是是X X和和y yn-1n-1的最长公共子序列。的最长公共子序列。由此可见，由此可见，2 2个序列的最长公共子序列包含了这个序列

17、的最长公共子序列包含了这2 2个序列的前缀的最长公个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有共子序列。因此，最长公共子序列问题具有最优子结构性质。最优子结构性质。19第19页，本讲稿共48页子问题的递归结构子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用递归关系。用cijcij记录序列和的最长公共子序列的长度。其记录序列和的最长公共子序列的长度。其中，中，X Xi i=x=x1 1,x,x2 2,x,xi i；Yj=yYj=y1 1,y,y2 2,y,yj j。当。当i=0i=0或或j=0j

18、=0时，空序列时，空序列是是X Xi i和和Y Yj j的最长公共子序列。故此时的最长公共子序列。故此时Cij=0Cij=0。其它情况下，由最。其它情况下，由最优子结构性质可建立递归关系如下：优子结构性质可建立递归关系如下：20第20页，本讲稿共48页计算最优值计算最优值 由于在所考虑的子问题空间中，总共有由于在所考虑的子问题空间中，总共有(mn)(mn)个不同的子问题，个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。因此，用动态规划算法自底向上地计算最优值能提高算法的效率。void LCSLength(int m，int n，char*x，char*y，int*c，

19、int*b)int i，j;for(i=1;i=m;i+)ci0=0;for(i=1;i=n;i+)c0i=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;bij=2;else cij=cij-1;bij=3;构造最长公共子序列构造最长公共子序列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);coutxi;else if(bij=2)LCS(i-1，j，x，b);else LCS(i，j-1，x，b);21第21页，本讲稿共48页算法的改进算法的改进

20、在算法在算法lcsLengthlcsLength和和lcslcs中，可进一步将数组中，可进一步将数组b b省去。事实上，数组省去。事实上，数组元素元素cijcij的值仅由的值仅由ci-1j-1ci-1j-1，ci-1jci-1j和和cij-1cij-1这这3 3个个数组元素的值所确定。对于给定的数组元素数组元素的值所确定。对于给定的数组元素cijcij，可以不借助于，可以不借助于数组数组b b而仅借助于而仅借助于c c本身在时间内确定本身在时间内确定cijcij的值是由的值是由ci-1j-1ci-1j-1，ci-1jci-1j和和cij-1cij-1中哪一个值所确定的。中哪一个值所确定的。如果

21、只需要计算最长公共子序列的长度，则算法的空间需求可如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算大大减少。事实上，在计算cijcij时，只用到数组时，只用到数组c c的第的第i i行和第行和第i-1i-1行。因此，用行。因此，用2 2行的数组空间就可以计算出最长公共子序列的长度。行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至进一步的分析还可将空间需求减至O(min(m,n)O(min(m,n)。22第22页，本讲稿共48页凸多边形最优三角剖分凸多边形最优三角剖分用多边形顶点的逆时针序列表示凸多边形，即用多边形顶点的逆时针序列表示凸多

22、边形，即P=vP=v0 0,v,v1 1,v,vn-1n-1 表表示具有示具有n n条边的凸多边形。条边的凸多边形。若若v vi i与与v vj j是多边形上不相邻的是多边形上不相邻的2 2个顶点，则线段个顶点，则线段v vi iv vj j称为多边形称为多边形的一条弦。弦将多边形分割成的一条弦。弦将多边形分割成2 2个多边形个多边形vvi i,v,vi+1i+1,v,vj j 和和vvj j,v,vj+1j+1,v vi i。多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T T。给定凸多边形给定凸多边形P P，以及定义在由

23、多边形的边和弦组成的三角形上的，以及定义在由多边形的边和弦组成的三角形上的权函数权函数w w。要求确定该凸多边形的三角剖分，使得即该三角剖。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。分中诸三角形上权之和为最小。23第23页，本讲稿共48页三角剖分的结构及其相关问题三角剖分的结构及其相关问题一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积的语法树。例如，完全加括号的矩阵连乘积(A(A1 1(A(A2 2A A3 3)(A)(A4 4(A(A5 5A A6 6)所

24、所相应的语法树如图相应的语法树如图(a)(a)所示。所示。凸多边形凸多边形vv0 0,v,v1 1,v vn-1n-1 的三角剖分也可以用语法树表示。例如，图的三角剖分也可以用语法树表示。例如，图(b)(b)中凸多边形的三角剖分可用图中凸多边形的三角剖分可用图(a)(a)所示的语法树表示。所示的语法树表示。矩阵连乘积中的每个矩阵矩阵连乘积中的每个矩阵A Ai i对应于凸对应于凸(n+1)(n+1)边形中的一条边边形中的一条边v vi-1i-1v vi i。三角剖分。三角剖分中的一条弦中的一条弦v vi iv vj j，ijij，对应于矩阵连乘积，对应于矩阵连乘积Ai+1:jAi+1:j。24第

25、24页，本讲稿共48页最优子结构性质最优子结构性质凸多边形的最优三角剖分问题有最优子结构性质。凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸事实上，若凸(n+1)(n+1)边形边形P=vP=v0 0,v,v1 1,v,vn-1n-1 的最优三角剖分的最优三角剖分T T包含三角形包含三角形v v0 0v vk kv vn n，1kn-11kn-1，则，则T T的权为的权为3 3个部分权的个部分权的和：三角形和：三角形v v0 0v vk kv vn n的权，子多边形的权，子多边形vv0 0,v,v1 1,v,vk k 和和vvk k,v,vk+1k+1,v,vn n 的权之和。可以断言

26、，由的权之和。可以断言，由T T所确定的这所确定的这2 2个子个子多边形的三角剖分也是最优的。因为若有多边形的三角剖分也是最优的。因为若有vv0 0,v,v1 1,v,vk k 或或vvk k,v,vk+1k+1,v,vn n 的更小权的三角剖分将导致的更小权的三角剖分将导致T T不是最优三不是最优三角剖分的矛盾。角剖分的矛盾。25第25页，本讲稿共48页最优三角剖分的递归结构最优三角剖分的递归结构定义定义tijtij，1ijn1ijn为凸子多边形为凸子多边形vi-1,vi,vi-1,vi,vj,vj的最优三角剖分所对应的权函数值，的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化

27、的多边形即其最优值。为方便起见，设退化的多边形vi-1,vivi-1,vi具有权值具有权值0 0。据此定义，要计算的。据此定义，要计算的凸凸(n+1)(n+1)边形边形P P的最优权值为的最优权值为t1nt1n。tijtij的值可以利用最优子结构性质递归地计算。当的值可以利用最优子结构性质递归地计算。当j-i1j-i1时，凸子多边形至少有时，凸子多边形至少有3 3个顶点。由最优子结构性质，个顶点。由最优子结构性质，tijtij的值应为的值应为tiktik的值加上的值加上tk+1jtk+1j的值，的值，再加上三角形再加上三角形v vi-1i-1v vk kv vj j的权值，其中的权值，其中ik

28、j-1ikj-1。由于在计算时还不知道。由于在计算时还不知道k k的确切位置，的确切位置，而而k k的所有可能位置只有的所有可能位置只有j-ij-i个，因此可以在这个，因此可以在这j-ij-i个位置中选出使个位置中选出使tijtij值达到最小值达到最小的位置。由此，的位置。由此，tijtij可递归地定义为：可递归地定义为：26第26页，本讲稿共48页多边形游戏多边形游戏多边形游戏是一个单人玩的游戏，开始时有一个由多边形游戏是一个单人玩的游戏，开始时有一个由n n个顶点构成个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算

29、符“+”或或“*”。所有边依次用整数从。所有边依次用整数从1 1到到n n编号。编号。游戏第游戏第1 1步，将一条边删除。步，将一条边删除。随后随后n-1n-1步按以下方式操作：步按以下方式操作：(1)(1)选择一条边选择一条边E E以及由以及由E E连接着的连接着的2 2个顶点个顶点V1V1和和V2V2；(2)(2)用一个新的顶点取代边用一个新的顶点取代边E E以及由以及由E E连接着的连接着的2 2个顶点个顶点V1V1和和V2V2。将由。将由顶点顶点V1V1和和V2V2的整数值通过边的整数值通过边E E上的运算得到的结果赋予新顶点。上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结

30、束。游戏的得分就是所剩顶点上的整数最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。值。问题问题:对于给定的多边形，计算最高得分。对于给定的多边形，计算最高得分。27第27页，本讲稿共48页最优子结构性质最优子结构性质在所给多边形中，从顶点在所给多边形中，从顶点i(1in)i(1in)开始，长度为开始，长度为j(j(链中有链中有j j个顶点个顶点)的顺时针链的顺时针链p(i,j)p(i,j)可表示为可表示为vi,opi+1,vi,opi+1,vi+j-1,vi+j-1。如果这条链的最后一次合并运算在如果这条链的最后一次合并运算在opi+sopi+s处发生处发生(1sj-1)(1

31、sj-1)，则可在，则可在opi+sopi+s处将链分割为处将链分割为2 2个子链个子链p(i.s)p(i.s)和和p(i+s,j-s)p(i+s,j-s)。设设m1m1是对子链是对子链p(ip(i，s)s)的任意一种合并方式得到的值，而的任意一种合并方式得到的值，而a a和和b b分别是在所有可能分别是在所有可能的合并中得到的最小值和最大值。的合并中得到的最小值和最大值。m2m2是是p(i+sp(i+s，j-s)j-s)的任意一种合并方式得到的的任意一种合并方式得到的值，而值，而c c和和d d分别是在所有可能的合并中得到的最小值和最大值。依此定义有分别是在所有可能的合并中得到的最小值和最大

32、值。依此定义有am1bam1b，cm2dcm2d(1)(1)当当opi+s=+opi+s=+时，显然有时，显然有a+cmb+da+cmb+d(2)(2)当当opi+s=*opi+s=*时，有时，有minacminac，adad，bcbc，bdmmaxacbdmmaxac，adad，bcbc，bd bd 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。28第28页，本讲稿共48页图像压缩图像压缩 图象的变位压缩存储格式将所给的象素点序列图象的变位压缩存储格式将所给的象素点序列p1,p2,p1,p2,pn,0pi255,pn,

33、0pi255分割成分割成m m个连续段个连续段S1,S2,S1,S2,Sm,Sm。第。第i i个象个象素段素段SiSi中中(1im)(1im)，有，有l lii个象素个象素,且该段中每个象素都只用且该段中每个象素都只用bibi位位表示。设表示。设 则第则第i i个象素段个象素段SiSi为为 设设 ，则，则hihi bibi 8 8。因此需要用。因此需要用3 3位表示位表示bi,bi,如果限制如果限制1 1 lili 255255，则需要用，则需要用8 8位表示位表示lili。因此，第。因此，第i i个个象素段所需的存储空间为象素段所需的存储空间为li*bi+11li*bi+11位。按此格式存储

34、象素序位。按此格式存储象素序列列p1,p2,p1,p2,pn,pn，需要，需要 位的存储空间。位的存储空间。图象压缩问题要求确定象素序列图象压缩问题要求确定象素序列p1,p2,p1,p2,pn,pn的最优分段，使的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过得依此分段所需的存储空间最少。每个分段的长度不超过256256位。位。29第29页，本讲稿共48页图像压缩图像压缩 设设l lii，bibi，是，是p1,p2,p1,p2,pn,pn的最优分段。显而易见，的最优分段。显而易见，l l11，b1b1是是pp1 1,p,pl1l1 的最优分段，且的最优分段，且l lii，bib

35、i，是，是ppl1+1l1+1,p,pn n 的的最优分段。即图象压缩问题满足最优子结构性质。最优分段。即图象压缩问题满足最优子结构性质。设设sisi，1in1in，是象素序列，是象素序列p1,p1,pn,pn的最优分段所需的存储的最优分段所需的存储位数。由最优子结构性质易知：位数。由最优子结构性质易知：其中其中算法复杂度分析：算法复杂度分析：由于算法由于算法compresscompress中对中对k k的循环次数不超这的循环次数不超这256256，故对每一个确，故对每一个确定的定的i i，可在时间，可在时间O(1)O(1)内完成的计算。因此整个算法所需的内完成的计算。因此整个算法所需的计算时

36、间为计算时间为O(n)O(n)。30第30页，本讲稿共48页电路布线电路布线在一块电路板的上、下在一块电路板的上、下2 2端分别有端分别有n n个接线柱。根据电路设计，要求用个接线柱。根据电路设计，要求用导线导线(i,(i)(i,(i)将上端接线柱与下端接线柱相连，如图所示。其中将上端接线柱与下端接线柱相连，如图所示。其中(i)(i)是是1,2,1,2,n,n的一个排列。导线的一个排列。导线(i,(i)(i,(i)称为该电路板上的第称为该电路板上的第i i条连线。条连线。对于任何对于任何1ijn1i(j)(i)(j)。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可电路布线问题要确

37、定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集能多的连线。换句话说，该问题要求确定导线集Nets=(i,(i),1inNets=(i,(i),1in的最大不相交子集。的最大不相交子集。31第31页，本讲稿共48页记记 。N(i,j)N(i,j)的最大的最大不相交子集为不相交子集为MNS(i,j)MNS(i,j)。Size(i,j)=|MNS(i,j)|Size(i,j)=|MNS(i,j)|。(1)(1)当当i=1i=1时，时，(2)(2)当当i1i1时，时，2.1 j(i)2.1 j(i)。此时，。此时，。故在这种情况下，。故在这种情况下，N(i,j)

38、=N(i-1,j)N(i,j)=N(i-1,j)，从而，从而Size(i,j)=Size(i-1,j)Size(i,j)=Size(i-1,j)。2.2 j(i)2.2 j(i)，(i,(i)(i,(i)MMNS(i,j)NS(i,j)。则对任意则对任意(t,(t)(t,(t)MMNS(i,j)NS(i,j)有有titi且且(t)(i)(t)(i)。在这种情况下。在这种情况下MNS(i,j)-(i,(i)MNS(i,j)-(i,(i)是是N(i-1,(i)-1)N(i-1,(i)-1)的最大不的最大不相交子集。相交子集。2.3 2.3 若若 ，则对任意，则对任意(t,(t)(t,(t)MMNS

39、(i,j)NS(i,j)有有 ti t1时32第32页，本讲稿共48页流水作业调度流水作业调度 n n个作业个作业11，2 2，nn要在由要在由2 2台机器台机器M1M1和和M2M2组成的流水线上完成组成的流水线上完成加工。每个作业加工的顺序都是先在加工。每个作业加工的顺序都是先在M1M1上加工，然后在上加工，然后在M2M2上加工。上加工。M1M1和和M2M2加工作业加工作业i i所需的时间分别为所需的时间分别为a ai i和和b bi i。流水作业调度问题要求确定这流水作业调度问题要求确定这n n个作业的最优加工顺序，使得从第一个作业的最优加工顺序，使得从第一个作业在机器个作业在机器M1M1

40、上开始加工，到最后一个作业在机器上开始加工，到最后一个作业在机器M2M2上加工完成所需上加工完成所需的时间最少。的时间最少。分析：分析：直观上，一个最优调度应使机器直观上，一个最优调度应使机器M1M1没有空闲时间，且机器没有空闲时间，且机器M2M2的空闲时间最少。在的空闲时间最少。在一般情况下，机器一般情况下，机器M2M2上会有机器空闲和作业积压上会有机器空闲和作业积压2 2种情况。种情况。设全部作业的集合为设全部作业的集合为N=1N=1，2 2，nn。S S N N是是N N的作业子集。在一般情况下，的作业子集。在一般情况下，机器机器M1M1开始加工开始加工S S中作业时，机器中作业时，机器

41、M2M2还在加工其它作业，要等时间还在加工其它作业，要等时间t t后才可利用。后才可利用。将这种情况下完成将这种情况下完成S S中作业所需的最短时间记为中作业所需的最短时间记为T(S,t)T(S,t)。流水作业调度问题的最。流水作业调度问题的最优值为优值为T(N,0)T(N,0)。33第33页，本讲稿共48页流水作业调度流水作业调度 设设 是所给是所给n n个流水作业的一个最优调度，它所需的加工时间为个流水作业的一个最优调度，它所需的加工时间为 a a(1)(1)+T+T。其中。其中T T是在机器是在机器M2M2的等待时间为的等待时间为b b(1)(1)时，安排作业时，安排作业(2)(2)，(

42、n)(n)所需的时间。所需的时间。记记S=N-S=N-(1)(1)，则有，则有T T=T(S,b=T(S,b(1)(1)。证明：事实上，由证明：事实上，由T T的定义知的定义知T T T(S,bT(S,b(1)(1)。若。若T TT(S,bT(S,b(1)(1)，设，设 是作业集是作业集S S在机器在机器M2M2的等待时间为的等待时间为b b(1)(1)情况下的一个最优调度。则情况下的一个最优调度。则(1)(1)，(2)(2)，(n)(n)是是N N的一个调度，且该调度所需的时间为的一个调度，且该调度所需的时间为a a(1)(1)+T(S,b+T(S,b(1)(1)a)a(1)(1)+T+T。

43、这与。这与 是是N N的最优调度矛盾。故的最优调度矛盾。故T T T(S,bT(S,b(1)(1)。从而。从而T T=T(S,b=T(S,b(1)(1)。这就证明了流水作业调度问题具有。这就证明了流水作业调度问题具有最优子结构的性质。最优子结构的性质。由流水作业调度问题的最优子结构性质可知，由流水作业调度问题的最优子结构性质可知，34第34页，本讲稿共48页JohnsonJohnson不等式不等式对递归式的深入分析表明，算法可进一步得到简化。对递归式的深入分析表明，算法可进一步得到简化。设设 是作业集是作业集S S在机器在机器M2M2的等待时间为的等待时间为t t时的任一最优调度。若时的任一最

44、优调度。若(1)=i,(1)=i,(2)=j(2)=j。则由动态规划递归式可得。则由动态规划递归式可得:T(S,t)=aT(S,t)=ai i+T(S-i,b+T(S-i,bi i+maxt-a+maxt-ai i,0)=a,0)=ai i+a+aj j+T(S-i,j,t+T(S-i,j,tijij)其中，其中，如果作业如果作业i i和和j j满足满足minbminbi i,a,aj jminbminbj j,a,ai i，则称作业，则称作业i i和和j j满足满足JohnsonJohnson不等式。不等式。35第35页，本讲稿共48页流水作业调度的流水作业调度的JohnsonJohnson

45、法则法则交换作业交换作业i i和作业和作业j j的加工顺序，得到作业集的加工顺序，得到作业集S S的另一调度，它所需的加的另一调度，它所需的加工时间为工时间为T T(S,t)=a(S,t)=ai i+a+aj j+T(S-i,j,t+T(S-i,j,tjiji)其中，其中，当作业当作业i i和和j j满足满足JohnsonJohnson不等式时，有不等式时，有由此可见当作业由此可见当作业i i和作业和作业j j不满足不满足JohnsonJohnson不等式时，交换它们的加工顺序不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度后，不增加加工时间。对于流水作业调

46、度问题，必存在最优调度 ，使得作，使得作业业(i)(i)和和(i+1)(i+1)满足满足JohnsonJohnson不等式。进一步还可以证明，调度满足不等式。进一步还可以证明，调度满足JohnsonJohnson法则当且仅当对任意法则当且仅当对任意iji2c2n n时，算法需要时，算法需要(n2n2n n)计算时间。计算时间。39第39页，本讲稿共48页算法改进算法改进 由由m(i,j)m(i,j)的递归式容易证明，在一般情况下，对每一个确定的的递归式容易证明，在一般情况下，对每一个确定的i(1in)i(1in)，函数，函数m(i,j)m(i,j)是关于变量是关于变量j j的阶梯状单调不减函数

47、。跳跃的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数点是这一类函数的描述特征。在一般情况下，函数m(i,j)m(i,j)由其全部跳由其全部跳跃点唯一确定。如图所示。跃点唯一确定。如图所示。对每一个确定的对每一个确定的i(1in)i(1in)，用一个表，用一个表pipi存储函数存储函数m(im(i，j)j)的全的全部跳跃点。表部跳跃点。表pipi可依计算可依计算m(im(i，j)j)的递归式递归地由表的递归式递归地由表pi+1pi+1计算，计算，初始时初始时pn+1=(0pn+1=(0，0)0)。40第40页，本讲稿共48页一个例子一个例子n=3，c=6，w=4，3，2，

48、v=5，2，1。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)41第41页，本讲稿共48页函数函数m(i,j)m(i,j)是由函数是由函数m(i+1,j)m(i+1,j)与函数与函数m(i+1,j-wi)+vim(i

49、+1,j-wi)+vi作作maxmax运算得到的。因此，运算得到的。因此，函数函数m(i,j)m(i,j)的全部跳跃点包含于函数的全部跳跃点包含于函数m(i+1m(i+1，j)j)的跳跃点集的跳跃点集pi+1pi+1与函数与函数m(i+1m(i+1，j-wi)+vij-wi)+vi的跳跃点集的跳跃点集qi+1qi+1的并集中。易知，的并集中。易知，(s,t)(s,t)qi+1qi+1当且仅当当且仅当wiwi s s c c且且(s-wi,t-vi)(s-wi,t-vi)pi+1pi+1。因此，容易由。因此，容易由pi+1pi+1确定跳跃点集确定跳跃点集qi+1qi+1如下如下qi+1=pi+1

50、qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1pi+1 另一方面，设另一方面，设(a(a，b)b)和和(c(c，d)d)是是pi+1pi+1 qi+1qi+1中的中的2 2个跳跃点，则当个跳跃点，则当c c a a且且dbdb时，时，(c(c，d)d)受控于受控于(a(a，b)b)，从而，从而(c(c，d)d)不是不是pipi中的跳跃点。除受控跳跃点外，中的跳跃点。除受控跳跃点外，pi+1pi+1 qi+1qi+1中的其它跳跃点均为中的其它跳跃点均为pipi中的跳跃点。中的跳跃点