算法设计与分析课件.pptx

《算法设计与分析课件.pptx》由会员分享，可在线阅读，更多相关《算法设计与分析课件.pptx（141页珍藏版）》请在三一办公上搜索。

1、主要内容介绍,7.1 一般方法和基本要素7.2 最大字段和7.3 每对结点间的最短路径7.4 矩阵连乘问题7.5 最长公共子序列问题7.6最优二叉搜索树,主要内容介绍,7.7 0-1背包问题7.8流水作业调度,引言,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,Those who cannot remember the past are

2、 doomed to repeat it.George Santayana, The life of Reason, Book I: Introduction and Reason in Common Sense (1905),第七章 动态规划,7.1 一般方法1. 多阶段决策问题 多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这决策过程称为多阶段决策过程(multistep decision process) 。 最优化问题：问题的每一阶段可能有多种可供选择的决策，

3、必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。 多阶段决策的最优化问题就是：求能够获得问题最优解的决策序列最优决策序列。,2. 多阶段决策过程的求解策略1）枚举法 穷举可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问题的新方法动态规划。 动态规划(dynamic programming)是运筹学的一个分支，是求解决

4、策过程(decision process)最优化的数学方法。 应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。,3. 最优性原理(Principle of Optimality) 过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。 利用动态规划求解问题的前提 1) 证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题 2) 获

5、得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键。,Divide-and-conquer技术的问题子问题是相互独立的如果子问题不是相互独立的，分治方法将重复计算公共子问题，效率很低优化问题给定一组约束条件和一个代价函数，在解空间中搜索具有最小或最大代价的优化解很多优化问题可分为多个子问题，子问题相互关联，子问题的解被重复使用,Why?,Dynamic Programming特点把原始问题划分成一系列子问题求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间自底向上地计算适用范围一类优化问题：可分为多个相关子问题，子问题的解被重复使用,Wh

6、at?, 牛牛文库文档分享,使用Dynamic Programming的条件Optimal substructure（优化子结构）当一个问题的优化解包含了子问题的优化解时，我们说这个问题具有优化子结构。缩小子问题集合，只需那些优化问题中包含的子问题，减低实现复杂性优化子结构使得我们能自下而上地完成求解过程Subteties（重叠子问题）在问题的求解过程中，很多子问题的解将被多次使用,How?, 牛牛文库文档分享,Dynamic Programming算法的设计步骤分析优化解的结构递归地定义最优解的代价自底向上地计算优化解的代价保存之， 并获取构造最优解的信息根据构造最优解的信息构造优化解,多段

7、图问题多段图G=(V,E)是一个有向图，且具有特性: 结点：结点集V被分成k2个不相交的集合Vi，1ik， 其中V1和Vk分别只有一个结点：s(源结点)和t(汇点)。 段： 每一集合Vi定义图中的一段共k段。 边： 所有的边(u,v)均具有如下性质： 若E，则 若uVi，则uVi1,即该边将是从某段i指向i+1段， 1ik1。 成本：每条边(u,v)均附有成本c(u,v)。 s到t的路径：是一条从第1段的源点s出发，依次经过第2段的某结点v2,i，经第3段的某结点v3,j、最后在第k段的汇点t结束的路径。 该路径的成本是这条路径上边的成本和。 多段图问题：求由s到t的最小成本路径。,7.1.2

8、 多段图问题,7.1.2 多段图问题,1. 问题的描述 在多段图中求从s到t的一条最小成本的路径，可以看 作是在k-2个段作出某种决策的结果。 第i次决策决定Vi+1中的哪个结点在这条路径上，这里 1ik-2； 最优性原理对多段图问题成立,多段图问题的多阶段决策过程：生成从s到t的最小成本路径是在k-2个阶段（除s和t外）进行某种决策的过程：从s开始，第i次决策决定Vi+1(1ik-2)中的哪个结点在从s到t的最短路径上。 最优性原理对多段图问题成立 假设s,v2,v3,vk-1,t是一条由s到t的最短路径。 初始状态：s 初始决策：(s,v2)， v2V2 初始决策产生的状态：v2 则，其余

