动态规划法优秀课件.ppt

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

1、动态规划法第1页，本讲稿共53页算法设计与分析2问题的分解n将待求解问题分解为若干子问题，通过子问题的解得到原问题的解，这是问题求解的有效途径。但是如何实施分解？n分治策略的基本思想是将规模为n的问题分解为k个规模较小的子问题，各子问题相互独立但与原问题求解策略相同。并不是所有问题都可以这样处理。n问题分解的另一个途径是将求解过程分解为若干阶段（级），依次求解每个阶段即得到原问题的解。通过分解得到的各子阶段不要求相互独立，但希望它们具有相同类型，而且前一阶段的输出可以作为下一阶段的输入。这种策略特别适合求解具有某种最优性质的问题。n贪心法属于这类求解策略：对问题P(n)，其求解过程中各贪心选择

2、步骤构成决策序列D=。Di的最优性仅依赖于D1,D2,.Di-1。贪心法不保证决策序列D最后求出解的最优性。第2页，本讲稿共53页算法设计与分析3动态规划n动态规划也是一个分阶段判定决策过程，其问题求解策略的基础是决策过程的最优原理：为达到某问题的最优目标T，需要依次作出决策序列D=。如果D是最优的，则对任意i(1ik)，决策子序列Di+1,Dk也是最优的，即当前决策的最优性取决于其后续决策序列的是否最优。由此追溯至目标，再由最终目标决策向上回溯，导出决策序列 D=，因此动态规划方法可以保证问题求解是全局最优的。n也可以这样理解：如果求最优解的问题可以划分成若干段（级），那么最后求得的最优解是

3、由各个部分解所组成，而这些部分解一定是对应阶段的最优解。第3页，本讲稿共53页算法设计与分析4最短路径n给定简单有向连通赋权图G=，w(i,j)是G中边的权。顶点集V可以划分为k+1个两两不交的子集Vi，i=0,1,2,.k。其中V0=s，Vk=t。对G中任一边，存在Vi、Vi+1，使得u属于Vi，v属于Vi+1，其中0ik。称G为k段图，s点为起点，t为终点。n在G中求s出发到t的最短路径。这里最短是指s到t的路径上各边权的和最小。第4页，本讲稿共53页算法设计与分析5一个多段图例子记D(u,v)是G中起点为u,终点为v的最短路径，C(u,v)是该路径上各边权的和。设D(s,t)=，vir属

4、于Vr（r=1,2.k-1），则D(vi1,t)=是从vi1出发到t的最短路径，D(vi2,t)=是从vi2出发到t的最短路径等等。设u属于Vi，有：C(u,t)=minw(u,v)+C(v,t)(4.1)vVi+1阶段4:C(7,t)=w(7,t)=8，C(8,t)=w(8,t)=4阶段3:C(4,t)=minw(4,7)+C(7,t),w(4,8)+C(8,t)=12C(5,t)=minw(5,7)+C(7,t),w(5,8)+C(8,t)=10C(6,t)=minw(6,7)+C(7,t),w(6,8)+C(8,t)=8阶段2:C(1,t)=minw(1,4)+C(4,t),w(1,5)

5、+C(5,t)=19C(2,t)=minw(2,4)+C(4,t),w(2,5)+C(5,t),w(2,6)+C(6,t)=17C(3,t)=minw(3,5)+C(5,t),w(3,6)+C(6,t)=13阶段1:C(s,t)=minw(s,1)+C(1,t),w(s,2)+C(2,t),w(s,3)+C(3,t)=16沿求解中带下划线的项回溯，得最短路径解：D(s,t)=第5页，本讲稿共53页算法设计与分析6问题解决关键n求解过程中起到关键作用的是公式(4.1)，它给出了求该问题最优解的基本性质：原始问题最优解与子问题的最优解存在递归关系，称这种关系为问题的最优子结构。最优子结构。最优子结

