单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法设计与分析,授课教师：王秋芬,办公地点：,7307,Email:,w_,第四章 动态规划,目录,概述,矩阵连乘问题,凸多边形最优三角剖分,最长公共子序列问题,加工顺序问题,0-1,背包问题,最优二叉查找树,教学目标,理解动态规划的思想,掌握动态规划、分治法及贪心法的异同,掌握动态规划的基本要素,掌握动态规划的设计步骤,通过实例学习，掌握动态规划设计的策略,学习动态规划的意义,动态规划的应用领域：经济管理、生产调度、工程技术和,最优控制,等，例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，是多阶段决策过程，因此研究该算法具有很强的实际意义动态规划算法通常用于求解具有某种最优性质的问题，,动态规划的基本思想,基本思想,适合采用动态规划法求解的问题，经分解得到的各个子问题往往不是相互独立的在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出这样就避免了大量的无意义的重复计算，从而降低算法的时间复杂性。
如何对已解决的子问题的解进行保存呢？通常采用表的形式，即在实际求解过程中，一旦某个子问题被计算过，不管该问题以后是否用得到，都将其计算结果填入该表，需要的时候就从表中找出该子问题的解，具体的动态规划算法多种多样，但它们具有相同的填表格式参考,【,例,4-1】,）,动态规划的解题步骤,（,1,）分析最优解的性质，刻画最优解的结构特征,考察是否适合采用动态规划法2,）递归定义最优值（即建立递归式或动态规划方程）3,）以自底向上的方式计算出最优值，并记录相关信息4,）根据计算最优值时得到的信息，构造出最优解动态规划的基本要素,最优子结构性质,子问题重叠性质,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题出现多次，这种性质称为子问题的重叠性质在应用动态规划时，对于重复出现的子问题，只需在第一次遇到时就加以解决，并把已解决的各个子问题的解储存在表中，便于以后遇到时直接引用，从而不必重新求解，可大大提高解题的效率自底向上的求解方式,矩阵连乘,问题描述,给定,n,个矩阵,A,1,A,2,A,3,A,n,，其中,A,i,与,A,i+1,(i=1,2,3,n-1),是可乘的用加括号的方法表示矩阵连乘的次序，不同加括号的方法所对应的计算次序是不同的。
以,【,例,4-2】,为例讲述,最优子结构性质分析,建立最优值的递归关系式,A,i,A,i+1,A,j,矩阵连乘，其中矩阵,A,m,的行数为,p,m,，列数为,q,m,(m,=i,i+1,j),且相邻矩阵是可乘的,(,即,q,m,=p,m,+1),设它们的最佳计算次序所对应的乘法次数为,mij,，则,A,i,A,i+1,A,k,的最佳计算次序对应的乘法次数为,mik,，,A,k+1,A,k+2,A,j,的最佳计算次序对应的乘法次数为,mk+1j,当,i=j,时，只有一个矩阵,故,mii,=0,；,当,ij,时，将,n,个矩阵的行数和列数存储在数组,P0:n,则上述递归式可改写为：,算法设计,步骤,1,：确定合适的数据结构采用数组,m,来存放各个子问题的最优值，数组,s,来存放各个子问题的最优决策,;,步骤,2,：初始化令,mii,=0,，,sii,0,，其中,i=1,2,n,；,步骤,3,：循环阶段步骤,3-1,：按照递归关系式计算,2,个矩阵,A,i,A,i+1,相乘时的最优值并将其存入,mii+1,，同时将最优决策记入,sii+1,，,i=1,2,n-1,；,步骤,3-2,：按照递归关系式计算,3,个矩阵,A,i,A,i+1,A,i+2,相乘时的最优值并将其存入,mii+2,，同时将最优决策记入,sii+2,，,i=1,2,n-2,；,依此类推，直到,步骤,3-(n-1),：按照递归关系式计算,n,个矩阵,A,1,A,2,A,n,相乘时的最优值并将其存入,m1n,，同时将最优决策记入,s1n,。
至此，,m1n,即为原问题的最优值步骤,4,：根据数组,s,记录的最优决策信息来构造最优解步骤,4-1,：递归构造,A,1,A,s1n,的最优解，直到包含一个矩阵结束；,步骤,4-2,：递归构造,A,s1n+1,A,n,的最优解，直到包含一个矩阵结束；,步骤,4-3,：将步骤,4-1,和步骤,4-2,递归的结果加括号构造实例,求矩阵,A,1,（,32,）、,A,2,（,25,）、,A,3,（,510,）、,A,4,（,102,）和,A,5,（,23,）连乘的最佳计算次序表,4-6,实例最优值,mij,表,4-7,实例最优决策,sij,mij,A,1,A,2,A,3,A,4,A,5,sij,A,1,A,2,A,3,A,4,A,5,A,1,0,30,160,132,150,A,1,0,1,1,1,1,A,2,0,100,120,132,A,2,0,2,2,4,A,3,0,100,130,A,3,0,3,4,A,4,0,60,A,4,0,4,A,5,0,A,5,0,递归构造最优解,算法分析,语句,int,t=mik+mk+1j+pi-1*,pk,*,pj,;,为算法,MatrixChain,的基本语句，最坏情况下该语句的执行次数为,O(n,3,),，故该算法的最坏时间复杂性为,O(n,3,),。
构造最优解的,Traceback,算法的时间主要取决于递归最坏情况下时间复杂性的递归式为：,解此递归式得,T(n,)=,O(n,),凸多边形最优三角剖分,基本概念,一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形凸多边形的不相邻的两个顶点连接的直线段称为凸多边形的弦凸多边形的三角剖分指将一个凸多边形分割成互不相交的三角形的弦的集合给定凸多边形及定义在边、弦构成的三角形的权函数，最优三角剖分即不同剖分方法所划分的各三角形上权函数之和最小的三角剖分三角剖分的结构,将图,4-6,中的叶子结点,v,i,v,i+1,与矩阵,A,i+1,(i=0,1,2,3,4),对应，则图,4-6,和图,4-4,所示的二叉树是一样的因此，,n+1,边形的三角剖分与,n,个矩阵连乘的计算次序是一一对应的可见，,凸多边形最优剖分问题的解决方法和矩阵连乘问题相似最优子结构性质分析,设,v,0,v,k,v,n,是将,n+1,边形,P=v,0,v,1,v,n,分成三部分,v,0,v,1,v,k,、,v,k,v,k+1,v,n,和,v,0,v,k,v,n,的最佳剖分方法，那么凸多边形,v,0,v,1,v,k,的剖分一定是最优的，,v,k,v,k+1,v,n,的剖分也一定是最优的。
设,v,0,v,1,v,n,三角剖分的权函数之和为,c,，,v,0,v,1,v,k,三角剖分的权函数之和为,a,，,v,k,v,k+1,v,n,三角剖分的权函数之和为,b,，三角形,v,0,v,k,v,n,的权函数为,w(v,0,v,k,v,n,),，则,c=,a+b,+w(v,0,v,k,v,n,),如果,c,是最小的，则一定包含,a,和,b,都是最小的如果,a,不是最小的，则它所对应的,v,0,v,1,v,k,的三角剖分就不是最优的那么，对于凸多边形,v,0,v,1,v,k,来说，肯定存在最优的三角剖分，设,v,0,v,1,v,k,的最优三角剖分对应的权函数之和为,a(aa),，用,a,代替,a,得到,c=a+b+w(v,0,v,k,vn),，则,cc,，这说明,c,对应的,v,0,v,1,v,n,的三角剖分不,是,最优的，产生矛盾故,a,一定是最小的同理，,b,也是最小的最优子结构性质得证建立最优值的递归关系式,设,mij,表示,v,i-1,v,i,v,j,最优三角剖分权函数之和，,i=j,时表示一条直线段，将其看作退化多边形，其权函数为,0,则,最长公共子序列问题,基本概念,（,1,）子序列,给定序列,X=x,1,x,2,x,n,、,Z=z,1,z,2,z,k,，若,Z,是,X,的子序列，当且仅当存在一个严格递增的下标序列,i,1,i,2,i,k,，对,j1,2,k,有,z,j,=x,。
2,）公共子序列,给定序列,X,和,Y,，序列,Z,是,X,的子序列，也是,Y,的子序列，则称,Z,是,X,和,Y,的公共子序列3,）最长公共子序列,包含元素最多的公共子序列即为最长公共子序列建立最优值的递归关系式,设,cij,表示序列,X,i,和,Y,j,的最长公共子序列的长度则：,算法设计,步骤,1,：确定合适的数据结构采用数组,c,来存放各个子问题的最优值，数组,b,来存放各个子问题最优值的来源数组,x1:m,和,y1:n,分别存放,X,序列和,Y,序列；,步骤,2,：初始化令,ci0,0,，,c0j=0,，其中,0im,，,0jn,；,步骤,3,：循环阶段根据递归关系式，确定序列,Xi,和,Y,的最长公共子序列长度；,步骤,3-1,：,i=1,时，求出,c1j,，同时记录,b1j,，,1jn,；,步骤,3-2,：,i=2,时，求出,c2j,，同时记录,b2j,，,1jn,；,依此类推，直到,步骤,3-m,：,i=m,时，求出,cmj,，同时记录,bmj,，,1jn,此时，,cmn,便是序列,X,和,Y,的最长公共子序列长度；,步骤,4,：根据二维数组,b,记录的相关信息以自底向上的方式来构造最优解；,步骤,4-1,：初始时，,i=m,，,j=n,；,步骤,4-2,：如果,bij,=1,，则输出,xi,，同时递推到,bi-1j-1;,如果,bij,=2,，则递推到,bij-1;,如果,bij,=3,，则递推到,bi-1j,；,重复执行步骤,4-2,，直到,i=0,或,j=0,，此时就可得到序列,X,和,Y,的最长公共子序列。
实例构造,【,例,4-6】,给定序列,X=A,B,C,B,D,A,B,和,Y=B,D,C,A,B,A,，求它们的最长公共子序列1,）,m=7,，,n=6,，将停止条件填入数组,c,中，即,ci0,0,，,c0j=0,，其中,0im,，,0jn,2,）当,i=1,时，,X,1,=A,，最后一个字符为,A,；,Y,j,的规模从,1,逐步放大到,6,，其最后一个字符分别为,B,、,D,、,C,、,A,、,B,、,A,；,依此类推，直到,i=7,从,i=7,，,j=6,处向前递推，找到,X,和,Y,的最长公共子序列为,B,C,B,A,加工顺序问题,问题描述,设有,n,个工件需要在机器,Ml,和,M2,上加工，每个工件的加工顺序都是先在,Ml,上加工，然后在,M2,上加工t,1j,，,t,2j,分别表示工件,j,在,M1,，,M2,上所需的加工时间,(j=1,2,n),问应如何在两机器上安排生产，使得第一个工件从在,M1,上加工开始到最后一个工件在,M2,上加工完所需的总加工时间最短？,最优子结构性质分析,将,n,个工件的集合看作,N=1,2,n,，设,P,是给定,n,个工件的一个最优加工顺序方案，,P(i,),是该调度方案的第,i,个要调度的工件,(i=1,2,n),。
从集合,S,中的第一个工件开始在机器,M1,上加工到最后一个工件在机器,M2,上加工结束时所耗的时间为,T(S,，,t),设集合,S,的最优加工顺序中第一个要加工的工件为,i,，那么，经过的时间，进入的状态为第一台机器,M1,开始加工集合,S-i,中的工件时，第二台机器,M2,需要时间才能空闲下来，这种情况下机器,M2,加工完,S-i,中的工件所需的时间为,T(S-i,，,t),，其中，即,t=t,2i,+maxt-t,1i,，,0,，则,T(S,，,t)=t,1i,+T(S-i,，,t,2i,+,maxt,-t,1i,，,0),（,4-1,）,从式（,4-1,）。