算法分析与设计 动态规划法精.ppt

《算法分析与设计 动态规划法精.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计 动态规划法精.ppt（138页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法分析与设计课件 动态规划法1第1页，本讲稿共138页通过应用范例学习动态规划算法设计策略。通过应用范例学习动态规划算法设计策略。（1 1）矩阵连乘问题；）矩阵连乘问题；（2 2）最长公共子序列；）最长公共子序列；（3 3）最大子段和）最大子段和（4 4）凸多边形最优三角剖分；）凸多边形最优三角剖分；（5 5）多边形游戏；）多边形游戏；（6 6）图像压缩；）图像压缩；（7 7）电路布线；）电路布线；（8 8）流水作业调度；）流水作业调度；（9 9）背包问题；）背包问题；（1010）最优二叉搜索树。）最优二叉搜索树。2第2页，本讲稿共138页nT(n)=n/2T(n/4)T(n/4)T(n/4

2、)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)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动态规划算法与分治法类似，其基本思想也是将待求解问题分解动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题成若干个子问题n但是经分解得到的子问题往往不是互相独立的。不同子问题的数目但是经分解得到的子问题往往不是

3、互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。了许多次。算法总体思想算法总体思想3第3页，本讲稿共138页n如果能够保存已解决的子问题的答案，而在需要时再找出已求如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算得的答案，就可以避免大量重复计算，从而得到多项式时间算法。法。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、/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)4第4页，本讲稿共138页动态规划基本步骤n找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。n递归地定义最优值。递归地定义最优值。n以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。n根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。5第5页，本讲稿共138页n假定假定A A为为10011001矩阵矩阵,B B为为11001100矩阵，矩阵，C C为为10011001矩阵矩阵,(,(A A*B

5、 B)*)*C C需乘法数为需乘法数为 1001100 1001100100100110010012000020000n而而 A A*(*(B B*C C)所需乘法数为所需乘法数为11001110011001110011200200n长度长度q q的矩阵乘法链有指数量级的矩阵乘法链有指数量级(2(2n n)的可能的相乘方式的可能的相乘方式(有有q q个叶个叶节点的二叉数的数目节点的二叉数的数目).).n要找一种相乘方式要找一种相乘方式,使得元素乘法数最少使得元素乘法数最少6第6页，本讲稿共138页16000,10500,36000,87500,34500完全加括号的矩阵连乘积可递归地定义为：完

6、全加括号的矩阵连乘积可递归地定义为：（1 1）单个矩阵是完全加括号的；）单个矩阵是完全加括号的；（2 2）矩阵连乘积）矩阵连乘积A A是完全加括号的，则是完全加括号的，则A A可表示为可表示为2 2个完全加括个完全加括号的矩阵连乘积号的矩阵连乘积A A和和B B的乘积并加括号，即的乘积并加括号，即A=(BC)A=(BC)设有四个矩阵设有四个矩阵A,B,C,DA,B,C,D，它们的维数分别是：，它们的维数分别是：矩阵连乘积u总共有五中完全加括号的方式总共有五中完全加括号的方式7第7页，本讲稿共138页n给定给定n n个矩阵个矩阵 ，其中其中 与与 是可乘的。考察是可乘的。考察这这n n个矩阵的连

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

8、i与与Ai+1Ai+1是可乘的，是可乘的，i=1i=1，2 2，n-n-1 1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。要的数乘次数最少。u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号

9、问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：9第9页，本讲稿共138页u动态规划动态规划 将矩阵连乘积将矩阵连乘积A Ai iA Ai i+1+1A Aj j ，简记为简记为Ai:j Ai:j，这里，这里ij ij 考察计算考察计算Ai:jAi:j的最优计算次序。设这个计算次序在矩阵的最优计算次序。设这个计算次序在矩阵AkAk和和Ak+1Ak+1之间将矩阵链断开，之间将矩阵链断开，ikjikj，则其相应完全，则其相应完全加括号方式为加括号方式为 计算量：计算量：Ai:kAi:k的计算量加上的计算量加上Ak+1:jAk+1:j的计算量，再加上的计算量，再加上Ai:kAi

10、:k和和Ak+1:jAk+1:j相乘的计算量相乘的计算量10第10页，本讲稿共138页n特征：计算特征：计算Ai:jAi:j的最优次序所包含的计算矩阵子链的最优次序所包含的计算矩阵子链 Ai:kAi:k和和Ak+1:jAk+1:j的次序也是最优的。的次序也是最优的。n矩阵连乘计算次序问题的最优解包含着其子问题的最优解。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。该问题可用动态规划算法求解的显著特征。分析最优解的结构分析最优解的结构11第11页，本讲稿

11、共138页建立递归关系建立递归关系n设计算设计算Ai:j，1ijn，所需要的最少数乘次数，所需要的最少数乘次数mi,j，则原问题的最优值为，则原问题的最优值为m1,n n当当i=j时，时，Ai:j=Ai，因此，因此，mi,i=0，i=1,2,nn当当ij时，时，这里 的维数为 的位置只有的位置只有 种种可能可能n 可以递归地定义可以递归地定义mi,j为：为：12第12页，本讲稿共138页计算最优值计算最优值n对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有n由此可见，在递归计算时，许多子问题被重复计算多次。这也是该由此可见，在递归计算时，许多子问题被重复计算

12、多次。这也是该问题可用动态规划算法求解的又一显著特征。问题可用动态规划算法求解的又一显著特征。n用动态规划算法解此问题，可依据其递归式以自底向上的用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法从而避免大量的重复计算，最终得到多项式时间的算法13第13页，本讲稿共138页用动态规划法求最优解用动态规划法求最优解voidMatrixChain

13、(int*p，intn，int*m，int*s)for(inti=1;i=n;i+)mii=0;for(intr=2;r=n;r+)for(inti=1;i=n-r+1;i+)intj=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(intk=i+1;kj;k+)intt=mik+mk+1j+pi-1*pk*pj;if(tmij)mij=t;sij=k;14第14页，本讲稿共138页A1A2A3A4A5A6303535151555101020202515第15页，本讲稿共138页算法复杂度分析：算法复杂度分析：算法算法matrixChainmatrixChain的主要

14、计算量取决于算法中对的主要计算量取决于算法中对r r，i i和和k k的的3 3重循环。循环体内的计算量为重循环。循环体内的计算量为O(1)O(1)，而，而3 3重循环的总次数为重循环的总次数为O O(n(n3 3)。因此算法的计算时间上界为。因此算法的计算时间上界为O(nO(n3 3)。算法所占用的空间。算法所占用的空间显然为显然为O(nO(n2 2)。16第16页，本讲稿共138页动态规划算法的基本要素动态规划算法的基本要素一、最优子结构一、最优子结构一、最优子结构一、最优子结构矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为矩阵连乘计算次序问题的最优解包含着其子问题的最优

15、解。这种性质称为最优子结构性质。最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态最优解逐步构造出整个问题的最优

16、解。最优子结构是问题能用动态规划算法求解的前提。规划算法求解的前提。同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）求解速度更快（空间占用小，问题的维度低）17第17页，本讲稿共138页二、重叠子问题二、重叠子问题二、重叠子问题二、重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一

17、次，而后将其解保存在动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。划算法只需要多项式时间，从而获得较高的解题效率。18第18页，本讲稿共138页intrecmat(inti，intj)if(i=j)return0;intu=recmat(i，i)+recmat(i+1，j)+pi-1*p

18、i*pj;sij=i;for(intk=i+1;kj;k+)intt=recmat(i，k)+recmat(k+1，j)+pi-1*pk*pj;if(t0)returnmij;if(i=j)return0;intu=LookupChain(i，i)+LookupChain(i+1，j)+pi-1*pi*pj;sij=i;for(intk=i+1;kj;k+)intt=LookupChain(i，k)+LookupChain(k+1，j)+pi-1*pk*pj;if(tu)u=t;sij=k;mij=u;returnu;20第20页，本讲稿共138页最长公共子序列最长公共子序列 若给定序列若给定

19、序列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个序列个序列X X和和Y Y，

20、当另一序列，当另一序列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的最的最长公共子序列。长公共子序列。21第21页，本讲稿共138页 设序列设序列X=xX=x1 1,x,x2 2,x,xm m 和和Y=yY=y1 1,y,y2 2,y,yn n 的最长公共子序列为的最长公共子序列为Z=Z=zz1 1,z,z2 2,z,zk k ，则，则(1)(1)若

21、若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个序列的最长公共子序列包含了这个序列的最长公共子序列包含了这2 2个序列的前缀的最个序列的前缀的最长

22、公共子序列。因此，最长公共子序列问题具有最优子结构性质。长公共子序列。因此，最长公共子序列问题具有最优子结构性质。22第22页，本讲稿共138页子问题的递归结构子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用的递归关系。用cij记录序列和的最长公共子序列的长度。其记录序列和的最长公共子序列的长度。其中，中，Xi=x1,x2,xi；Yj=y1,y2,yj。当。当i=0或或j=0时，空序列是时，空序列是Xi和和Yj的最长公共子序列。故此时的最长公共子序列。故此时Cij=0。其它情况下，由最优。其它情况下，由最优子

23、结构性质可建立递归关系如下：子结构性质可建立递归关系如下：23第23页，本讲稿共138页计算最优值由于在所考虑的子问题空间中，总共有由于在所考虑的子问题空间中，总共有(mn)个不同的子个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。的效率。voidLCSLength(intm，intn，char*x，char*y，int*c，int*b)inti，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

24、;bij=2;elsecij=cij-1;bij=3;24第24页，本讲稿共138页构造最长公共子序列构造最长公共子序列voidLCS(inti，intj，char*x，int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1,j-1,x,b);coutxi;elseif(bij=2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);j0123456yjBDCABAi0 xj1A2B3C4B5D6A7B000000000000000011111112211222211223312223312233412234425第25页，本讲稿共138页算法的改进算

25、法的改进 在算法在算法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-ci-1j-11j-1，ci-1jci-1j和和cij-1cij-1中哪一个值所确定的。中哪一个值所确

26、定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算大大减少。事实上，在计算cijcij时，只用到数组时，只用到数组c c的第的第i i行和第行和第i-1i-1行。因此，用行。因此，用2 2行的数组空间就可以计算出最长公共子序列的长度。行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至进一步的分析还可将空间需求减至O(min(m,n)O(min(m,n)。26第26页，本讲稿共138页最大字段和最大字段和给定由给定由n个整数（可能为负数）组成的序列个整数（可能为负数）组成的序列a1,

27、a2,an，求该序求该序列形如列形如的字段和的最大值。当所有整数均为负整数的字段和的最大值。当所有整数均为负整数时，定义其最大字段和为时，定义其最大字段和为0。所以，所求最优值为：。所以，所求最优值为：例如：当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最大字段和为27第27页，本讲稿共138页最大字段和的简单算法最大字段和的简单算法intmaxsum(intn,int*a,int&besti,int&bestj)intsum=0;for(inti=1;i=n;i+)for(intj=i;j=n;j+)intthissum=0;for(intk=i;ksu

28、m)sum=thissum;besti=i;bestj=j;returnsum;O(nO(n3 3)28第28页，本讲稿共138页最大字段和的简单算法改进最大字段和的简单算法改进intmaxsum(intn,int*a,int&besti,int&bestj)intsum=0;for(inti=1;i=n;i+)intthissum=0;for(intj=i;jsum)sum=thissum;besti=i;bestj=j;returnsum;O(nO(n2 2)29第29页，本讲稿共138页最大字段和的分治算法最大字段和的分治算法如果将所给的序列如果将所给的序列a1:n分为长度相等的两段分为

29、长度相等的两段a1:n/2和和an/2+1:n，分别求出这两段的最大字段和，则分别求出这两段的最大字段和，则a1:n的最大字段和的最大字段和有三种情形：有三种情形：1、a1:n的最大字段和与的最大字段和与a1:n/2的最大字段和相同；的最大字段和相同；2、a1:n的最大字段和与的最大字段和与an/2+1:n的最大字段和相同；的最大字段和相同；3、a1:n的最大字段和为的最大字段和为1=i=n/2,n/2+1=j0?aleft:0;elseintcenter=(left+right)/2;intleftsum=maxsunsum(a,left,center);intrightsum=maxsun

30、sum(a,center+1,right);31第31页，本讲稿共138页ints1=0;intlefts=0;for(inti=center;i=left;i-)left+=ai;if(lefts1)s1=left;ints2=0;intrights=0;for(inti=center+1;is2)s2=rights;sum=s1+s2;if(sumleftsum)sum=leftsum;if(sum0时，bj=bj-1+aj，否则bj=aj。由此可得动态规划递归式：bj=maxbj-1+aj,aj，1=j=n34第34页，本讲稿共138页最大字段和的动态规划算法最大字段和的动态规划算法in

31、tmaxsum(intn,int*a)intsum=0,b=0;for(inti=1;i0)b+=ai;elseb=ai;if(bsum)sum=b;returnsum;O(n)35第35页，本讲稿共138页求任意一对顶点的最短路径求任意一对顶点的最短路径-弗罗伊德弗罗伊德(Floyd)Floyd)算法算法设图设图g用邻接矩阵法表示，求图用邻接矩阵法表示，求图g中任意一对顶点中任意一对顶点vi、vj间的最短间的最短路径。路径。1.将将vi到到vj的最短的路径长度初始化为的最短的路径长度初始化为g.arcsij，然后进行如下然后进行如下n次次比较和修正：比较和修正：2.在在vi、vj间加入顶点间

32、加入顶点v0，比较（，比较（vi,v0,vj）和）和(vi,vj)的路径长度，的路径长度，取其中较短的路径作为取其中较短的路径作为vi到到vj的且中间顶点号不大于的且中间顶点号不大于0的最短路径。的最短路径。36第36页，本讲稿共138页n3.在在vi、vj间加入顶点间加入顶点v1，得，得（vi,，v1）和和(v1,，vj)，其中其中（vi,v1）是是vi到到v1的且中间顶点号不大于的且中间顶点号不大于0的最短路径的最短路径，(v1,vj)是是v1到到vj的且中间顶点号不大于的且中间顶点号不大于0的最短路径的最短路径，这两条路径在上一步中已求出。这两条路径在上一步中已求出。将（将（vi,v1,

33、vj）与上一步已求出）与上一步已求出的且的且vi到到vj中间顶点号不大于中间顶点号不大于0的最短路径比较，取其中较短的路径作为的最短路径比较，取其中较短的路径作为vi到到vj的且中间顶点号不大于的且中间顶点号不大于1的最短路径。的最短路径。n37第37页，本讲稿共138页4.在在vi、vj间加入顶点间加入顶点v2，得，得（vi,v2）和和(v2,vj)，其中其中（vi,v2）是是vi到到v2的且中间顶点号不大于的且中间顶点号不大于1的最短路径的最短路径(v2,vj)是是v2到到vj的且中间顶点号不大于的且中间顶点号不大于1的最短路径的最短路径，这这两两条条路路径径在在上上一一步步中中已已求求出

34、出。将将（vi,v2,vj）与与上上一一步步已已求求出出的的且且vi到到vj中中间间顶顶点点号号不不大大于于1的的最最短短路路径径比比较较，取取其其中中较较短短的的路路径径作作为为vi到到vj的且中间顶点号不大于的且中间顶点号不大于2的最短路径。的最短路径。依次类推，经过依次类推，经过n次比较和修正，在第（次比较和修正，在第（n-1）步，将求得）步，将求得vi到到vj的的且中间顶点号不大于且中间顶点号不大于n-1的最短路径，这必是从的最短路径，这必是从vi到到vj的最短路径。的最短路径。按此方法可求得各对顶点间的最短路径。按此方法可求得各对顶点间的最短路径。38第38页，本讲稿共138页现定义

35、一个现定义一个n阶方阵序列。阶方阵序列。A(-1)，A(0)，A(1)，A(k)，A(n-1)其中其中A(-1)ij=G.arcsijA(k)ij=MinA(k-1)ij,A(k-1)ik+A(k-1)kj0kn-1从从上上述述计计算算公公式式可可见见，A(1)ij是是从从vi到到vj的的中中间间顶顶点点的的序序号号不不大大于于1的的最最短短路路径径的的长长度度；A(k)ij是是从从vi到到vj的的中中间间顶顶点点的的个个数数不不大大于于k的最短路径的长度；的最短路径的长度；A(n-1)ij就是从就是从vi到到vj的最短路径的长度。的最短路径的长度。由此得到求任意两顶点间的最短路径的算法。由此

36、得到求任意两顶点间的最短路径的算法。39第39页，本讲稿共138页voidFloyd(MgraphG,PathMatrix*P,DistancMatrix*A)/*用Floyd算法求有向网G中各对顶点v和w之间的最短路径Pvw及其带权长度Dvw。/*若Pvwu为1，则u是从v到w当前求得的最短路径上的顶点。*/for(v=0;vG.vexnum;+v)/*各对顶点之间初始已知路径及距离*/for(w=0;wG.vexnum;+w)Avw=G.arcsvw;for(u=0;uG.vexnum;+u)Pvwu=0;if(AvwINFINITY)/*从v到w有直接路径*/Pvwv=1;40第40页，

37、本讲稿共138页for(u=0;uG.vexnum;+u)for(v=0;vG.vexnum;+v)for(w=0;wG.vexnum;+w)if(Avu+AuwAvw)/*从v经u到w的一条路径更短*/Avw=Avu+Auw;for(i=0;iG.vexnum;+i)Pvwi=Pvui|Puwi;/*Floyd*/图7.20给出了一个简单的有向网及其邻接矩阵。图7.21给出了用Floyd算法求该有向网中每对顶点之间的最短路径过程中，数组D和数组P的变化情况。41第41页，本讲稿共138页42第42页，本讲稿共138页43第43页，本讲稿共138页凸多边形最优三角剖分凸多边形最优三角剖分 用多

38、边形顶点的逆时针序列表示凸多边形，即用多边形顶点的逆时针序列表示凸多边形，即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。多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合多边形的三角剖分是将多边形分割成互不相交的

39、三角形的弦的集合T T。给定凸多边形给定凸多边形P P，以及定义在由多边形的边和弦组成的三角形上的权，以及定义在由多边形的边和弦组成的三角形上的权函数函数w w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。三角形上权之和为最小。44第44页，本讲稿共138页三角剖分的结构及其相关问题三角剖分的结构及其相关问题一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积树。例如，完全加括号的矩阵连乘积(A1(A2A3)

40、(A4(A5A6)所相应的语法树如图所相应的语法树如图(a)所示。所示。矩阵连乘积中的每个矩阵矩阵连乘积中的每个矩阵Ai对应于凸对应于凸(n+1)边形中的一条边边形中的一条边vi-1vi。三角剖分中的。三角剖分中的一条弦一条弦vivj，ij，对应于矩阵连乘积，对应于矩阵连乘积Ai+1:j。一般情况下，一个凸边形的三角剖分对应于一棵有一般情况下，一个凸边形的三角剖分对应于一棵有n-1个叶结点的语法树。个叶结点的语法树。凸多边形凸多边形v0,v1,vn-1的三的三角剖分也可以用语法树表示。例角剖分也可以用语法树表示。例如，图如，图(b)中凸多边形的三角剖中凸多边形的三角剖分可用图分可用图(a)所示

41、的语法树表示。所示的语法树表示。45第45页，本讲稿共138页最优子结构性质最优子结构性质凸多边形的最优三角剖分问题有最优子结构性质。凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸事实上，若凸(n+1)边形边形P=v0,v1,vn-1的最优三角剖分的最优三角剖分T包含包含三角形三角形v0vkvn，1kn-1，则，则T的权为的权为3个部分权的和：三角形个部分权的和：三角形v0vkvn的权，子多边形的权，子多边形v0,v1,vk和和vk,vk+1,vn的权之和。可的权之和。可以断言，由以断言，由T所确定的这所确定的这2个子多边形的三角剖分也是最优的。因为个子多边形的三角剖分也是最优的。因

42、为若有若有v0,v1,vk或或vk,vk+1,vn的更小权的三角剖分将导致的更小权的三角剖分将导致T不是不是最优三角剖分的矛盾。最优三角剖分的矛盾。46第46页，本讲稿共138页最优三角剖分的递归结构最优三角剖分的递归结构定义定义tij，1ijn为凸子多边形为凸子多边形vi-1,vi,vj的最优三角剖分所对应的权函的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形数值，即其最优值。为方便起见，设退化的多边形vi-1,vi具有权值具有权值0。据此定义，要。据此定义，要计算的凸计算的凸(n+1)边形边形P的最优权值为的最优权值为t1n。tij的值可以利用最优子结构性质递归地计算

43、。当的值可以利用最优子结构性质递归地计算。当j-i1时，凸子多边形至少有时，凸子多边形至少有3个顶点。由最优子结构性质，个顶点。由最优子结构性质，tij的值应为的值应为tik的值加上的值加上tk+1j的值，再加上的值，再加上三角形三角形vi-1vkvj的权值，其中的权值，其中ikj-1。由于在计算时还不知道。由于在计算时还不知道k的确切位置，而的确切位置，而k的所有可能位置只有的所有可能位置只有j-i个，因此可以在这个，因此可以在这j-i个位置中选出使个位置中选出使tij值达到最小的值达到最小的位置。由此，位置。由此，tij可递归地定义为：可递归地定义为：47第47页，本讲稿共138页计算最优

44、值templatevoidminweighttriangulation(intn,type*t,int*s)for(inti=1;i=n;i+)tii=0;for(intr=2;r=n;r+)for(inti=1;i=n-r+1;i+)intj=I+r-1;tij=ti+1j+w(i-1,i,j);sij=I;for(intk=i+1;k=i+r+1;k+)intu=tik+tk+1j+w(i-1,k,j);if(utij)tij=u;sij=k;占用空间：占用空间：耗时：耗时：48第48页，本讲稿共138页多边形游戏多边形游戏多边形游戏是一个单人玩的游戏，开始时有一个由多边形游戏是一个单人玩

45、的游戏，开始时有一个由n n个顶点构成的多边形。每个顶个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符点被赋予一个整数值，每条边被赋予一个运算符“+”或或“*”。所有边依次用整。所有边依次用整数从数从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

46、。将由顶点。将由顶点V1V1和和V2V2的的整数值通过边整数值通过边E E上的运算得到的结果赋予新顶点。上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。问题问题:对于给定的多边形，计算最高得分。对于给定的多边形，计算最高得分。49第49页，本讲稿共138页最优子结构性质最优子结构性质 设所给的多边形的顶点和边的顺时针序列为：设所给的多边形的顶点和边的顺时针序列为：op1,v1,op2,v2,op1,v1,op2,v2,opn,vn,opn,vn其中，其中，opiopi表示第表示第I

47、 I条边所对应的运算符，条边所对应的运算符，vivi表示第表示第i i个顶点上的数值。个顶点上的数值。在所给多边形中，从顶点在所给多边形中，从顶点i(1in)i(1in)开始，长度为开始，长度为j(j(链中有链中有j j个顶点个顶点)的顺时针链的顺时针链p p(i(i，j)j)可表示为可表示为vivi，opi+1opi+1，vi+j-1vi+j-1。如果这条链的最后一次合并运算在如果这条链的最后一次合并运算在opi+sopi+s处发生处发生(1sj-1)(1sj-1)，则可在，则可在opi+sopi+s处将链分割为处将链分割为2 2个子链个子链p(ip(i，s)s)和和p(i+sp(i+s，j

48、-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分别是在所有可能的合并中得到的最小值和最大值。依此定义有分别是在所有可能的合并中得到的最小值和最大值。依此定义有am1bam1b，cm2dcm2d50第50页，本讲稿共138页 由于子链由于子链p(i,s)p(i,s)和和p(i+s,j-s

49、)p(i+s,j-s)的合并方式决定了的合并方式决定了p(i,j)p(i,j)在在opi+sopi+s处断开后的合并方式，在处断开后的合并方式，在opi+sopi+s处合并后其值为：处合并后其值为：m=(m1)opi+s(m2)m=(m1)opi+s(m2)(1)(1)当当opi+s=+opi+s=+时，显然有时，显然有a+cmb+da+cmb+d (2)(2)当当opi+s=opi+s=*时，由于时，由于vivi可能取负值，子链的最大值相乘可能取负值，子链的最大值相乘未必得到主链的最大值。但有未必得到主链的最大值。但有 minac minac，adad，bcbc，bdmmaxacbdmmax

50、ac，adad，bcbc，bd bd 换句话说，主链的最大值和最小值可由子链的最大值和最小值得换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。例如：当到。例如：当m=acm=ac时，最大主链由它的两条最小子链组成；同理当时，最大主链由它的两条最小子链组成；同理当m=bdm=bd时，最大主链由它的两条最大子链组成。时，最大主链由它的两条最大子链组成。51第51页，本讲稿共138页递归求解为了求链合并的最大值，必须同时求子链合并的最大值和最小值。因此，在整个计算过为了求链合并的最大值，必须同时求子链合并的最大值和最小值。因此，在整个计算过程中，应同时计算最大值和最小值。程中，应同时计算