6、构为构造求解问题的最优决策序列提供了重要线索，它提示可以自底向上的方式逐次由子问题最优解构造原始问题的最优解。n公式(4.1)还有一个重要特征：由给出的自顶向下的递归分解中，每次产生的子问题求解的关键（例如，求C(v,t)）与原问题是类似的，只是在相对较小的子问题空间中考虑问题的解，因此子问题与原始问题存在相似性相似性。而且这些子问题的解在不同的上一级问题中都需要用到，这种特征可以称为子子问题重叠问题重叠。第6页，本讲稿共53页算法设计与分析7n采用邻接矩阵表示图G，其中wij为G中边的权，如果不是G的边,则wij=。G的节点集V=0,1,2,n，其中V0=0是起始点集，Vk=n是终点集，V0

7、,V1,Vk中各子集非空、两两不交。设V1=1，2，.r1，V2=r1+1，r1+2，r2，Vk-1=rk-2+1，rk-2+2，.(n-1)。n【算法4-1】MultiStage_GraphS1:初始化：j=n-1；对i=0,1,n，ci=0；/ci为节点i到终点n的最短路径长S2:求节点r，使得wjr+cr=minwji+ci|是G的边;/按照V0,V1,Vk对节点的标记，ji。S3:cj=wjr+cr,Dj=r;/Dj=r表示边是从j出发到n的最短路径上第1条边S4:j=j-1;S5:如果j0则转S2;S6:输出从源点0出发的最短路径长c0；p0=0,pk=n;S7:对j=1,2,k，p

8、j=Dpj-1;/最短路径Path=第7页，本讲稿共53页算法设计与分析8MultiStage_Graph算法复杂度nG用邻接矩阵表示，对于S2到S5的主循环执行n次。为求满足wjr+cr=minwji+ci|是G的边的r，最多要求n-1次比较。因此时间复杂性为O(n2)。除输入G，输出P外，要求附加存储空间c、D。n如果G采用邻接表表示，求满足最小性的节点r仅对属于G的边访问一次，此算法的时间复杂性应该为O(n+e)（e为G的边数）。n一般地，为避免递归过程中的重复计算，每个子问题首次处理时将结果保存以备查。在上面的过程中，每一次求得的cj都必须记录下来。第8页，本讲稿共53页算法设计与分析

9、9从源点往后推n算法4-1完全是从汇点往前推，实际上我们也可以用同样的思想，从源点出发往后推。阶段1:C(s,1)=w(s,1)=4，C(s,2)=w(s,2)=2,C(s,3)=w(s,3)=3阶段2:C(s,4)=minw(1,4)+C(s,1),w(2,4)+C(s,2)=min14,8=8C(s,5)=minw(1,5)+C(s,1),w(2,5)+C(s,2),w(3,5)+C(s,3)=min13,9,6=6C(s,6)=minw(2,6)+C(s,2),w(3,6)+C(s,3)=min12,11=11阶段3:C(s,7)=minw(4,7)+C(s,4),w(5,7)+C(s,

10、5),w(6,7)+C(s,6)=min12,15,16=12C(s,8)=minw(4,8)+C(s,4),w(5,8)+C(s,5),w(6,8)+C(s,6)=min16,12,15=12阶段4:C(s,t)=minw(7,t)+C(s,7),w(8,t)+C(s,8)=min20,16=16第9页，本讲稿共53页算法设计与分析10MultiStage_Graph2()/*用用Ck来记录到达每一个结点的最短距离来记录到达每一个结点的最短距离,m是划分的段数是划分的段数,Vk表示到达了表示到达了哪一段哪一段*/C01=0;for(k=1;k=m;k+)for(i=1;i=Vk中结点的数目中

11、结点的数目;i+)/*本循环求第本循环求第K段中所有顶点到段中所有顶点到S的最短的最短路径路径*/current=MAX;/*对于对于K段中的一个点段中的一个点i，求出，求出K-1段中所有的点到它的距离，记录下从原点出发段中所有的点到它的距离，记录下从原点出发最短的那一个最短的那一个*/for(j=1;j=Vk-1中结点的数目中结点的数目;j+)r=d(Vki,Vk-1j)+Ck-1j;if(rcurrent)rec=j;current=r;Cki=current;将结点将结点Vki指向结点结点指向结点结点Vk-1rec;从从T到到S沿沿VK逆向输出；逆向输出；第10页，本讲稿共53页算法设计

