第四章动态规划法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,算法设计与分析,*,算法设计与分析,1,第四章,动态规划,算法设计与分析,2,矩阵连乘问题,给定,n,个矩阵：,A,1, A,2, , A,n,，其中,A,i,与,A,i+1,是可乘的。确定一种连乘的顺序，使得矩阵连乘的计算量为最小。,设,A,和,B,分别是,pq,和,qr,的两个矩阵，则乘积,C=AB,为,pr,的矩阵，计算量为,pqr,次数乘。,但是对于多于,2,个以上的矩阵连乘，连乘的顺序却非常重要，因为不同的顺序的总计算量将会有很大的差别。,算法设计与分析,3,不同计算顺序的差别,设矩阵,A,1, A,2,和,A,3,分别为,10100, 1005,和,550,的矩阵，现要计算,A,1,A,2,A,3,。,若按,(A,1,A,2,)A,3,),来计算，则需要的数乘次数为,101005 + 10550 = 7500,若按,(A,1,(A,2,A,3,),来计算，则需要的数乘次数为,100 5 50+ 1010050 = 75000,后一种计算顺序的计算量竟是前者的,10,倍！,所以，求多个矩阵的连乘积时，计算的结合顺序是十分重要的。,算法设计与分析,4,不同计算顺序的数量,设,n,个矩阵的连乘积有,P(n),个不同的计算顺序。,先在第,k,个和第,k+1,个矩阵之间将原矩阵序列分成两个矩阵子序列，,k=1,，,，,n,；再分别对两个子序列完全加括号，最后对结果加括号，便得到原序列的一种完全加括号方式。,由此可得出关于,P(n),的递归式：,P(n) =,n = 1,n1,P(k) P(nk) n,1,k=1,解此递归方程可得,P(n) = C(n1),，其中,C(n) =,1,n+1,2n,n,=,(4,n,/n,3/2,),所以,P(n),随,n,的增长呈指数增长。因而穷举搜索法不是有效的算法。,算法设计与分析,5,分解最优解的结构,将矩阵连乘积,A,i,A,i+1,A,j,记为,Ai: j,。,若,A1: n,的一个最优解是在矩阵,A,k,和,A,k+1,处断开的，即,A1: n = (A1: k Ak+1: n),，则,A1: k,和,Ak+1: n,也分别是最优解。,事实上，若,A1: k,的一个计算次序所需计算量更少的话，则用此计算次序替换原来的次序，则得到,A1: n,一个更少的计算量，这是一个矛盾。同理,Ak+1: n,也是最优解。,最优子结构性质：最优解的子结构也最优的。,算法设计与分析,6,建立递归关系,令,mij , 1i, jn,，为计算,Ai, j,的最少数乘次数，则原问题为,m1n,。,当,i = j,时，,Ai, j,为单一矩阵，,mij = 0,；,当,i,j,时，利用最优子结构性质有：,mij =,minmik + mk+1j + p,i1,p,k,p,j,ik,j,其中矩阵,A,i,，,1in,，的维数为,p,i1,p,i,。,根据此递归式就可以直接用递归程序来实现。,算法设计与分析,7,直接递归的时间复杂性,根据前面的递归式不难得出的时间复杂性为,n1,1 + (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,可用数学归纳法证明,T(n)2,n1,=,(2,n,),。,直接递归算法的时间复杂性随,n,的指数增长。,n1,= n + 2T(k),k=1,算法设计与分析,8,直接递归中有大量重复计算,直接递归中有大量重复计算，如,A1: 4,计算中：,1: 4,1: 1,2: 4,1: 2,3: 4,1: 3,4: 4,2: 2,3: 4,2: 3,4: 4,1:1,2: 2,3: 3,4: 4,1: 1,2: 3,1: 2,3: 3,3: 3,4: 4,2: 2,3: 3,2: 2,3: 3,1: 1,2: 2,图中红框标出的都是重复计算。,算法设计与分析,9,消除重复的计算,要消除重复计算，可在在计算过程中保存已解决的子问题的答案。这样，每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免重复计算。,计算方式可依据递归式自底向上地进行。,注意到在此问题中，,不同的有序对,(i, j),就对应不同的子问题，因此,不同的子问题个数个数最多只有,C,n,2,+ n =,(,n,2,),个。,这样便可以得到多项式时间的算法。,算法设计与分析,10,自底向上的计算,例如对于,A,1,A,2,A,3,A,4,，,依据递归式以自底向上的方式计算出各个子问题，其过程如下：,m11,m22,m33,m44,m12,m23,m34,m13,m24,m24,其中,mii = 0,mii+1 = p,i1,p,i,p,i+1,mij = min,ik,j,mik+mk+1j+p,i1,p,k,p,j,例如：,m13 =,min,m11+m23+p,0,p,1,p,3,m12+m33+p,0,p,2,p,3,算法设计与分析,11,消除重复的矩阵连乘算法,Void MatrixChain(int p, int n, int *m, int *s), for (int i = 1; i = n; i+) mii = 0;,/,将对角线元素赋值为零，即单个矩阵计算量为,0,for (int r = 2; r = n; r+),for (int i = 1; i = n r +1; i+) ,int j = i + r 1;,(5),mij = mi+1j + pi1*pi*pj,;,/,计算,Ai, j = Ai: i Ai+1: j,sij = i;,/,记下断点,i,(7),for (int k = i + 1; k j; k+) ,int t = mik + mk+1j + pi1*pk*pj,;,/,对,ikj,逐个计算,Ai, j = Ai: k Ak+1: j,if (t mij) mij = t; sij = k;,/,记下较小的,mij,及相应的断点,k,第,(5),步与第,(7),步,能否合在一起,?,能。此处分开是为,了给,mij,赋初值。,算法设计与分析,12,MatrixChain,的运行举例,设要计算矩阵连乘积,A,1,A,2,A,3,A,4,A,5,A,6,，其维数分别为,3535, 3515, 155, 510, 1020, 2025,即,p,0,=35, p,1,=35, p,2,=15, p,3,=5, p,4,=10, p,5,=20, p,6,=25,。,MatrixChain,用矩阵,mij, sij,存放子问题,Ai: j,的最小计算量以及相应的断点。,1,2,3,4,5,6,1 2 3 4 5 6,mij,1,2,3,4,5,6,1 2 3 4 5 6,sij,MatrixChain,将如下面红色箭头所示的过程逐个计算子问题,Ai: j,：,执行,for (int i = 1; i = n; i+) mii = 0,后将对角线元素全部置零，即子问题,Aii = 0,。,0,0,0,0,0,0,当,r=2,，执行,第,(5),句,完成了相邻矩阵,Aii+1=pi1*pi*pj,的计算，并在,sij,中添入了相应的断点。其中的,第,(7),句,因为,j = i+1(k=i+1),而被跳过去了，实际并没有执行。,15750,2625,750,1000,5000,1,2,3,4,5,当,r=3,，,i=1,时，执行,第,(5),句,计算,A1:12:3,，,m13 = m23 + p0*p1*p3 = 2625 +30*35*5 = 7875,7875,1,执行,第,(7),句,计算,A1:23:3,，,t = m12 + m33 + p0*p2*p3 = 15750+0+35*15*5 = 18375,7875,，所以,m13,不变，断点仍为,1,。,当,r=3,，,i=2,时，执行,第,(5),句,计算,A2:23:4,，,m24 = m34 + p1*p2*p4 = 750 +35*15*10 = 6000,6000,2,执行,第,(7),句,计算,A2:34:4,，,t = m23+m44+ p1*p3*p4 = 2625+0+35*5*10 = 4375,6000,，所以,m24,改为,4375,，断点改为,3,。,4375,3,当,r=3,，,i=3,时，执行,第,(5),句,计算,A3:34:5,，,m35 = m45 + p2*p3*p5 = 1000 +15*5*20 = 2500,2500,3,执行,第,(7),句,计算,A3:45:5,，,t = m34+m55+ p2*p4*p5 = 750+0+15*10*20 = 3750,2500,，所以,m35,仍为,2500,，断点仍为,3,。,当,r=3,，,i=4,时，执行,第,(5),句,计算,A4:45:6,，,m46 = m56 + p3*p4*p6 = 5000 +5*10*25 = 6250,6250,4,执行,第,(7),句,计算,A4:56:6,，,t = m45+m66+ p3*p5*p6 = 1000+0+5*20*25 = 3500,6250,，所以,m46,改为,3500,，断点改为,5,。,3500,5,类似的，当,r=4,、,5,、,6,时，可以计算出相应的,mij,及其相应的断点,sij,，如下图中所示：,9375,3,7125,3,5375,3,11875,3,10500,3,15125,3,由,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,；因此最优计算次序为：,(,A,1,(,A,2,A,3,)(,A,4,A,5,),A,6,),。,算法设计与分析,13,MatrixChain,的时间复杂性,算法,MatrixChain,的主要计算取决于程序中对,r,、,i,和,k,的三重循环。循环体内的计算量为,O(1),，,1 r,、,i,、,kn,，三重循环的总次数为,O(n,3,),。因此该算法时间复杂性的上界为,O(n,3,),，比直接递归算法要有效得多。算法使用空间显然为,O(n,2,),。,这种算法称为动态规划。,算法设计与分析,14,动态规划的基本思想,将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。,这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。,在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。,算法设计与分析,15,动态规划的基本要素,最优子结构：问题的最优解是由其子问题的最优解所构成的。,重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。,最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。,因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。,算法设计与分析,16,动态规划的基本方法,动态规划通常可以按以下几个步骤进行：,(1),找出最优解的性质，并刻画其结构特征；,(2),递归地定义最优值；,(3),以自底向上的方式计算出各子结构的最优值并添入表格中保存；,(4),根据计算最优值时得到的信息，构造最优解。,步骤,13,是动态规划算法的基本步骤。若需要最优解，则必须执行第,4,步，,为此还需要在第,3,步中记录构造最优解所必需的信息,。,算法设计与分析,17,动态规划的备忘录方法,动态规划中采用自底向上的方式。但是在递归定义中往往是自上而下的描述。备忘录方法就采用与递归定义一致的自上而下的方式。,备忘录方法同样用表格来保存已解子问题的信息。每个子问题初始化时都标记为尚未求解。在递归求解过程中，对每个待解子问题，先查看它是否已求解。若未求解，则计算其解并填表保存。若已求解，则查表取出相应的结果。,备忘录方法同样避免了子问题的重复计算，因而和动态规划算法具有同样效率。,算法设计与分析,18,凸多边形最优三角剖分,凸多边形的三角剖分是将一个凸多边形分割成互不相交的三角形的弦的集合,T,。,下面是一个凸,7,边形的,2,个不同的三角剖分：,v,0,v,1,v,2,v,3,v,4,v,5,v,6,v,0,v,1,v,2,v,3,v,4,v,5,v,6,在凸多边形的一个三角剖分,T,中，各弦互不相交，且,T,已达到最大，即任何一条不在,T,中的弦必与,T,中某弦相交。,在有,n,个顶点的凸多边形的中三角剖分中，恰有,n3,条弦和,n2,个三角形。,凸多边形的最优三角剖分问题：给定凸多边形,P=v,0, v,1, v,n1,，以及定义在由凸多边形的边和弦组成的三角形上的权函数,w,。要求确定该凸多边形的一个三角剖分，使得该剖分中诸三角形上权之和为最小。,可定义三角形上各种各样的权函数,w,。,例如,w(v,i,v,j,v,k,) = |v,i,v,j,| + |v,j,v,k,| + |v,k,v,i,|,，其中,|v,i,v,j,|,是点,v,i,到,v,j,的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。,算法设计与分析,19,三角剖分与矩阵连乘积同构,三角剖分问题和矩阵连乘积问题都对应于一个完全二叉树，也称为表达式的语法树。,0,1,2,3,A,1,A,4,4,A,2,A,3,A,5,A,6,(A,1,(A,2,A,3,)(A,4,(A,5,A,6,),所对应的二叉树,v,1,v,0,v,2,v,3,v,4,v,5,v,6,0,1,2,A,1,3,A,2,A,3,A,4,4,A,5,A,6,凸多边形,v,0,v,1,v,2,v,3,v,4,v,5,v,6,一个三角剖分所对应的二叉树,n,个矩阵连乘积计算顺序同构于,n,个叶子的完全二叉树，凸,(n+1),边形三角剖分同构于,n,个叶子的完全二叉树，所以,n,个矩阵连乘积的计算顺序问题同构于凸,(n+1),边形的三角剖分问题。,事实上，矩阵连乘积最优计算顺序问题相当于是凸多边形最优三角剖分问题中一种特殊定义的权函数的情形。,算法设计与分析,20,最优子结构性质,能应用动态规划求解的问题应具有最优子结构性质。凸多边形最优三角剖分问题具有最优子结构性质。,事实上，若,凸,(n+1),边形,P=v,0, v,1, v,n,的一个最优三角剖分,T,包含了三角形,v,0,v,k,v,n,，,1k,n,，则,T,的权为三角形,v,0,v,k,v,n,，多边形,v,0, v,1, v,k,和多边形,v,k, v,k+1, v,n,的权之和。显然这两个子多边形的三角剖分也是最优的。,因为，其中若有一个子多边形的三角剖分不是最优的将导致,T,不是最优三角剖分的矛盾。,算法设计与分析,21,最优三角剖分的递归结构,定义,tij, 1ijn,为子多边形,v,i1, v,i, v,j,的最优三角剖分所对应的权函数值，并为方便起见，设退化的多边形,v,i1, v,i,的权值为,0,。,于是凸,(n+1),边形的最优三角剖分为,t1n,易知，,tij,可递归定义为,当,i = j,时，为退化多边形,v,i1, v,i,，,tij = 0,；,当,i,j,时，利用最优子结构性质有：,tij =,mintik + tk+1j + w(v,i1,v,k,v,j,),ik,j,与矩阵连乘积问题相对比：,mij =,minmik + mk+1j + p,i1,p,k,p,j,ik,j,显然，矩阵连乘积的最优计算顺序与,凸多边形最优三角剖分具有完全相同的递归结构。,算法设计与分析,22,最优三角剖分的算法,由于凸多边形最优三角剖分与矩阵连乘积的最优计算顺序具有完全相同的递归结构，其区别仅在于权函数的不同，所以只需要修改求矩阵连乘积的最优计算顺序的算法中的权函数计算便可得到凸多边形最优三角剖分的算法。,显然该算法的时间复杂性也是,O(n3),。,Void MinWeightTriangulation(int n, Type *,t, int *s), for (int i = 1; i = n; i+) tii = 0;,for (int r = 2; r = n; r+),for (int i = 1; i = n r +1; i+) ,int j = i + r 1;,t,ij =,t,i+1j +,w(i1, i, j),;,sij = i;,for (int k = i + 1; k j; k+) ,int,u,=,t,ik +,t,k+1j +,w(i1, k, j),;,if (,u,t,ij) ,t,ij =,u,; sij = k;,/,程序中红色的部分为改动的地方,算法设计与分析,23,多边形游戏,有一个,n,边形，每个顶点被赋予一整数值，每条边上被赋予一个运算符“,+”,或“*”。,游戏的第,1,步，将一条边删去；,随后的,n1,步按以下方式操作：,(1),选择一条边,E,及其所连接的两个顶点,v1,和,v2,；,(2),用一个新顶点取代边,E,以及顶点,v1,和,v2,，赋予新顶点的值为顶点,v1,和,v2,的值通过,边,E,上的运算所得到的值。,最后所有的边被删去，所剩顶点的值即为得分。,算法设计与分析,24,多边形游戏的表达,设所有的边依次从,1,到,n,编号，按顺时针序列为,op1, v1, op2, v2, , opn, vn,其中,opi,为边,i,上的运算符，,vi,顶点,i,上的值。,将多边形中始于顶点,i (1in),，长度为,j,的顺时针链,vi, opi+1, , vi+j1,表示为,p(i, j),。,若链,p(i, j),最后一次合并在,opi+s(1sj1),处发生，则被分割为两个子链,p(i, s),和,p(i+s, js),算法设计与分析,25,多边形游戏的最优子结构性质,若链,p(i, j),取最优值的最后一次合并是在,opi+s,处发生的，则子链,p(i, s),和,p(i+s, js),也是最优。,因为若子链,p(i, s),和,p(i+s, js),不是最优的，则可推出链,p(i, j),也不是最优的矛盾。所以多边形游戏具有最优子结构性质。,但是这里的最优子结构要稍微地复杂一点。,若,p(i, j),的最后合并的边,opi+s =“+”,，子链,p(i, s),和,p(i+s, s),应该取最大值，,若,p(i, j),的最后合并的边,opi+s =“*”,，子链,p(i, s),和,p(i+s, js),是否仍然取最大值呢？,不见得！,算法设计与分析,26,多边形游戏的最优子结构分析,设,m1,是对子链,p(i, s),的任意合并方式得到的值，,a,和,b,是其最小值和最大值，,m2,是对子链,p(i+s, js),的任意合并方式得到的值，,c,和,d,分别是最小值和最大值，即,am1b,，,cm2d,。,若,opi+s =“+”,，则,a+cmb+d,。可见,p(i, s),的最小、最大值分别对应于子链的最小、最大值。,若,opi+s =“*”,，由于,vi,可取负整数，所以,minac, ad, bc, bdmmaxac, ad, bc, bd,。,即主链最小、最大值亦来自子链最小、最大值。,算法设计与分析,27,多边形游戏的递归求解,由前面的分析可知，为了求链合并的最大值，必须同时求子链合并的最大值和最小值。因此整个计算过程中应同时计算最大值和最小值。,设链,p(i, j),合并的最大、最小值分别是,mi, j, 0,和,mi, j, 1,，最优合并处是在,opi+s,，且长度小于,j,的子链的最大、最小值均已算出，且记：,a = mi, i+s, 0, b = mi, i+s, 1, c = mi+s, js, 0,，,d = mi+s, js, 1,，则,当,opi+s = “+”,时，,mi, j, 0 = a + c,，,mi, j, 1 = b + d,当,opi+s = “*”,时，,mi, j, 0 = minac, ad, bc, bd mi, j, 1 = maxac, ad, bc, bd,算法设计与分析,28,多边形游戏的递归求解,令,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 = “*”,由于,p(i, j),的最优断开位置,s,有,1sj1,的,j1,中情况，于是便可得到求解多边形游戏的递归式：,算法设计与分析,29,求解多边形游戏的递归式,由于多边形是封闭的，当,i+s,n,时，顶点,i+s,实际编号应为,(i+s)mod 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,算法设计与分析,30,多边形游戏的动态规划算法,依据上述讨论以及所得的递归式，不难写出多边形游戏动态规划算法。请同学们自己编写。,算法的主程序为,Poly_Max,，它包含了一个子程序,MIN_MAX,。子程序,MIN_MAX,负责对确定,s,的,minf (i, j, s),和,maxf (i, j, s),的计算。而对任意链的最大值,mi, j, 1,和最小值,mi, j, 0,的计算则是在主程序,Poly_Max,中进行的。,算法的时间复杂性显然仍为,O(n,3,),。,算法设计与分析,31,DNA,序列的相似性,将序列,A,、,B,表示,为对偶,(a, b),的序列。其中若：,1,、,a,A,和,b,B,称为替换，,a = b,称为匹配，否则称为不匹配，其得分为,(a, b),；,2,、,a,A,，,b,是空位为删除空白；,3,、,a,是空位，,b,B,为插入空白；,对于长度为,k,的空位，其得分为,(q + k, r),。,这里，参数,(a, b),、,q,和,r,由用户确定。,两个序列,A,、,B,的相似性为所有这样的对偶序列中最高的得分。,算法设计与分析,32,DNA,序列的相似性,若给定两个,DNA,序列：,AGCTACGTACACTACC,AGCTATCGTACTAGC,下面是其一个相似性序列：,AGCTACGTACACTACC,AGCTATCGTAC TAGC,其中有,13,个匹配、,1,个不匹配、一个长度为,1,的插入空白和一个长度为,2,的删除空白。,若：,a = b,时,(a, b) = 10,；,a,b,时,(a, b) = 20,；,q = 40,；,r = 2,。该相似性序列的得分为,10 * 13 20 (40 + 2) (40 + 2 * 2) = 24,算法设计与分析,33,递归求序列相似性,设,A = a,1,a,2,a,m,，,B = b,1,b,2,b,n,。令,S(m, n),为,A,和,B,的相似性，即各种对偶序列最大的得分。,为了采用递归方法来求解此问题，我们从序列尾部来考虑，那么有三种方案：,尾部用替换，即最后一个对偶为,(a,m, b,n,),；,尾部用删除空白，即最后一个对偶为,(a,m, ),；,尾部用插入空白，即最后一个对偶为,(, b,n,),。,令,S(m, n),、,D(m, n),和,I(m, n),分别为三种方案的得分，则,其相似性应为三种方案的最大得分。,算法设计与分析,34,递归求序列相似性,S(m, n) = S(m 1, n 1) +,(a,m, b,n,),。,若用方案，即尾部用替换，则,D(m, n) = S(m 1, n) q r,或者，,D(m, n) = D(m 1, n) r,若用方案，即尾部用删除空白，则,I(m, n) = S(m, n 1) q r,或者，,I(m, n) = I(m, n 1) r,若用方案，即尾部用插入空白，则,算法设计与分析,35,递归求序列相似性,现在考虑非递归分支：,S(0, 0) = 0,、,S(m, 0) = D(m, 0),、,S(0, n) = I(0, n),。,对方案，有,D(m, 0) = D(m 1, 0) r,、,D(0, n) = S(0, n) q,。,对方案，有,I(m, 0) = S(m, 0) q,、,I(0, n) = S(0, n 1) q,。,对方案，有,算法设计与分析,36,递归求序列相似性,S(m,n) =,0 m = 0, n = 0,D(m, 0) for n, 0,I(0, n) for m, 0,maxS(m1,n1)+,(a,m,b,n,), D(m,n), I(m,n),D(m,n) =,S(0, n) q for n,0,D(m 1, 0) r for m, 0,maxS(m1,n) q - r, D(m 1,n) r,I(m,n) =,S(m, 0) q for m,0,I(0, n 1) r for n, 0,maxS(m,n1) q - r, I(m 1,n) r,算法设计与分析,37,动态规划求序列相似性,如果用递归算法求序列的相似性，其时间复杂性显然是指数级的。,考虑采用动态规划法。为此，需要,用矩阵,S0:m, 0:n,、,D0:m, 0:n,和,I0:m, 0: n,来分别记载对应于子序列,A,i,和,B,j,的得分,S(i, j),、,D(i, j),和,I(i, j),，,0, i m,，,0 j n,。,从,(0, 0),开始逐个计算,S(i, j),、,D(i, j),和,I(i, j),并将结果记入,Si, j,、,Di, j,和,Ii, j,。,必要时，是用辅助矩阵记载每步的方案。,算法设计与分析,38,动态规划法的递归式,S(i, j) =,0 m = 0, n = 0,D(i, 0) for j, 0,I(0, j) for i, 0,maxS(i1, j1)+,(a,i,b,j,), D(i, j), I(i, j),D(i, j) =,S(0, j) q for j,0,D(i 1, 0) r for i, 0,maxS(i1, j) q - r, D(i 1, j) r,I(i, j) =,S(i, 0) q for i,0,I(0, j 1) r for j, 0,maxS(i, j1) q - r, I(i 1, j) r,算法设计与分析,39,动态规划法求序列相似性,Alignment(int m, int n, char Am, char Bn),int Smn, Dmn, Imn;,初始化；,从,(i, j) = (1, 1),到,(m, n),逐个计算并填写,Di, j,、,Ii, j,和,Si, j,；,输出,S(m, n);,算法设计与分析,40,递归式中的数据依赖,由递归式,可知,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, 0,I(0, j) for i, 0,maxS(i1, j1)+,(a,i,b,j,), D(i, j), I(i, j),S(i1, j1),D(i, j),I(i, j),S(i, j),由递归式,可知,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, 0,maxS(i1, j) q - r, D(i 1, j) r,S(i1, j),D(i1, j),D(i, j),由递归式,可知,D(i, j),依赖于,S(i 1, j),、,D(i 1, j),。,I(i, j) =,S(i, 0) q for i,0,I(0, j 1) r for j, 0,maxS(i, j 1) q - r, I(i 1, j) r,S(i, j1),I(i1, j),I(i, j),递归式中的数据依赖关系如下面的三个图所示。在用循环程序实现这些递归式时，必须要保证在计算的过程中能够满足这里的数据依赖关系。,算法设计与分析,41,递归式中的数据依赖,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),0,j,i,Sm, n,0,j,i,Dm, n,0,j,i,Im, n,Si, j,Di, j,Ii, j,由数据依赖关系可知，：在,i,和,j,方向上按,Di, j,、,Ii, j,、,Si, j,逐个进行是可行的计算。,算法设计与分析,42,初始化的工作,Initialization ( ),S00 = 0; D00 = q; I00 = q,for (int i = 1; i = m; i+),Di0 = Di 10 r; Si0 = Di0;,Ii0 = Si0 q;,for (int j = 1; j = n; j+),I0j = I0j 1 r; S0j = I0j;,D0j = S0j q;,算法设计与分析,43,Si, j,、,Di, j,和,Ii, j,的计算,while (i =m & j = n) do ,for (int t = j; t = n; t+),Dit = maxDi1t r, Si1t q r;,Iit = maxIit1 r, Sit1 q r;,Sit = maxSi 1t1 +,(a,i,b,t,), Dit, Iit;,for (int t = i; t = m; t+),Dit = maxDi1t r, Si1t q r;,Iit = maxIit1 r, Sit1 q r;,Sit = maxSi 1t1 +,(a,i,b,t,), Dit, Iit;,i+; j +,算法设计与分析,44,动态规划总结,与分治法相比，相同之处是也将原问题分解为若干子问题，再递归求解；不同之处是所分解的子问题彼此并不独立，而是互有重叠。,基本思想是造表记录已解的子问题，再次遇到时仅查表即可，避免了重复计算，提高效率。,通常用于求解具有最优性质的问题，而且其子问题也具有最优性质,(,最优子结构性质,),。,实现方法通常为自底向上的递归形式，但也可以采用自上而下的形式,(,备忘录方法,),。,