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

算法设计与分析动态规划第四章2023/2/20计算机算法设计与分析1第1页，本讲稿共58页2023/2/20计算机算法设计与分析2矩阵连乘问题给定n个矩阵：A1,A2,An，其中Ai与Ai+1是可乘的。确定一种连乘的顺序，使得矩阵连乘的计算量为最小。设A和B分别是pq和qr的矩阵，则乘积C=AB为pr的矩阵，计算量为pqr次数乘。但是对于多于2个以上的矩阵连乘，连乘的顺序却非常重要，因为不同的顺序的总计算量将会有很大的差别。第2页，本讲稿共58页2023/2/20计算机算法设计与分析3不同计算顺序的差别设矩阵A1,A2和A3分别为10100,1005和550的矩阵，现要计算A1A2A3。若按(A1A2)A3)来计算，则需要的数乘次数为101005+10550=7500若按(A1(A2 A3)来计算，则需要的数乘次数为100 5 50+1010050=75000两种计算顺序的计算量竟然相差两种计算顺序的计算量竟然相差10倍！倍！计算顺序通计算顺序通过加括号来过加括号来实现实现第3页，本讲稿共58页2023/2/20计算机算法设计与分析4不同计算顺序的数量设n个矩阵的连乘有P(n)个不同的计算顺序。先在第k个和第k+1个矩阵之间将原矩阵序列分成两个矩阵子序列，k=1，n；再分别对两个子序列完全加括号，最后对结果加括号，便得到原序列的一种完全加括号方式。第4页，本讲稿共58页2023/2/20计算机算法设计与分析5不同计算顺序的数量设n个矩阵的连乘有P(n)个不同的计算顺序。由此可得出关于P(n)的递归式：P(n)=1 n=1 n1P(k)P(nk)n1 k=1 解此递归方程可得P(n)=C(n1)，其中C(n)=1 n+12n n=(4n/n3/2)P(n)随n的增长呈指数增长。第5页，本讲稿共58页2023/2/20计算机算法设计与分析6分解最优解的结构将AiAi+1Aj的矩阵连乘问题记为Ai:j。设A1:n 的一个最优解是在Ak和Ak+1处断开的，即A1:n=(A1:k Ak+1:n)，则A1:k和Ak+1:n也分别是其最优解。否者，若有A1:k的一个计算次序的计算量更少的话，则用此计算次序替换原来的次序，则得到A1:n一个更少计算量。矛盾。同理Ak+1:n也是最优解。第6页，本讲稿共58页2023/2/20计算机算法设计与分析7最优子结构性质A1A2An的矩阵连乘问题，即A1:n，的最优解中的子问题A1:k和Ak+1:n的解也是该子问题的最优解。最优子结构性质：如果某问题的每个最优最优子结构性质：如果某问题的每个最优解中的子问题的解也是最优的，则称该问解中的子问题的解也是最优的，则称该问题具有最优子结构性质。题具有最优子结构性质。换言之，满足最优子结构性质的问题的最优解是由子问题的最优解构成的。第7页，本讲稿共58页2023/2/20计算机算法设计与分析8建立递归关系令mij,1i,jn，为计算Ai,j 的最少数乘次数，则原问题为m1n。当i=j时，Ai,j为单一矩阵，mij=0；当ij时，利用最优子结构性质有：mij=minmik+mk+1j+pi1pkpjikj其中矩阵Ai，1in，的维数为pi1pi。只需数组Pn+1就可存放各矩阵的行列数。注意：因为这注意：因为这n个矩阵可乘，故后一个矩阵的个矩阵可乘，故后一个矩阵的行数就是一个矩阵的列数。行数就是一个矩阵的列数。P0为为A1的行数的行数,P1为为A1的列数，也是的列数，也是A2的行数的行数,以此类推。最以此类推。最后的后的Pn是是An的列数。的列数。第8页，本讲稿共58页2023/2/20计算机算法设计与分析9递归的执行过程该递归自顶向下地执行，如A1:4计算：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第9页，本讲稿共58页2023/2/20计算机算法设计与分析10直接递归的时间复杂性根据该递归式不难得出的时间复杂性为 n11+(T(k)+T(nk)+1)k=1 T(n)n1=1+(n 1)+(T(k)+T(nk)k=1 n1 n1=n+T(k)+T(nk)k=1 k=1 该递归算法的时间复杂性为O(2n)。n1 =n+2T(k)k=1 用数学归用数学归纳法可证纳法可证T(n)2n1=O(2n)。第10页，本讲稿共58页2023/2/20计算机算法设计与分析11递归的执行过程在此递归的执行中有大量重复计算：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红色的都是红色的都是重复计算！重复计算！第11页，本讲稿共58页2023/2/20计算机算法设计与分析12子问题个数最多为O(n2)可在计算过程中保存已解子问题的答案。这样，每个子问题只要计算一次，而在后面需要该子问题答案时只要简单查一下，从而避免了重复计算。计算方式可从最简单的子问题开始，依据递归式自底向上地进行。此问题中不同有序对(i,j)就对应不同子问题，故子问题个数最多有C +n=O(n2)个。n2第12页，本讲稿共58页2023/2/20计算机算法设计与分析13自底向上的计算例如对于A1A2A3A4，依据递归式以自底向上的方式计算出各个子问题，其过程如下：m11m22m33m44m12m23m34m13m24m14其中mii=0mii+1=pi1pipi+1mij=minikj mik+mk+1j+pi1pkpj最简单情况是单个最简单情况是单个矩阵的计算。矩阵的计算。第13页，本讲稿共58页2023/2/20计算机算法设计与分析14自底向上的计算例如对于A1A2A3A4，依据递归式以自底向上的方式计算出各个子问题，其过程如下：m11m22m33m44m12m23m34m13m24m14mii=0mii+1=pi1pipi+1例如：m13=min m11+m23+p0p1p3m12+m33+p0p2p3第14页，本讲稿共58页2023/2/20计算机算法设计与分析15自底向上的计算例如对于A1A2A3A4，依据递归式以自底向上的方式计算出各个子问题，其过程如下：m11m22m33m44m12m23m34m13m24m14mii=0mii+1=pi1pipi+1例如：m14=m11+m24+p0p1p4m12+m34+p0p2p4m13+m44+p0p3p4min 第15页，本讲稿共58页2023/2/20计算机算法设计与分析16自底向上的计算例如对于A1A2A3A4，依据递归式以自底向上的方式计算出各个子问题，其过程如下：m11m22m33m44m12m23m34m13m24m14这层的断点为这层的断点为0个个。这层的断点为这层的断点为1个个。这层的断点为这层的断点为2个个。这层的断点为这层的断点为3个。个。第16页，本讲稿共58页2023/2/20计算机算法设计与分析17矩阵连乘算法给矩阵连乘算法取个名字MatrixChain。第17页，本讲稿共58页2023/2/20计算机算法设计与分析18矩阵连乘算法MatrixChain(形参表）初始化；自底向上地计算每一个mij并将结果填入表中。底是底是mii，即对角线元素。，即对角线元素。最顶层是最顶层是m1n。初始化是将初始化是将mii，即对角线，即对角线元素，赋值为元素，赋值为0。第18页，本讲稿共58页2023/2/20计算机算法设计与分析19矩阵连乘算法的数据结构形参表中应有n和Pn+1。算法需要两个二维数组：二维矩阵mnn。其每个元素mij,1i,jn，为Ai,j 的最少数乘次数。二维矩阵snn，其元素sij,1i,jn，为计算Ai,j 的断点位置。第19页，本讲稿共58页2023/2/20计算机算法设计与分析20矩阵连乘算法MatrixChain(n,Pn+1）初始化：将初始化：将mii 赋值为赋值为0。for(i=1;i=n;i+)mii=0;第20页，本讲稿共58页2023/2/20计算机算法设计与分析21矩阵连乘算法MatrixChain(n,Pn+1）for(i=1;i=n;i+)mii=0;for(r=2;r=n;r+)for(i=1;i=n r+1;i+)j=i+r 1;for(k=i;k j;k+)t=mik+mk+1j+pi1*pk*pj;if(t mij)mij=t;sij=k;从第二层开始，对从第二层开始，对(i,j)间的每个断点间的每个断点k，计算，计算mi,j=mi:kmk+1:j+pi1*pk*pj，并记下较小的并记下较小的mij及相应的断点及相应的断点k。第21页，本讲稿共58页2023/2/20计算机算法设计与分析22矩阵连乘算法MatrixChain(n,Pn+1）for(i=1;i=n;i+)mii=0;for(r=2;r=n;r+)for(i=1;i=n r+1;i+)j=i+r 1;for(k=i;k j;k+)t=mik+mk+1j+pi1*pk*pj;if(t mij)mij=t;sij=k;当当r=2，对每个，对每个i，j为为i+1，最内层循环仅执行一，最内层循环仅执行一次，计算相邻两个矩阵的数乘次数，即次，计算相邻两个矩阵的数乘次数，即Ai,i+1=Ai,i+Ai+1,i+1+pi1*pi*pi+1。第22页，本讲稿共58页2023/2/20计算机算法设计与分析23矩阵连乘算法MatrixChain(n,Pn+1）for(i=1;i=n;i+)mii=0;for(r=2;r=n;r+)for(i=1;i=n r+1;i+)j=i+r 1;for(k=i;k j;k+)t=mik+mk+1j+pi1*pk*pj;if(t 2，每对，每对(i,j)中的断点中的断点k有有r 1个，越往个，越往高层断点数目越多。这样自底向上完成整个高层断点数目越多。这样自底向上完成整个mij的计算。的计算。第23页，本讲稿共58页2023/2/20计算机算法设计与分析24矩阵连乘算法MatrixChain(n,Pn+1）for(i=1;i=n;i+)mii=0;for(r=2;r=n;r+)for(i=1;i=n r+1;i+)j=i+r 1;for(k=i;k j;k+)t=mik+mk+1j+pi1*pk*pj;if(t mij)mij=t;sij=k;第24页，本讲稿共58页2023/2/20计算机算法设计与分析25MatrixChain的运行举例MatrixChain用矩阵mij,sij存放子问题Ai:j的最小计算量以及相应的断点。123456 1 2 3 4 5 6mij1 2 3 4 5 6sij第25页，本讲稿共58页2023/2/20计算机算法设计与分析26MatrixChain的运行举例MatrixChain将如下面红色箭头所示的过程逐个计算子问题Ai:j：。123456 1 2 3 4 5 6mij1 2 3 4 5 6sij第26页，本讲稿共58页2023/2/20计算机算法设计与分析27MatrixChain的运行举例123456 1 2 3 4 5 6mij1 2 3 4 5 6sij设要计算矩阵连乘积A1A2A3A4A5A6，其维数分别为3535,3515,155,510,1020,2025,即p0=35,p1=35,p2=15,p3=5,p4=10,p5=20,p6=25。第27页，本讲稿共58页2023/2/20计算机算法设计与分析28MatrixChain的运行举例123456 1 2 3 4 5 6mij1 2 3 4 5 6sij执行for(int i=1;i 7857。m13仍为7857。第31页，本讲稿共58页2023/2/20计算机算法设计与分析32MatrixChain的运行举例123456 1 2 3 4 5 6mij1 2 3 4 5 6sij当r=3，i=2时，断点k有两个：000000157501262527503100045000578751对断点k=2，计算A2:4有m24=m34+p1*p2*p4=750+35*15*10=6000。60002第32页，本讲稿共58页2023/2/20计算机算法设计与分析33MatrixChain的运行举例123456 1 2 3 4 5 6mij1 2 3 4 5 6sij当r=3，i=2时，断点k有两个：000000157501262527503100045000578751对断点k=3，计算A2:3A4:4有m24=m23+m44+p1*p3*p4=2625+0+35*5*10 =4375 6000。m24改为4375，断点改为3。6000243753第33页，本讲稿共58页2023/2/20计算机算法设计与分析34MatrixChain的运行举例123456 1 2 3 4 5 6mij1 2 3 4 5 6sij当r=3，i=3时，断点k有两个：000000157501262527503100045000578751对断点k=3，计算A3:3A4:5有m35=m45+m45+p2*p3*p5=1000+15*5*20=2500。4375325003第34页，本讲稿共58页2023/2/20计算机算法设计与分析35MatrixChain的运行举例123456 1 2 3 4 5 6mij1 2 3 4 5 6sij当r=3，i=3时，断点k有两个：000000157501262527503100045000578751对断点k=4，计算A3:4A5:5有m35=m34+m55+p2*p4*p5=750+0+15*10*20=3750 2500。m35仍为2500，断点仍为3。4375325003第35页，本讲稿共58页2023/2/20计算机算法设计与分析36MatrixChain的运行举例123456 1 2 3 4 5 6mij1 2 3 4 5 6sij当r=3，i=4时，断点k有两个：000000157501262527503100045000578751对断点k=4，计算A4:4A5:6有m46=m44+m56+p3*p4*p6=5000+5*10*25=6250437532500362504第36页，本讲稿共58页2023/2/20计算机算法设计与分析37MatrixChain的运行举例123456 1 2 3 4 5 6mij1 2 3 4 5 6sij当r=3，i=4时，断点k有两个：000000157501262527503100045000578751对断点k=5，计算A4:5A6:6有m46=m45+m66+p3*p5*p6=1000+0+5*20*25=35006250。m46改为3500，断点改为5。43753250036250435005第37页，本讲稿共58页2023/2/20计算机算法设计与分析38MatrixChain的运行举例123456 1 2 3 4 5 6mij1 2 3 4 5 6sij类似的，当r=4、5、6时，可计算出相应的mij及其相应的断点sij，如下图中所示：000000157501262527503100045000578751437532500335005937537125353753118753105003151253第38页，本讲稿共58页2023/2/20计算机算法设计与分析39MatrixChain的运行举例123456 1 2 3 4 5 6mij1 2 3 4 5 6sij000000157501262527503100045000578751437532500335005937537125353753118753105003151253由m16知此矩阵连乘的最小数乘量为15125。由s16=3、s13=1、s46=5可知矩阵连乘的最优计算次序为：(A1(A2A3)(A4A5)A6)。第39页，本讲稿共58页2023/2/20计算机算法设计与分析40MatrixChain的时间复杂性算法MatrixChain的主要计算取决于程序中对r、i和k的三重循环。循环体内的计算量为O(1)，1 r、i、kn，三重循环的总次数为O(n3)。因此该算法时间复杂性的上界为O(n3)，比直接递归算法要有效得多。算法使用空间显然为O(n2)。这种算法就称为动态规划。第40页，本讲稿共58页2023/2/20计算机算法设计与分析41动态规划的基本思想其求解方法与分治法是相同的。不同之处是子问题不是相互独立的，而是互有重叠。为了避免重复计算，动态规划算法采用填表来保存子问题解的方法。在求解过程中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，从而避免了重复计算。第41页，本讲稿共58页2023/2/20计算机算法设计与分析42动态规划的基本要素最优子结构：最优解由子问题最优解构成。重叠子问题：子问题彼此有重叠的。最优子结构性质使之能以自底向上的方式递归地最优子结构性质使之能以自底向上的方式递归地从子结构最优解构造出问题的最优解。从子结构最优解构造出问题的最优解。子问题重叠造成重复计算。这样就可以用填子问题重叠造成重复计算。这样就可以用填表保存子问题解的方法来提高效率。表保存子问题解的方法来提高效率。第42页，本讲稿共58页2023/2/20计算机算法设计与分析43动态规划的基本方法动态规划求解的步骤：找出最优解性质，并刻画其结构特征；给出最优解的递归定义；自底向上地计算并保存子问题最优解；根据步骤中得到的信息构造最优解。步骤 是动态规划算法的基本步骤。若要构造最优解，则必须执行步骤，为此需在步骤中增加必要信息的记录。第43页，本讲稿共58页2023/2/20计算机算法设计与分析44动态规划的算法框架DynamicProgram(形参表）初始化；自底向上地计算子任务并将结果填入表中。第44页，本讲稿共58页2023/2/20计算机算法设计与分析45动态规划的备忘录方法动态规划中的自底向上方式与递归定义中自上而下的描述往往不一致。用自上而下的方式求解也可避免重复。How to do it?同样用表来存放子问题的解，初始时所有子问题都标记为未解。在求解过程中，对待解子问题，先查看是否已解。若已解，则取出其结果，否则计算其解并保存。这种方法称为动态规划的备忘录方法。这种方法称为动态规划的备忘录方法。第45页，本讲稿共58页2023/2/20计算机算法设计与分析46凸多边形的三角剖分凸多边形的三角剖分是将一个凸多边形分割成互不相交的三角形的弦的集合T。下面是一个凸7边形的2个不同的三角剖分：v0v1v2v3v4v5v6v0v1v2v3v4v5v6第46页，本讲稿共58页2023/2/20计算机算法设计与分析47凸多边形的三角剖分凸多边形的三角剖分是将一个凸多边形分割成互不相交的三角形的弦的集合T。在凸多边形的一个三角剖分T中，各弦互不相交，且T已达到最大，即任何一条不在T中的弦必与T中某弦相交。在有n个顶点的凸多边形的中三角剖分中，恰有n3条弦和n2个三角形。第47页，本讲稿共58页2023/2/20计算机算法设计与分析48凸多边形的最优三角剖分问题：给定凸多边形P=v0,v1,vn1及定义在由P的边和弦组成的三角形上的权函数w。求P的一个三角剖分T，使得T中诸三角形上权之和为最小。可定义三角形上各种各样的权函数w。例如：w(vivjvk)=|vivj|+|vjvk|+|vkvi|，其中|vivj|是点vi到vj的欧氏距离，其对应的最优三角剖分就是最小弦长三角剖分。第48页，本讲稿共58页2023/2/20计算机算法设计与分析49三角剖分与矩阵连乘积同构三角剖分问题和矩阵连乘问题都对应于一棵完全二叉树，也称为表达式的语法树。0123A1A44A2A3A5A6(A1(A2A3)(A4(A5A6)所对应的二叉树凸多边形v0v1v2v3v4v5v6的三角剖分对应的二叉树v0v1v2v3v4v5v612A13A2A3A44A5A60第49页，本讲稿共58页2023/2/20计算机算法设计与分析50三角剖分与矩阵连乘积同构三角剖分问题和矩阵连乘问题都对应于一棵完全二叉树，也称为表达式的语法树。0123A1A44A2A3A5A6v0v1v2v3v4v5v612A13A2A3A44A5A60显然，矩阵连乘的最优计算顺序与凸多边形最优三角剖分有完全具相同的递归结构。第50页，本讲稿共58页2023/2/20计算机算法设计与分析51最优子结构性质最优三角剖分问题具有最优子结构性质。若凸多边形P=v0,v1,vn的最优三角剖分T包含三角形v0vkvn，1kn，则T的权为三角形v0vkvn，多边形P1=v0,v1,vk 和多边形P2=vk,vk+1,vn的权之和。显然P1和P2的三角剖分也是最优的。因为，若P1或P2的三角剖分不是最优的，则导致T不是最优三角剖分的矛盾。第51页，本讲稿共58页2023/2/20计算机算法设计与分析52最优三角剖分的递归结构定义mij，1ijn，为子多边形vi1,vi,vj的最优三角剖分所对应的权函数值，并设退化多边形vi1,vi的权值为0。mij可递归定义为：当i=j时，mij=0；退化多边形退化多边形vi1,vi第52页，本讲稿共58页2023/2/20计算机算法设计与分析53最优三角剖分的递归结构定义mij，1ijn，为子多边形vi1,vi,vj的最优三角剖分所对应的权函数值，并设退化多边形vi1,vi的权值为0。mij可递归定义为：当i=j时，mij=0；mij=minmik+mk+1j+w(vi1vkvj)ikj当ij时，有：w(vi1vkvj计算以计算以vi1、vk和和vj为顶点的三角形的为顶点的三角形的周长。周长。第53页，本讲稿共58页2023/2/20计算机算法设计与分析54最优三角剖分的递归结构定义tij,1ijn,为子多边形vi1,vi,vj的最优三角剖分所对应的权函数值，并设退化多边形vi1,vi的权值为0。tij可递归定义为：当i=j时，tij=0；mij=minmik+mk+1j+w(vi1vkvj)ikj当ij时，有：矩阵连乘问题的递归式：mij=minmik+mk+1j+pi1pkpj ikj只是权函数不同而已只是权函数不同而已第54页，本讲稿共58页2023/2/20计算机算法设计与分析55最优三角剖分的算法MatrixChain(n,P)for(i=1;i=n;i+)mii=0for(r=2;r=n;r+)for(i=1;i=n r+1;i+)j=i+r 1;for(k=i;k j;k+)t=mik+mk+1j+pi1*pk*pj;if(t mij)mij=t;sij=k;这是求解矩阵连乘这是求解矩阵连乘问题的程序。问题的程序。既然最优三角剖既然最优三角剖分问题和它同构分问题和它同构且只是权函数的且只是权函数的不同，那么只要不同，那么只要对该程序做修改对该程序做修改就可以了。就可以了。第55页，本讲稿共58页2023/2/20计算机算法设计与分析56最优三角剖分的算法MatrixChain(n,for(i=1;i=n;i+)mii=0;for(r=2;r=n;r+)for(i=1;i=n r+1;i+)j=i+r 1;for(k=i;k j;k+)t=mik+mk+1j+if(t mij)mij=t;sij=k;用二维矩阵表示多用二维矩阵表示多边形顶点坐标。边形顶点坐标。P)P)pi1*pk*pj;w(i1,k,j);权重的计算修改权重的计算修改为三角形周长的为三角形周长的计算。计算。第56页，本讲稿共58页2023/2/20计算机算法设计与分析57最优三角剖分的算法由于凸多边形最优三角剖分与矩阵连乘积的最优计算顺序具有完全相同的递归结构，其区别仅在于权函数的不同，所以只需要修改求矩阵连乘积的最优计算顺序的算法中的权函数计算便可得到凸多边形最优三角剖分的算法。显然该算法的时间复杂性也是O(n3)。第57页，本讲稿共58页2023/2/20计算机算法设计与分析58动态规划总结与分治法相比，相同之处是也将原问题分解为若干子问题，再递归求解；不同之处是所分解的子问题彼此并不独立，而是互有重叠。基本思想是造表记录已解的子问题，再次遇到时仅查表即可，避免了重复计算，提高效率。通常用于求解具有最优性质的问题，而且其子问题也具有最优性质(最优子结构性质)。实现方法通常为自底向上的递归形式，但也可以采用自上而下的形式(备忘录方法)。第58页，本讲稿共58页