9、的决策：v3,.,vk-1相对于v2将构成一个最优决策序列最优性原理成立。 反证：若不然，设v2,q3,qk-1,t是一条由v2到t的更短的路径，则s, v2,q3,qk-1,t将是比s,v2,v3,vk-1,t更短的从s到t的路径。与假设矛盾。 故，最优性原理成立,即，是v2 v3,.,vk-1t构成从v2至t的最短路径,4. 最优决策序列的表示 设 S0：问题的初始状态 n次决策：问题需要做n次决策 xi：i阶段的决策值，1in。 设X1=r1,1,r1,2,r1,p1是x1可选决策值的集合，S1,j1是在选择决策值r1,j1之后所产生的状态“初始决策”所产生的状态。 设1,j1是相应于状

10、态S1,j1的最优决策序列。则，相应于S0的最优决策序列就是r1,j11,j1|1j1p1中最优的序列，记为,就一个特定的r1,j1而言,若已经做了k-1次决策，1k-1n，设x1,x2,xk-1的最优决策值是r1,r2,rk-1，所产生的状态依次为S1,S2,Sk-1。 设Xk=rk,1,rk,2,rk,pk是xk可能的决策值的集合，Sk,jk是在选择决策值rk,jk之后所产生的状态, 1jkpk。 k,jk是相应于状态Sk,jk的最优决策序列。则，相应于Sk-1的最优决策序列是 相应于S0的最优决策序列为r1,rk-1，rk, k,就一个特定的rk,jk而言,2. 向前处理策略求解 设 P

11、(i,j)是一条从Vi中的结点j到汇点t的最小成本路径， COST(i,j)是这条路径的成本。 1) 向前递推式 2) 递推过程 第k-1段 c(j,t) E COST(k-1,j) = ,l1,l2,.,lpi+1,t,j,Vi,Vi+1,各递推结果第4段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2 COST(4,11) = c(11,12) = 5第3段 COST(3,6) = min6+COST(4,9),5+COST(4,10) = 7 COST(3,7) = min4+COST(4,9),3+COST(4,10) = 5 COS

12、T(3,8) = min5+COST(4,10),6+COST(4,11) = 7第2段 COST(2,2) = min4+COST(3,6) , 2+COST(3,7), 1+COST(3,8) = 7 COST(2,3) = 9 COST(2,4) = 18 COST(2,5) = 15第1段 COST(1,1) = min9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5) = 16S到t的最小成本路径的成本 16, 最小成本路径的求取 记 D(i,j)每一COST(i,j)的决策 即，使c(j,l)+COST(i+1,l)取得最小值的l值。