12、与分析11图中任意两点间的最短距离n如果上面的图不是分段图，仍然可以用此方法来求图中任意两点间的最短路径，这就是大名鼎鼎的Floyd算法。程序段如下：nfor(k=1;k=vtxnum;k+)for(i=1;i=vtxnum;i+)for(j=1;j=vtxnum;j+)if(lengthik+lengthkjlengthij)lengthij=lengthik+lengthkj;pathi,j=pathi,k+pathk,j;第11页，本讲稿共53页算法设计与分析12矩阵连乘问题n给定n个矩阵：A1,A2,An，其中Ai与Ai+1是可乘的。确定一种连乘的顺序，使得矩阵连乘的计算量为最小。n设

13、A和B分别是pq和qr的两个矩阵，则乘积C=AB为pr的矩阵，计算量为pqr次数乘。n但是对于多于2个以上的矩阵连乘，连乘的顺序却非常重要，因为不同的顺序的总计算量将会有很大的差别。第12页，本讲稿共53页算法设计与分析13不同计算顺序的差别n设矩阵A1,A2和A3分别为10100,1005和550的矩阵，现要计算A1A2A3。n若按(A1A2)A3)来计算，则需要的数乘次数为101005+10550=7500n若按(A1(A2A3)来计算，则需要的数乘次数为100550+1010050=75000n后一种计算顺序的计算量竟是前者的10倍！n所以，求多个矩阵的连乘积时，计算的结合顺序是十分重要

14、的。第13页，本讲稿共53页算法设计与分析14不同计算顺序的数量n设n个矩阵的连乘积有P(n)个不同的计算顺序。n先在第k个和第k+1个矩阵之间将原矩阵序列分成两个矩阵子序列，k=1,n；再分别对两个子序列完全加括号，最后对结果加括号，便得到原序列的一种完全加括号方式。n由此可得出关于P(n)的递归式：P(n)=1n=1n1P(k)P(nk)n1k=1n解此递归方程可得P(n)=C(n1)，其中C(n)=1n+12nn=(4n/n3/2)n所以P(n)随n的增长呈指数增长。因而穷举搜索法不是有效的算法。第14页，本讲稿共53页算法设计与分析15分解最优解的结构n将矩阵连乘积AiAi+1Aj记为

15、Ai:j。n若A1:n的一个最优解是在矩阵Ak和Ak+1处断开的，即A1:n=(A1:kAk+1:n)，则A1:k和Ak+1:n也分别是最优解。n事实上，若A1:k的一个计算次序所需计算量更少的话，则用此计算次序替换原来的次序，则得到A1:n一个更少的计算量，这是一个矛盾。同理Ak+1:n也是最优解。n最优子结构性质：最优解的子结构也最优的。最优子结构性质：最优解的子结构也最优的。第15页，本讲稿共53页算法设计与分析16建立递归关系n令mij,1i,jn，为计算Ai,j的最少数乘次数，则原问题为m1n。n当i=j时，Ai,j为单一矩阵，mij=0；n当ij时，利用最优子结构性质有：mij=m

16、inmik+mk+1j+pi1pkpjikj其中矩阵Ai(1in)的维数为pi1pi。n根据此递归式就可以直接用递归程序来实现。第16页，本讲稿共53页算法设计与分析17直接递归的时间复杂性n根据前面的递归式不难得出的时间复杂性为n1(T(k)+T(nk)+1)k=1T(n)n1=(n1)+(T(k)+T(nk)k=1n1n1=(n-1)+T(k)+T(nk)k=1k=1n可用数学归纳法证明T(n)2n1=(2n)。n直接递归算法的时间复杂性随n的指数增长。n1=n+2T(k)k=1第17页，本讲稿共53页算法设计与分析18直接递归中有大量重复计算n直接递归中有大量重复计算，如A1:4计算中：

17、1:41:12:41:23:41:34:42:23:42:34:41:12:23:34:41:12:31:23:33:34:42:23:32:23:31:12:2图中红框标出的都是重复计算。第18页，本讲稿共53页算法设计与分析19消除重复的计算n要消除重复计算，可在计算过程中保存已解决的子问题的答案。这样，每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免重复计算。n计算方式可依据递归式自底向上地进行。n注意到在此问题中，不同的有序对(i,j)就对应不同的子问题，因此不同的子问题个数最多只有Cn2+n=(n2)个。n这样便可以得到多项式时间的算法。第19页，本讲稿共53页算法设计与

18、分析20自底向上的计算n例如对于A1A2A3A4，依据递归式以自底向上的方式计算出各个子问题，其过程如下：m11m22m33m44m12m23m34m13m24m14其中mii=0mii+1=pi1pipi+1mij=minikjmik+mk+1j+pi1pkpj例如：m13=minm11+m23+p0p1p3m12+m33+p0p2p3第20页，本讲稿共53页算法设计与分析21消除重复的矩阵连乘算法nIntMatrixChain(intp,intn,int*m,int*s)nfor(inti=1;i=n;i+)mii=0;n/将对角线元素赋值为零，即单个矩阵计算量为0nfor(intr=2;

19、r=n;r+)/r为连续相乘矩阵的个数nfor(inti=1;i=nr+1;i+)nintj=i+r1;n(5)mij=mi+1j+pi1*pi*pj;n/计算Ai,j=Ai:iAi+1:jnsij=i;/记下断点in(7)for(intk=i+1;kj;k+)nintt=mik+mk+1j+pi1*pk*pj;n/对ikj,逐个计算Ai,j=Ai:kAk+1:jnif(tmij)mij=t;sij=k;n/记下较小的mij及相应的断点knnreturn(m1n);第(5)步与第(7)步能否合在一起?能。此处分开是为了给mij赋初值。第21页，本讲稿共53页算法设计与分析22MatrixCha

20、in的运行举例 设要计算矩阵连乘积A1A2A3A4A5A6，其维数分别为3535,3515,155,510,1020,2025,即p0=35,p1=35,p2=15,p3=5,p4=10,p5=20,p6=25。MatrixChain用矩阵mij,sij存放子问题Ai:j的最小计算量以及相应的断点。1234561 2 3 4 5 6mij1234561 2 3 4 5 6sijMatrixChain将如下面红色箭头所示的过程逐个计算子问题Ai:j：执行for(inti=1;i=n;i+)mii=0后将对角线元素全部置零，即子问题Aii=0。000000当r=2，执行第(5)句完成了相邻矩阵Ai

21、i+1=pi1*pi*pj的计算，并在sij中添入了相应的断点。其中的第(7)句因为j=i+1(k=i+1)而被跳过去了，实际并没有执行。1575026257501000500012345当r=3，i=1时，执行第(5)句计算A1:12:3，m13=m23+p0*p1*p3=2625+30*35*5=787578751执行第(7)句计算A1:23:3，t=m12+m33+p0*p2*p3=15750+0+35*15*5=183757875，所以m13不变，断点仍为1。当r=3，i=2时，执行第(5)句计算A2:23:4，m24=m34+p1*p2*p4=750+35*15*10=6000600

22、02执行第(7)句计算A2:34:4，t=m23+m44+p1*p3*p4=2625+0+35*5*10=43756000，所以m24改为4375，断点改为3。43753当r=3，i=3时，执行第(5)句计算A3:34:5，m35=m45+p2*p3*p5=1000+15*5*20=250025003执行第(7)句计算A3:45:5，t=m34+m55+p2*p4*p5=750+0+15*10*20=37502500，所以m35仍为2500，断点仍为3。当r=3，i=4时，执行第(5)句计算A4:45:6，m46=m56+p3*p4*p6=5000+5*10*25=625062504执行第(7

23、)句计算A4:56:6，t=m45+m66+p3*p5*p6=1000+0+5*20*25=35006250，所以m46改为3500，断点改为5。35005类似的，当r=4、5、6时，可以计算出相应的mij及其相应的断点sij，如下图中所示：937537125353753118753105003151253由m16=15125可知这6个矩阵连乘积的最小运算次数为15125。由s16=3可知A1:6的最优计算次序为A1:3A4:6；由s13=1可知A1:3的最优计算次序为A1:1A2:3；由s46=5可知A4:6的最优计算次序为A4:5A6:6；因此最优计算次序为：(A1(A2A3)(A4A5)

24、A6)。第22页，本讲稿共53页算法设计与分析23MatrixChain的时间复杂性n算法MatrixChain的主要计算取决于程序中对r、i和k的三重循环。循环体内的计算量为O(1)，1r、i、kn，三重循环的总次数为O(n3)。因此该算法时间复杂性的上界为O(n3)，比直接递归算法要有效得多。算法使用空间显然为O(n2)。n这种算法称为动态规划。第23页，本讲稿共53页算法设计与分析24动态规划的基本思想n将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。n这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划

25、算法采用了填表来保存子问题解的方法。n在算法中用表格来保存已经求解的子问题的解，在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。可查表取出其解，避免了重复计算。第24页，本讲稿共53页算法设计与分析25动态规划的基本要素n最优子结构：问题的最优解是由其子问题的最优解所构成的。n重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提

26、高效率。第25页，本讲稿共53页算法设计与分析26动态规划的基本方法n动态规划通常可以按以下几个步骤进行：n(1)找出最优解的性质，并刻画其结构特征；n(2)递归地定义最优值；n(3)以自底向上的方式计算出各子结构的最优值并添入表格中保存；n(4)根据计算最优值时得到的信息，构造最优解。n步骤13是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第为此还需要在第3步中记录构造步中记录构造最优解所必需的信息最优解所必需的信息。第26页，本讲稿共53页算法设计与分析27最长公共子序列n给定序列A=，B=。如果存在A的子序列A1=(i1i2ir)和B的子序列B1=(j1j2jr)

27、，使得aik=bjk(k=1,2,.r)，则称C=A1=B1为序列A、B的一个公共子序列。nA,B的长度最大公共子序列称为A,B的最长公共子序列。n例如：A=，B=，C1=是A、B的一个公共子序列，但不是最长子序列。C2=和C3=都是A、B的最长子序列。n注意：这里的子序列对于原序列而言不一定是连续的。第27页，本讲稿共53页算法设计与分析28求最长公共子序列n对A=，B=求序列A、B的最长公共子序列的最直接方法是对A的所有子序列逐个检查是否为B的子序列，并且在检查过程中记录最长子序列。nA的每个子序列对应下标集1,2,.n的一个子集，因此遍历所有A的不同子序列要求的时间复杂性为O(2n)。n

28、显然这不是一个有效的方法。第28页，本讲稿共53页算法设计与分析29最长公共子序列性质n对长度为n的序列S=，记Sr=(r=n，Sn=S)。n如果C=是A、B的一个最长公共子序列，则C必为如下三种情况之一：1）如果an=bm，则cr=an=bm，即Cr-1是An-1和Bm-1的最长公共子序列；2）如果anbm且cran，则C是An-1和B的最长公共子序列；3）如果anbm且crbm，则C是A和Bm-1的最长公共子序列；n即两个序列的最长公共子序列包含了这两个序列前缀的最长公共子序列。第29页，本讲稿共53页算法设计与分析30最长公共子序列的递归结构n以LCS(A,B)表示序列A、B的最长公共子

29、序列，求LCS(A,B)的递归结构如下：n表示空，|表示在子序列尾部添加一个元素。n计算A、B的最长公共子序列可能要求计算A、Bm-1的公共最长子序列或者An-1、B的公共最长子序列，而这两个子问题又都包含求An-1、Bm-1的公共最长子序列。n以len(i,j)表示LCS(Ai,Bj)的长度有：第30页，本讲稿共53页算法设计与分析31求最长公共子串长度的算法intLCSlength(char*a,char*b,int*len,int*flag)/a、b是输入字符串，输出数组是输入字符串，输出数组len的元素的元素lenij记录记录len(i,j)，/数组数组flag在求在求a、b的最长公共

30、子序列时作为标志使用。的最长公共子序列时作为标志使用。/flagij=0：表示：表示LCS(ai,bj)=LCS(ai-1,bj-1)|ai，ai=bj;/flagij=1：表示：表示LCS(ai,bj)=LCS(ai-1,bj);/flagij=-1:表示表示LCS(ai,bj)=LCS(ai,bj-1);m=strlen(a);n=strlen(b);for(i=0;i=m;i+)leni0=0;for(i=1;i=n;i+)len0i=0;for(i=1;i=m;i+)for(j=1;j=lenij-1)lenij=leni-1j;flagij=1;elselenij=lenij-1;f

31、lagij=-1;return(lenmn);第31页，本讲稿共53页算法设计与分析32求最长公共子串的算法n根据根据LCSlength()输出的标志数组输出的标志数组flag和最长公共子串的长度和最长公共子串的长度值值lenmn，按照公式可以得到子字符串，按照公式可以得到子字符串ai、bj的最长公共的最长公共子串子串c：n求求c=LCS(ai,bj)voidLCS0(inti,intj,char*a,intk,int*flag,chr*c)/k是当前最长公共子串长度，数组是当前最长公共子串长度，数组flag由由LCSlength()得到得到if(i=0)|(j=0)return;if(fla

32、gij=0)LCS0(i-1,j-1,a,k-1,flag,c);ck-1=ai;elseif(flagij=1)LCS0(i-1,j,a,k,flag,c);elseLCS0(i,j-1,a,k,flag,c);第32页，本讲稿共53页算法设计与分析33LCS算法运行举例设A=d,b,a,d,b，B=b,a,b,dLCS用矩阵lenij,flagij存放子问题Ai与Bj的最长公共子串长度和相应的标志01234501 2 3 4 12345 1 2 3 4 lenijflagijLCSlength将如下面红色箭头所示的过程逐个计算子问题执行for(i=0;i=m;i+)leni0=0;for(

33、i=0;i=m;i+)len0i=0;后完成初始化如下：0000000000当i=1，依次比较A1与Bj及len0j与len1j-1，填入len1j与flag1j的值如下：A1B1且len01=len10，len11=len01=0;flag11=1;01 A1B2且len02=len11，len12=len02=0;flag12=1;010 A1B3且len03=len12，len13=len03=0;flag13=1;1 A1=B4，len14=len03+1=1;flag14=0;10当i=2，依次比较A2与Bj及len1j与len2j-1，填入len2j与flag2j的值如下：A2=B

34、1，len21=len10+1=1;flag21=0;10 A2B2且len12len21;len22=len21=1;flag22=-1;1-1 A2=B3;len23=len12+1=1;flag23=0;10 A2B4且len14len23;len24=len23=2;flag24=-1;11类似的，当i=3，4，5时可以计算出相应的lenij及flagij，如下图所示：12102-12-1112-1213010213031故得到最长公共子串C长度为k=3；最后再由flag标识根据算法LCS0得到C=b,a,d。第33页，本讲稿共53页算法设计与分析34LCS的时间复杂性n算法LCSle

35、ngth的主要计算取决于程序中对i和j的二重循环，循环的总次数为O(nm)。n算法LCS0的每次递归调用中i减1或者j减1，因此时间复杂性为O(n+m)，。第34页，本讲稿共53页算法设计与分析35凸多边形最优三角剖分n凸多边形的三角剖分是将一个凸多边形分割成互不相交的三角形的弦的集合T。n下面是一个凸7边形的2个不同的三角剖分：v0v1v2v3v4v5v6v0v1v2v3v4v5v6n在凸多边形的一个三角剖分T中，各弦互不相交，且T已达到最大，即任何一条不在T中的弦必与T中某弦相交。n在有n个顶点的凸多边形的三角剖分中，恰有n3条弦和n2个三角形。n凸多边形的最优三角剖分问题：给定凸多边形P

36、=v0,v1,vn1，以及定义在由凸多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的一个三角剖分，使得该剖分中诸三角形上权之和为最小。n可定义三角形上各种各样的权函数w。n例如w(vivjvk)=|vivj|+|vjvk|+|vkvi|，其中|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。第35页，本讲稿共53页算法设计与分析36三角剖分与矩阵连乘积同构n三角剖分问题和矩阵连乘积问题都对应于一个完全二叉树，也称为表达式的语法树。0123A1A44A2A3A5A6(A1(A2A3)(A4(A5A6)所对应的二叉树v1v0v2v3v4v5v601

37、2A13A2A3A44A5A6凸多边形v0v1v2v3v4v5v6一个三角剖分所对应的二叉树nn个矩阵连乘积计算顺序同构于n个叶子的完全二叉树，凸(n+1)边形三角剖分同构于n个叶子的完全二叉树，所以n个矩阵连乘积的计算顺序问题同构于凸(n+1)边形的三角剖分问题。n事实上，矩阵连乘积最优计算顺序问题相当于是凸多边形最优三角剖分问题中一种特殊定义的权函数的情形。第36页，本讲稿共53页算法设计与分析37最优子结构性质n能应用动态规划求解的问题应具有最优子结构性质。凸多边形最优三角剖分问题具有最优子结构性质。n事实上，若凸(n+1)边形P=v0,v1,vn的一个最优三角剖分T包含了三角形v0vk

38、vn，1kn，则T的权为三角形v0vkvn、多边形v0,v1,vk和多边形vk,vk+1,vn的权之和。显然这两个子多边形的三角剖分也是最优的。n因为，其中若有一个子多边形的三角剖分不是最优的将导致T不是最优三角剖分的矛盾。第37页，本讲稿共53页算法设计与分析38最优三角剖分的递归结构n定义tij,1ijn,为子多边形vi1,vi,vj的最优三角剖分所对应的权函数值，并为方便起见，设退化的多边形vi1,vi的权值为0。n于是凸(n+1)边形的最优三角剖分为t1nn易知，tij可递归定义为n当i=j时，为退化多边形vi1,vi，tij=0；n当ij时，利用最优子结构性质有：tij=mintik

39、+tk+1j+w(vi1vkvj)ikj与矩阵连乘积问题相对比：mij=minmik+mk+1j+pi1pkpjikjn显然，矩阵连乘积的最优计算顺序与凸多边形最优三角剖分具有完全相同的递归结构。第38页，本讲稿共53页算法设计与分析39最优三角剖分的算法n由于凸多边形最优三角剖分与矩阵连乘积的最优计算顺序具有完全相同的递归结构，其区别仅在于权函数的不同，所以只需要修改求矩阵连乘积的最优计算顺序的算法中的权函数计算便可得到凸多边形最优三角剖分的算法。n显然该算法的时间复杂性也是O(n3)。nVoidMinWeightTriangulation(intn,Type*t,int*s)nfor(in

40、ti=1;i=n;i+)tii=0;nfor(intr=2;r=n;r+)nfor(inti=1;i=nr+1;i+)nintj=i+r1;ntij=ti+1j+w(i1,i,j);nsij=i;nfor(intk=i+1;kj;k+)nintu=tik+tk+1j+w(i1,k,j);nif(utij)tij=u;sij=k;n/程序中红色的部分为改动的地方第39页，本讲稿共53页算法设计与分析40动态规划总结n与分治法相比，相同之处是也将原问题分解为若干子问题，再递归求解；不同之处是所分解的子问题彼此并不独立，而是互有重叠。n基本思想是造表记录已解的子问题，再次遇到时仅查表即可，避免了重复

41、计算，提高效率。n通常用于求解具有最优性质的问题，而且其子问题也具有最优性质(最优子结构性质)。n实现方法通常为自底向上的递归形式，但也可以采用自上而下的形式(备忘录方法)。第40页，本讲稿共53页算法设计与分析41课堂练习n最大子段和问题给定由n个整数（可能有负整数）组成的序列，a1,a2,an,求该序列中连续子段和的最大值。当所有整数均为负数时，定义其最大子段和为0。例如：序列（-2,11,-4,13,-5,-1），最大子段和为：(11,-4,13)=20。第41页，本讲稿共53页nS(ai)表示以ai为最末字符的连续子串的最大值n令S(a0)=0n则S(ai)=maxS(ai-1)+ai

42、,ai|i=1,2,.,n算法设计与分析42第42页，本讲稿共53页算法设计与分析43课堂练习n递增最长子序列问题已知序列A=（a1,a2,.,an），设计一个动态规划算法，能在O(n2)的时间内求出该序列的递增最长子序列。例如：序列A=（5,12,46,32,1,45,7,9,51,10,18）它的递增最长子序列为：（1,7,9,10,18）或者（5,7,9,10,18）（只要找到一个即可）第43页，本讲稿共53页算法设计与分析44n用bj记序列a1:j中最长单调递增子序列的长度，sj为序列a1:j中所有长度为bj的单调递增子序列末尾元素的最小值。则第44页，本讲稿共53页算法设计与分析45

43、多边形游戏n有一个n边形，每个顶点被赋予一整数值，每条边上被赋予一个运算符“+”或“-”。n游戏的第1步，将一条边删去；n随后的n1步按以下方式操作：n(1)选择一条边e及其所连接的两个顶点v1和v2；n(2)用一个新顶点取代边e以及顶点v1和v2，赋予新顶点的值为顶点v1和v2的值通过边e上的运算所得到的值。n最后所有的边被删去，所剩顶点的值即为得分第45页，本讲稿共53页算法设计与分析46多边形游戏的表达n设所有的边依次从1到n编号，按顺时针序列为op1,v1,op2,v2,opn,vn其中opi为边i上的运算符，vi为顶点i上的值。n将多边形中始于顶点i(1in)，长度为j的顺时针链vi

44、,opi+1,vi+j1表示为p(i,j)。n若链p(i,j)最后一次合并在opi+s(1sj1)处发生，则被分割为两个子链p(i,s)和p(i+s,js)第46页，本讲稿共53页算法设计与分析47多边形游戏的最优子结构性质n若链p(i,j)取最优值的最后一次合并是在opi+s处发生的，则子链p(i,s)和p(i+s,js)也是最优。n因为若子链p(i,s)和p(i+s,js)不是最优的，则可推出链p(i,j)也不是最优的矛盾。所以多边形游戏具有最优子结构性质。n但是这里的最优子结构要稍微地复杂一点。n若p(i,j)的最后合并的边opi+s=“+”，子链p(i,s)和p(i+s,s)应该取最大

45、值，n若p(i,j)的最后合并的边opi+s=“-”，子链p(i,s)和p(i+s,js)应如何取值呢？第47页，本讲稿共53页算法设计与分析48多边形游戏的最优子结构分析n设m1是对子链p(i,s)的任意合并方式得到的值，a和b是其最小值和最大值，m2是对子链p(i+s,js)的任意合并方式得到的值，c和d分别是最小值和最大值，即am1b，cm2d。n若opi+s=“+”，则a+cmb+d。可见p(i,s)的最小、最大值分别对应于子链的最小、最大值。n若opi+s=“-”，则a-dmb-cn即主链最小、最大值亦来自子链最小、最大值。第48页，本讲稿共53页算法设计与分析49多边形游戏的递归求

46、解n由前面的分析可知，为了求链合并的最大值，必须同时求子链合并的最大值和最小值。因此整个计算过程中应同时计算最大值和最小值。n设链p(i,j)合并的最大、最小值分别是mi,j,0和mi,j,1，最优合并处是在opi+s，且长度小于j的子链的最大、最小值均已算出，且记：na=mi,i+s,0,b=mi,i+s,1,c=mi+s,js,0，d=mi+s,js,1，则n当opi+s=“+”时，mi,j,0=a+c，mi,j,1=b+dn当opi+s=“*”时，mi,j,0=bc，mi,j,1=ad第49页，本讲稿共53页算法设计与分析50多边形游戏的递归求解n令p(i,j)在opi+s断开的最大值和

47、最小值分别为maxf(i,j,s)和minf(i,j,s)，综合上面的讨论则minf(i,j,s)=a+copi+s=“+”adopi+s=“”maxf(i,j,s)=b+dopi+s=“+”bcopi+s=“”n由于p(i,j)的最优断开位置s有1sj1的j1种情况，于是便可得到求解多边形游戏的递归式：第50页，本讲稿共53页算法设计与分析51求解多边形游戏的递归式n由于多边形是封闭的，当i+sn时，顶点i+s实际编号应为(i+s)modn。n多边形游戏的最大得分即为mi,n,1。mi,j,0=minminf(i,j,s),1i,jn1sjmi,j,1=maxmaxf(i,j,s),1i,j

48、n1sj初始边界值为：mi,1,0=mi,1,1=vi,1in,j=1第51页，本讲稿共53页算法设计与分析52多边形游戏的动态规划算法n依据上述讨论以及所得的递归式，不难写出多边形游戏动态规划算法。请同学们自己编写。n算法的主程序为Poly_Max，它包含了一个子程序MIN_MAX。子程序MIN_MAX负责对确定s的minf(i,j,s)和maxf(i,j,s)的计算。而对任意链的最大值mi,j,1和最小值mi,j,0的计算则是在主程序Poly_Max中进行的。n算法的时间复杂性显然仍为O(n3)。第52页，本讲稿共53页算法设计与分析53作业：n第四章习题1，6，9第53页，本讲稿共53页