第三章动态规划算法课件

算法设计与分析1矩阵连乘问题n给定n个矩阵：A1,A2,An，其中Ai与Ai+1是可乘的。确定一种连乘的顺序，使得矩阵连乘的计算量为最小。n设A和B分别是pq和qr的两个矩阵，则乘积C=AB为pr的矩阵，计算量为pqr次数乘。n但是对于多于2个以上的矩阵连乘，连乘的顺序却非常重要，因为不同的顺序的总计算量将会有很大的差别。算法设计与分析2不同计算顺序的差别n设矩阵A1,A2和A3分别为10100,1005和550的矩阵，现要计算A1A2A3。n若按(A1A2)A3)来计算，则需要的数乘次数为101005+10550=7500n若按(A1(A2 A3)来计算，则需要的数乘次数为100 5 50+1010050=75000n后一种计算顺序的计算量竟是前者的10倍！n所以，求多个矩阵的连乘积时，计算的结合顺序是十分重要的。算法设计与分析3不同计算顺序的数量n设n个矩阵的连乘积有P(n)个不同的计算顺序。n先在第k个和第k+1个矩阵之间将原矩阵序列分成两个矩阵子序列，k=1，n；再分别对两个子序列完全加括号，最后对结果加括号，便得到原序列的一种完全加括号方式。n由此可得出关于P(n)的递归式：P(n)=1 n=1n1P(k)P(nk)n1k=1 n解此递归方程可得P(n)=C(n1)，其中C(n)=1 n+12n n=(4n/n3/2)n所以P(n)随n的增长呈指数增长。因而穷举搜索法不是有效的算法。算法设计与分析4分解最优解的结构n将矩阵连乘积AiAi+1Aj记为Ai:j。n若A1:n 的一个最优解是在矩阵Ak和Ak+1处断开的，即A1:n=(A1:k Ak+1:n)，则A1:k和Ak+1:n也分别是最优解。n事实上，若A1:k的一个计算次序所需计算量更少的话，则用此计算次序替换原来的次序，则得到A1:n一个更少的计算量，这是一个矛盾。同理Ak+1:n也是最优解。n最优子结构性质：最优解的子结构也最优的。算法设计与分析5建立递归关系n令mij,1i,jn，为计算Ai,j 的最少数乘次数，则原问题为m1n。n当i=j时，Ai,j为单一矩阵，mij=0；n当ij时，利用最优子结构性质有：mij=minmik+mk+1j+pi1pkpjikj其中矩阵Ai，1in，的维数为pi1pi。n根据此递归式就可以直接用递归程序来实现。算法设计与分析6直接递归的时间复杂性n根据前面的递归式不难得出的时间复杂性为 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 n可用数学归纳法证明T(n)2n1=(2n)。n直接递归算法的时间复杂性随n的指数增长。n1 =n+2T(k)k=1 算法设计与分析7直接递归中有大量重复计算n直接递归中有大量重复计算，如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图中红框标出的都是重复计算。算法设计与分析8消除重复的计算n要消除重复计算，可在在计算过程中保存已解决的子问题的答案。这样，每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免重复计算。n计算方式可依据递归式自底向上地进行。n注意到在此问题中，不同的有序对(i,j)就对应不同的子问题，因此不同的子问题个数个数最多只有Cn2+n=(n2)个。n这样便可以得到多项式时间的算法。算法设计与分析9自底向上的计算n例如对于A1A2A3A4，依据递归式以自底向上的方式计算出各个子问题，其过程如下：m11m22m33m44m12m23m34m13m24m24其中mii=0mii+1=pi1pipi+1mij=minikj mik+mk+1j+pi1pkpj例如：m13=min m11+m23+p0p1p3m12+m33+p0p2p3算法设计与分析10消除重复的矩阵连乘算法nVoid MatrixChain(int p,int n,int*m,int*s)n for(int i=1;i=n;i+)mii=0;n /将对角线元素赋值为零，即单个矩阵计算量为0n for(int r=2;r=n;r+)n for(int i=1;i=n r+1;i+)n int j=i+r 1;n(5)mij=mi+1j+pi1*pi*pj;n /计算Ai,j=Ai:i Ai+1:jn sij=i;/记下断点in(7)for(int k=i+1;k j;k+)n int t=mik+mk+1j+pi1*pk*pj;n /对ikj,逐个计算Ai,j=Ai:k Ak+1:jn if(t mij)mij=t;sij=k;n /记下较小的mij及相应的断点k n第(5)步与第(7)步能否合在一起?能。此处分开是为了给mij赋初值。算法设计与分析11MatrixChain的运行举例 设要计算矩阵连乘积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的最小计算量以及相应的断点。123456 1 2 3 4 5 6mij1234561 2 3 4 5 6sijMatrixChain将如下面红色箭头所示的过程逐个计算子问题Ai:j：执行for(int i=1;i=n;i+)mii=0后将对角线元素全部置零，即子问题Aii=0。000000当r=2，执行第(5)句完成了相邻矩阵Aii+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=600060002执行第(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)句计算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:3 A4:6；由s13=1可知A1:3的最优计算次序为A1:1 A2:3；由s46=5可知A4:6的最优计算次序为A4:5 A6:6；因此最优计算次序为：(A1(A2A3)(A4A5)A6)。算法设计与分析12MatrixChain的时间复杂性n算法MatrixChain的主要计算取决于程序中对r、i和k的三重循环。循环体内的计算量为O(1)，1 r、i、kn，三重循环的总次数为O(n3)。因此该算法时间复杂性的上界为O(n3)，比直接递归算法要有效得多。算法使用空间显然为O(n2)。n这种算法称为动态规划。算法设计与分析13动态规划的基本思想n将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。n这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。n在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。算法设计与分析14动态规划的基本要素n最优子结构：问题的最优解是由其子问题的最优解所构成的。n重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。算法设计与分析15动态规划的基本方法n动态规划通常可以按以下几个步骤进行：n(1)找出最优解的性质，并刻画其结构特征；n(2)递归地定义最优值；n(3)以自底向上的方式计算出各子结构的最优值并添入表格中保存；n(4)根据计算最优值时得到的信息，构造最优解。n步骤13是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。算法设计与分析16动态规划的备忘录方法n动态规划中采用自底向上的方式。但是在递归定义中往往是自上而下的描述。备忘录方法就采用与递归定义一致的自上而下的方式。n备忘录方法同样用表格来保存已解子问题的信息。每个子问题初始化时都标记为尚未求解。在递归求解过程中，对每个待解子问题，先查看它是否已求解。若未求解，则计算其解并填表保存。若已求解，则查表取出相应的结果。n备忘录方法同样避免了子问题的重复计算，因而和动态规划算法具有同样效率。算法设计与分析17凸多边形最优三角剖分n凸多边形的三角剖分是将一个凸多边形分割成互不相交的三角形的弦的集合T。n下面是一个凸7边形的2个不同的三角剖分：v0v1v2v3v4v5v6v0v1v2v3v4v5v6n在凸多边形的一个三角剖分T中，各弦互不相交，且T已达到最大，即任何一条不在T中的弦必与T中某弦相交。n在有n个顶点的凸多边形的中三角剖分中，恰有n3条弦和n2个三角形。n凸多边形的最优三角剖分问题：给定凸多边形P=v0,v1,vn1，以及定义在由凸多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的一个三角剖分，使得该剖分中诸三角形上权之和为最小。n可定义三角形上各种各样的权函数w。n例如w(vivjvk)=|vivj|+|vjvk|+|vkvi|，其中|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。算法设计与分析18三角剖分与矩阵连乘积同构n三角剖分问题和矩阵连乘积问题都对应于一个完全二叉树，也称为表达式的语法树。0123A1A44A2A3A5A6(A1(A2A3)(A4(A5A6)所对应的二叉树v1v0v2v3v4v5v6012A13A2A3A44A5A6凸多边形v0v1v2v3v4v5v6一个三角剖分所对应的二叉树nn个矩阵连乘积计算顺序同构于n个叶子的完全二叉树，凸(n+1)边形三角剖分同构于n个叶子的完全二叉树，所以n个矩阵连乘积的计算顺序问题同构于凸(n+1)边形的三角剖分问题。n事实上，矩阵连乘积最优计算顺序问题相当于是凸多边形最优三角剖分问题中一种特殊定义的权函数的情形。算法设计与分析19最优子结构性质n能应用动态规划求解的问题应具有最优子结构性质。凸多边形最优三角剖分问题具有最优子结构性质。n事实上，若凸(n+1)边形P=v0,v1,vn的一个最优三角剖分T包含了三角形v0vkvn，1kn，则T的权为三角形v0vkvn，多边形v0,v1,vk 和多边形vk,vk+1,vn的权之和。显然这两个子多边形的三角剖分也是最优的。n因为，其中若有一个子多边形的三角剖分不是最优的将导致T不是最优三角剖分的矛盾。算法设计与分析20最优三角剖分的递归结构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+tk+1j+w(vi1vkvj)ikj与矩阵连乘积问题相对比：mij=minmik+mk+1j+pi1pkpjikjn显然，矩阵连乘积的最优计算顺序与凸多边形最优三角剖分具有完全相同的递归结构。算法设计与分析21最优三角剖分的算法n由于凸多边形最优三角剖分与矩阵连乘积的最优计算顺序具有完全相同的递归结构，其区别仅在于权函数的不同，所以只需要修改求矩阵连乘积的最优计算顺序的算法中的权函数计算便可得到凸多边形最优三角剖分的算法。n显然该算法的时间复杂性也是O(n3)。nVoid MinWeightTriangulation(int n,Type*t,int*s)n for(int i=1;i=n;i+)tii=0;n for(int r=2;r=n;r+)n for(int i=1;i=n r+1;i+)n int j=i+r 1;n tij=ti+1j+w(i1,i,j);n sij=i;n for(int k=i+1;k j;k+)n int u=tik+tk+1j+w(i1,k,j);n if(u tij)tij=u;sij=k;n/程序中红色的部分为改动的地方算法设计与分析22多边形游戏n有一个n边形，每个顶点被赋予一整数值，每条边上被赋予一个运算符“+”或“*”。n游戏的第1步，将一条边删去；n随后的n1步按以下方式操作：n(1)选择一条边E及其所连接的两个顶点v1和v2；n(2)用一个新顶点取代边E以及顶点v1和v2，赋予新顶点的值为顶点v1和v2的值通过边E上的运算所得到的值。n最后所有的边被删去，所剩顶点的值即为得分。算法设计与分析23多边形游戏的表达n设所有的边依次从1到n编号，按顺时针序列为op1,v1,op2,v2,opn,vn 其中opi为边i上的运算符，vi顶点i上的值。n将多边形中始于顶点i(1in)，长度为j 的顺时针链vi,opi+1,vi+j1表示为p(i,j)。n若链p(i,j)最后一次合并在opi+s(1sj1)处发生，则被分割为两个子链p(i,s)和p(i+s,js)算法设计与分析24多边形游戏的最优子结构性质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)应该取最大值，n若p(i,j)的最后合并的边opi+s=“*”，子链p(i,s)和p(i+s,js)是否仍然取最大值呢？不见得！算法设计与分析25多边形游戏的最优子结构分析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=“*”，由于vi可取负整数，所以 minac,ad,bc,bdmmaxac,ad,bc,bd。n即主链最小、最大值亦来自子链最小、最大值。算法设计与分析26多边形游戏的递归求解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=minac,ad,bc,bd mi,j,1=maxac,ad,bc,bd 算法设计与分析27多边形游戏的递归求解n令p(i,j)在opi+s断开的最大值和最小值分别为maxf(i,j,s)和minf(i,j,s)，综合上面的讨论则minf(i,j,s)=a+c opi+s=“+”minac,ad,bc,bd opi+s=“*”maxf(i,j,s)=b+d opi+s=“+”maxac,ad,bc,bd opi+s=“*”n由于p(i,j)的最优断开位置s有1sj1的j1中情况，于是便可得到求解多边形游戏的递归式：算法设计与分析28求解多边形游戏的递归式n由于多边形是封闭的，当i+sn时，顶点i+s实际编号应为(i+s)mod n。n多边形游戏的最大得分即为mi,n,1。mi,j,0=minminf(i,j,s),1i,jn 1sj mi,j,1=maxmaxf(i,j,s),1i,jn 1sj初始边界值为：mi,1,0=mi,1,1=vi,1in,j=1算法设计与分析29多边形游戏的动态规划算法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)。算法设计与分析30DNA序列的相似性n将序列A、B表示为对偶(a,b)的序列。其中若：n1、aA和bB称为替换，a=b称为匹配，否则称为不匹配，其得分为(a,b)；n2、aA，b是空位为删除空白；n3、a是空位，bB为插入空白；n对于长度为k的空位，其得分为(q+k r)。n这里，参数(a,b)、q和r由用户确定。n两个序列A、B的相似性为所有这样的对偶序列中最高的得分。算法设计与分析31DNA序列的相似性n若给定两个DNA序列：AGCTACGTACACTACC AGCTATCGTACTAGCn下面是其一个相似性序列：AGCTACGTACACTACC AGCTATCGTAC TAGCn其中有13个匹配、1个不匹配、一个长度为1的插入空白和一个长度为2的删除空白。n若：a=b时 (a,b)=10；a b时(a,b)=20；q=40；r=2。该相似性序列的得分为 10*13 20 (40+2)(40+2*2)=24算法设计与分析32递归求序列相似性n设A=a1a2am，B=b1b2bn。令S(m,n)为A和B的相似性，即各种对偶序列最大的得分。n为了采用递归方法来求解此问题，我们从序列尾部来考虑，那么有三种方案：n尾部用替换，即最后一个对偶为(am,bn)；n尾部用删除空白，即最后一个对偶为(am,)；n尾部用插入空白，即最后一个对偶为(,bn)。n令S(m,n)、D(m,n)和I(m,n)分别为三种方案的得分，则其相似性应为三种方案的最大得分。算法设计与分析33递归求序列相似性S(m,n)=S(m 1,n 1)+(am,bn)。n 若用方案，即尾部用替换，则 D(m,n)=S(m 1,n)q r 或者，D(m,n)=D(m 1,n)r n 若用方案，即尾部用删除空白，则 I(m,n)=S(m,n 1)q r 或者，I(m,n)=I(m,n 1)r n 若用方案，即尾部用插入空白，则算法设计与分析34递归求序列相似性n现在考虑非递归分支：S(0,0)=0、S(m,0)=D(m,0)、S(0,n)=I(0,n)。n 对方案，有D(m,0)=D(m 1,0)r、D(0,n)=S(0,n)q。n 对方案，有I(m,0)=S(m,0)q、I(0,n)=S(0,n 1)q。n 对方案，有算法设计与分析35递归求序列相似性nS(m,n)=0 m=0,n=0 D(m,0)for n 0I(0,n)for m 0maxS(m1,n1)+(am,bn),D(m,n),I(m,n)nD(m,n)=S(0,n)q for n 0 D(m 1,0)r for m 0maxS(m1,n)q-r,D(m 1,n)rnI(m,n)=S(m,0)q for m 0 I(0,n 1)r for n 0maxS(m,n1)q-r,I(m 1,n)r算法设计与分析36动态规划求序列相似性n如果用递归算法求序列的相似性，其时间复杂性显然是指数级的。n考虑采用动态规划法。为此，需要n用矩阵S0:m,0:n、D0:m,0:n和I0:m,0:n来分别记载对应于子序列Ai和Bj的得分S(i,j)、D(i,j)和I(i,j)，0 i m，0 j n。n从(0,0)开始逐个计算S(i,j)、D(i,j)和I(i,j)并将结果记入Si,j、Di,j和Ii,j。n必要时，是用辅助矩阵记载每步的方案。算法设计与分析37动态规划法的递归式nS(i,j)=0 m=0,n=0 D(i,0)for j 0I(0,j)for i 0maxS(i1,j1)+(ai,bj),D(i,j),I(i,j)nD(i,j)=S(0,j)q for j 0 D(i 1,0)r for i 0maxS(i1,j)q-r,D(i 1,j)rnI(i,j)=S(i,0)q for i 0 I(0,j 1)r for j 0maxS(i,j1)q-r,I(i 1,j)r算法设计与分析38动态规划法求序列相似性nAlignment(int m,int n,char Am,char Bn)n int Smn,Dmn,Imn;n n 初始化；n 从(i,j)=(1,1)到(m,n)逐个计算并填写 Di,j、Ii,j和Si,j；n 输出S(m,n);n算法设计与分析39递归式中的数据依赖n由递归式可知S(i,j)依赖于S(i1,j1)、D(i,j)和I(i,j)。S(i,j)=0 m=0,n=0 D(i,0)for j 0I(0,j)for i 0maxS(i1,j1)+(ai,bj),D(i,j),I(i,j)S(i1,j1)D(i,j)I(i,j)S(i,j)n由递归式可知D(i,j)依赖于S(i 1,j)、D(i 1,j)。D(i,j)=S(0,j)q for j 0 D(i 1,0)r for i 0maxS(i1,j)q-r,D(i 1,j)rS(i1,j)D(i1,j)D(i,j)n由递归式可知D(i,j)依赖于S(i 1,j)、D(i 1,j)。I(i,j)=S(i,0)q for i 0I(0,j 1)r for j 0 maxS(i,j 1)q-r,I(i 1,j)rS(i,j1)I(i1,j)I(i,j)n递归式中的数据依赖关系如下面的三个图所示。在用循环程序实现这些递归式时，必须要保证在计算的过程中能够满足这里的数据依赖关系。算法设计与分析40递归式中的数据依赖S(i1,j1)D(i,j)I(i,j)S(i,j)S(i1,j)D(i1,j)D(i,j)S(i,j1)I(i1,j)I(i,j)0jiSm,n0jiDm,n0jiIm,nSi,jDi,jIi,jn由数据依赖关系可知，：在i和j方向上按Di,j、Ii,j、Si,j逐个进行是可行的计算。算法设计与分析41初始化的工作nInitialization()nS00=0;D00=q;I00=qnfor(int i=1;i=m;i+)n Di0=Di 10 r;Si0=Di0;n Ii0=Si0 q;nfor(int j=1;j=n;j+)n I0j=I0j 1 r;S0j=I0j;n D0j=S0j q;n算法设计与分析42Si,j、Di,j和Ii,j的计算nwhile(i=m&j=n)do n for(int t=j;t=n;t+)n Dit=maxDi1t r,Si1t q r;n Iit=maxIit1 r,Sit1 q r;n Sit=maxSi 1t1+(ai,bt),Dit,Iit;n for(int t=i;t=m;t+)nDit=maxDi1t r,Si1t q r;n Iit=maxIit1 r,Sit1 q r;n Sit=maxSi 1t1+(ai,bt),Dit,Iit;n i+;j+算法设计与分析43动态规划总结n与分治法相比，相同之处是也将原问题分解为若干子问题，再递归求解；不同之处是所分解的子问题彼此并不独立，而是互有重叠。n基本思想是造表记录已解的子问题，再次遇到时仅查表即可，避免了重复计算，提高效率。n通常用于求解具有最优性质的问题，而且其子问题也具有最优性质(最优子结构性质)。n实现方法通常为自底向上的递归形式，但也可以采用自上而下的形式(备忘录方法)。