13、例：D(3,6) = 10, D(3,7)= 10 D(3,8) = 10 D(2,2) = 7, D(2,3) = 6,D(2,4) = 8,D(2,5) = 8 D(1,1) = 2 根据D(1,1)的决策值向后递推求取最小成本路径： v2=D(1,1)=2 v3 = D(2,D(1,1) = 7 v4 = D(3,D(2,D(1,1) = D(3,7) = 10 故由s到t的最小成本路径是：1271012,3) 算法描述 结点的编号规则 源点s编号为1,然后依次对V2、V3Vk-1中的结点编号，汇点t编号为n。 目的：使对COST和D的计算仅按n-1,n-2,1的次序计算即可，无需考虑标

14、示结点所在段的第一个下标。 算法描述,算法7.1 多段图的向前处理算法 procedure FGRAPH(E,k,n,P) /输入是按段的顺序给结点编号的，有n个结点的k段图。E是边 集，c(i,j)是边的成本。P(1:k)带出最小成本路径/ real COST(n); integer D(n-1),P(k),r,j,k,n COST(n)0 for jn-1 to 1 by -1 do /计算COST(j)/ 设r是具有性质：E且使c(j,r)+COST(r)取最小值的结点 COST(j)c(j,r) + COST(r) D(j) r /记录决策值/ repeat P(1)1; P(k)n

15、for j2 to k-1 do /找路径上的第j个结点/ P(j) D(P(j-1) /回溯求出该路径/ repeat end FGRAPH,算法的时间复杂度 若G采用邻接表表示，总计算时间为：,3. 向后处理策略求解 设 BP(i,j)是一条从源点s到Vi中的结点j的最小成本路径， BCOST(i,j)是这条路径的成本。 1) 向后递推式 2) 递推过程 第2段 c(1,j) E COST(2,j) = ,各递推结果第2段 BCOST(2,2) = 9 BCOST(2,3) = 7 BCOST(2,4) = 3 BCOST(2,5) = 2第3段 BCOST(3,6) = minBCOST

16、(2,2)+4,BCOST(2,3)+2 = 9 BCOST(3,7) = minBCOST(2,2)+2,BCOST(2,3)+7, BCOST(2,5)+11 = 11 BCOST(3,8) = minBCOST(2,4)+11, BCOST(2,5)+8 = 10第4段 BCOST(4,9) = minBCOST(3,6)+6,BCOST(3,7)+4 = 15 BCOST(4,10) = minBCOST(3,6)+5,BCOST(3,7)+3, BCOST(3,8)+5 = 14 BCOST(4,11) = minBCOST(3,8)+6 = 16第5段 BCOST(5,12) =

17、minBCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5 = 16S到t的最小成本路径的成本 16, 最小成本路径的求取 记 BD(i,j)每一COST(i,j)的决策 即，使COST(i-1,l)+c(l,j)取得最小值的l值。 例：BD(3,6) = 3, BD(3,7)= 2 ,BD(3,8) = 5 BD(4,9) = 6, BD(4,10) = 7, BD(4,11) = 8 BD(5,12) = 10 根据D(5,12)的决策值向前递推求取最小成本路径： v4 = BD(5,12)=10 v3 = BD(4,BD(5,12) = 7 v2 = BD(

18、3,BD(4,BD(5,12) = BD(3,7) = 2 故由s到t的最小成本路径是：1271012,算法7.2 多段图的向后处理算法 procedure BGRAPH(E,k,n,P) /输入是按段的顺序给结点编号的，有n个结点的k段图。E是边 集，c(i,j)是边的成本。P(1:k)带出最小成本路径/ real BCOST(n); integer BD(n-1),P(k),r,j,k,n BCOST(1)0 for j2 to n do /计算BCOST(j)/ 设r是具有E且使BCOST(r)+ c(r,j)取最小值性质的结点 BCOST(j) BCOST(r)+ c(r,j) BD(

19、j) r /记录决策值/ repeat P(1)1; P(k)n for jk-1 to 2 by -1 do /找路径上的第j个结点/ P(j) D(P(j+1) /回溯求出该路径/ repeat end BGRAPH,4. 多段图问题的应用实例资源的分配问题 将n个资源分配给r个项目的问题：如果把j个资源，0jn，分配给项目i，可以获得N(i,j)的净利。 问题：如何将这n个资源分配给r个项目才能使各项目获得的净利之和达到最大。 转换成一个多段图问题求解。,用r1段图描述该问题： 段： 1到r之间的每个段i表示项目i。 结点： i=1时，只有一个结点源点s =V(1,0) 当2ir时，每段

20、有n+1个结点，每个结点具有形式 V(i,j)：表示到项目i之前为止，共把j个资源分配给了 前i-1个项目，j=0,1,n。 汇点t=V(r+1,n) 边的一般形式：,jl,1ir 成本： 当jl且1ir时，边赋予成本 N(i,l-j),表示给项目i分配l-j个资源所可能获得的净利。 当jn且i=r时，此时的边为：,该边赋 予成本：,指向汇点的边,注，并不是分给的资源越多，得到的净利就越大,实例：将4个资源分配给3个项目。构成一个4段图。 问题的解：资源的最优分配方案由一条s到t的最大成本路径给出改变边成本的符号，从而将问题转换成为求取最小成本路径问题。,7.2 最大子段和,问题描述：给定由n

21、个整数（包含负整数）组成的序列a1,a2,.,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。依此定义，所求的最优值为： 例如，当(a1,a2, a3, a4, a5,a6)=(-2,11,-4,13,-5,-2)时，最大子段和为：,1. 一个简单算法,一个简单算法：int MaxSum(int n, a, 算法有3重循环，复杂性为O(n3)。,由于有：算法可作如下改进：int MaxSum(int n, a, 改进后的算法复杂性为O(n2) 。,2. 分治方法求解,从问题的解的结构可以看出，它适合于用分治策略求解：如果将所给的序列a1:n分为长度相等的两段a1:n/1

22、和an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大子段和有三种情形：a1:n的最大子段和与a1:n/2的最大子段和相同；a1:n的最大子段和与an/2+1:n的最大子段和相同；a1:n的最大子段和为下面的形式。A、B这两种情形可递归求得。对于情形C，容易看出，an/2与an/2+1在最优子序列中。因此，我们可以在a1:n/2和an/2+1:n中分别计算出如下的s1和s2。则s1+s2即为出现情形C使得最优值。 从而设计出下面所示的分治算法。,int MaxSubSum(int a, int left, int right) int sum=0; if (left=right)su

23、m=aleft0?aleft:0; elseint center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int rightsum=MaxSubSum(a,center+1,right); int s1=0;lefts=0; for (int i=center;i=left;i-) lefts+=ai; if (leftss1) s1=lefts; int s2=0;rights=0; for (int i=center+1;is2) s2=rights; sum=s1+s2; if (sumleftsum) sum=left

24、sum; if (sumsightsum) sum=rightsum; return sum;,3. 动态规划方法求解,在对上述分治算法的分析中我们注意到，由bj的定义易知，当bj-10时bj=bj-1+aj，否则bj=aj。由此可得计算bj的动态规划递归式bj=maxbj-1+aj，aj，1jn。据此，可设计出求最大子段和的动态规划算法如下：int MaxSum(int n, int a)int sum=0; b=0;for (i=1;i0) b+=ai; else b=ai;if (bsum) sum=b;return sum;显然该算法的计算时间为O(n)。,4. 算法的推广,最大矩阵和

25、问题，略最大m子段和问题，略,7.3 每对结点之间的最短路径,1. 问题描述 设G=(V,E)是一个有n个结点的有向图，C是G的成本邻接矩阵，C中元素有： 0 ，i j c(i,j)= 边的成本，ij且E(G) ，ij且 其中，1i，jn 每对结点之间的最短路径问题：求满足下述条件的矩阵A，A中的任一元素A(i,j)代表结点i到结点j的最短路径长度。,分析： 利用单源最短路径算法求解 计算n个结点的单源最短路径。 时间复杂度：(n3)利用动态规划策略求解 将求解G中每对结点之间的最短路径问题转化成一个多阶段决策过程。 决策什么？ 最优性原理对于该问题是否成立？,2. 动态规划求解策略1）最优性

26、原理对于每对结点之间的最短路径问题成立 对G的一条由i到j的最短路径（假设该路径中不包含环），设k是该路径上的一个中间结点： i,.,k,j 由i到k的最短路径 k是中间结点 由k到i的最短路径 则，由i到k和k到j的两条子路径将分别是由i到k和由k到j的最短路径。（反证，否则i,.,k,j也将不是由i到j的最短路径） 故，最优性原理对于该问题成立。,2）多阶段决策过程 所有n个结点从1到n依次编号。 设k是由i到j的最短路径上编号最高的中间结点： i,.,k,j k是编号最高的中间结点 则由i到k的子路径上将不会有比编号k-1更大的结点；同理，由k到j的子路径上也将不会有比编号k-1更大的结

27、点。 构造多阶段决策过程：对由i到j的最短路径，首先决策哪一个结点是该路径上具有最大编号的中间结点k，然后再去求取由i到k和由k到j的最短路径其中应不包含比k-1还大的中间结点。,3）递推关系式 记Ak(i,j)表示从i到j并且不经过比k还大的结点的最短路径长度。则， A(i,j) = An(i,j) 即，由i到j的最短路径不通过编号比n还大的结点。 注：该路径可以经过结点n，也可以不经过结点n。 若该路径经过结点n，则 An(i,j) An-1(i,n) + An-1(n,j) 若该路径不经过结点n，则 An(i,j) An-1(i,j) 故可得， An(i,j) = minAn-1(i,j

28、) ，An-1(i,n) + An-1(n,j) 不经过n结点 经过n结点,对任意的k， k1，有， Ak(i,j) = minAk-1(i,j) ，Ak-1(i,k) + Ak-1(k,j) 不经过结点k 刚好经过结点k 初值： A0(i,j)= C(i,j)，1in，1jn递推计算： A1(i,j), A2(i,j), An(i,j)= A (i,j),3. 算法描述算法7.3 每对结点之间的最短路径长度 procedure ALL-PATHS(COST,A,n) /COST(n,n)是n结点图的成本邻接矩阵；A(i,j)是结点vi到vj的最短路 径的成本；COST(i,i)=0,1in/

29、 integer I,j,k,n; real COST(n,n),A(n,n) for i1 to n do for j1 to n do A(i,j) COST(i,j) /用COST(i,j)对A0赋初值/ repeat repeat for k1 to n do for i1 to n do for j1 to n do A (i,j) minA (i,j) ，A (i,k) + A (k,j) repeat repeat repeat end ALL-PATHS,算法的设计说明1） Ak(i,k) = Ak-1(i,k) Ak(k,j) = Ak-1(k,j) ,ik且kj,则有Ak(

30、i,j) minAk-1(i,j), Ak(i,k) + Ak-1(k,j) ,在第i-1到第i次的迭代过程中，A的第k行、第k列元素不变,ki且jk,则有Ak(i,j) minAk-1(i,j), Ak-1(i,k) + Ak(k,j) ,ki且kj,则有Ak(i,j) minAk-1(i,j), Ak(i,k) + Ak(k,j) ,Ak(i,j) minAk-1(i,j), Ak(i,k) + Ak-1(k,j) Ak(i,j) minAk-1(i,j), Ak-1(i,k) + Ak(k,j) Ak(i,j) minAk-1(i,j), Ak(i,k) + Ak(k,j) Ak(i,j

31、) minAk-1(i,j), Ak-1(i,k) + Ak-1(k,j) 在算法的计算过程中取消了A的上标，并保证了每次计算 的 Ak(i,j)即为 minAk-1(i,j), Ak-1(i,k) + Ak-1(k,j) 2）如何求每对结点之间的路径？,例7.3 有向图如图所示,求图中所有结点间最短路径的成本矩阵,注： A(i,j) = 表明G中从i到j没有有向路径,性能分析 计算时间 注：该时间与A的值无关： for k1 to n do 迭代n次 for i1 to n do 迭代n次 for j1 to n do 迭代n次 A (i,j) minA (i,j) ，A (i,k) + A

32、 (k,j) repeat repeat repeat,7.4 矩阵连乘问题,给定n个矩阵A1,A2,.,An，其中Ai与Ai+1是可乘的，i=1,2,.,n-1。考察这n个矩阵的连乘积A1A2.An。由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。,7.4 矩阵连乘问题,完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积

33、并加括号，即A=(BC)。,7.4矩阵连乘问题,设有四个矩阵A,B,C,D，它们的维数分别是：A=5010，B=1040，C=4030，D=305总共有五种完全加括号的方式：(A(BC)D) (A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D)其数乘次数分别为：16000, 10500, 36000, 87500, 34500,7.4 .1 穷举搜索法,问题描述：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相

34、应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,7.4.1 穷举搜索法,算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下： P(n)是随n的增长成指数增长的。,动态规划法1.分析最优解的结构,预处理：将矩阵连乘积A1A2.An简记为Ai:j，这里ij。考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为（A1A2. Ak）（Ak+1 Ak+2. An ）。计算量：Ai:k的计算量加上Ak+

35、1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量。,动态规划法1.分析最优解的结构,分析最优解的结构特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,2.建立递归关系,设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n。当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n。当ij时，mi,j=mi,k+mk+1,j+pi-1pkpj，这里Ai的维数为pi-1pi。可

36、以递归地定义mi,j为： k的位置只有j-1种可能。,3.计算最优值,对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。,7.3.3矩阵连乘算法算法描述,【程序73】矩阵连乘算法class MatrixChainpublic: MatrixChain(int mSize,i

37、nt *q); int MChain(); int LookupChain(); void Traceback(); ,private: void Traceback(int i,int j); int LookupChain(int i, int j); int *p,*m,*s,n;,int MatrixChain:MChain() /求A0:n-1的最优解值 for (int i=0;in;i+) mii=0;, 牛牛文库文档分享,for (int r=2; r=n;r+) for (int i=0;i=n-r;i+) int j=i+r-1; mij=mi+1j+pi*pi+1*pj+

38、1; sij=i; for (int k=i+1;kj;k+) int t=mik +mk+1j+pi*pk+1*pj+1; if (tmij) mij=t;sij=k; return m0n-1;, 牛牛文库文档分享,void MatrixChain:Traceback(int i,int j) if(i=j) coutAi;return; if (isij) cout(; Traceback(i,sij);if (isij)cout); if(sij+1j)cout(; Traceback(sij+1,j);if(sij+1j) cout);void MatrixChain:Traceba

39、ck() cout(; Traceback(0,n-1);cout); coutendl;, 牛牛文库文档分享,示例,4.构造最优解,算法描述：略。复杂性分析：算法MatrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。算法TraceBack的复杂性？,7.4.2 动态规划算法的基本要素,从计算矩阵连乘积最优计算次序的动态规划算法可以看出，该算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。从一般意义上讲，问题的这两个重要

40、性质是该问题可以用动态规划算法求解的基本要素。本节着重介绍：最优子结构重叠子问题备忘录方法,一、最优子结构,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。,一、最优子结构,利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占

41、用小，问题的维度低）,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,三、备忘录方法,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。int LookupChain(int i，int j)if

42、(mij 0) return mij;if (i = j) return 0;int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj;sij = i;for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj;if (t u) u = t; sij = k;mij = u;return u;算法复杂性：T(n)=O(n3),关于动态规划算法和备忘录方法的适用条件,矩阵连乘积的最优计算次序问题可用自顶向下的备忘录方法或自底向

43、上的动态规划算法在O(n3)计算时间内求解。这两个算法都利用了子问题重叠性质。总共有(n2)个不同的子问题，对每个子问题两种算法都只解一次并记录答案。当再次遇到该子问题时，简单地取用已得到的答案，节省了计算量，提高了算法的效率。,关于动态规划算法和备忘录方法的适用条件,适用条件：一般来说，当一个问题的所有子问题都至少要解一次时，用动态规划算法比用备忘录方法好。此时，动态规划算法没有任何多余的计算，还可以利用其规则的表格存取方式来减少在动态规划算法中的计算时间和空间需求。当子问题空间中部分子问题可以不必求解时，易用备忘录方法则较为有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题

44、。,7.5 Longest Common Susequence,问题的定义 最长公共子序列 (LCS) 结构分析 建立求解LCS长度的递归方程 自底向上LCS长度的计算 构造优化解, 牛牛文库文档分享,定义：若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X=x1,x

45、2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。,最长公共子序列（LCS）问题输入：X = (x1,x2,.,xn)，Y = (y1,y2,.ym)输出：Z = X与Y的最长公共子序列, 牛牛文库文档分享,最长公共子序列结构分析,第i前缀设X=(x1, x2, ., xn)是一个序列，X的第i前缀Xi是一个序列，定义为Xi=(x1, ., xi ) 例. X=(A, B, D, C, A), X1=(A), X2=(A, B), X3=(A, B, D),优化子结构定理1（优化子结构）设X=(x1, ., xm)、Y=(y1, ., yn)是两个序列，Z=(z1, ., zk)是X

46、与Y的LCS，我们有： 如果xm=yn, 则zk=xm=yn, Zk-1是Xm-1和Yn-1的LCS， 即，LCSXY = LCSXm-1Yn-1+ . 如果xmyn，且zkxm，则Z是Xm-1和Y的LCS，即LCSXY= LCSXm-1Y 如果xmyn,且zkyn,则Z是X与Yn-1的LCS，即LCSXY= LCSXYn-1,最长公共子序列的结构,设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。若xmyn且zk

47、yn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,证明: . X=, Y=，则 LCSXY = LCSXm-1Yn-1+ . 设zkxm，则可加xm=yn到Z，得到一个长为k+1的X与Y的公共序列，与Z是X和Y的LCS矛盾。于是zk=xm=yn。 现在证明Zk-1是Xm-1与Yn-1的LCS。显然Zk-1是Xm-1与Yn-1的公共序列。我们需要证明Zk-1是LCS。 设不然，则存在Xm-1与Yn-1的公共子序列W，W的长大于k-1。增加xm=yn到W，我们得到一个长大于k的X与Y的公

48、共序列，与Z是LCS矛盾。于是，Zk-1是Xm-1与Yn-1的LCS., X=, Y=，xmyn，zkxm，则 LCSXY= LCSXm-1Y 由于zkxm，Z是Xm-1与Y的公共子序列。我们来证Z是Xm-1与Y的LCS。设Xm-1与Y有一个公共子序列W，W的长大于k, 则W也是X与Y 的公共子序列，与Z是LCS矛盾。 同可证。,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由

49、最优子结构性质可建立递归关系如下：,计算最优值,由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j;for (i = 1; i =cij-1) cij=ci-1j; bij=2;else cij=cij-1; bij=3; ,构造最长公共子序列,算法描述：void LCS(int i，int j，char *x，int *b)if (i =0 | j=0) return;if (bij= 1) LC

50、S(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b);else LCS(i，j-1，x，b);,算法的改进,在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数