动态规划算法课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,、概述,什么是动态规划,?,它能解决哪些问题,?,解决的步骤又是什么样的,?,动态规划（,dynamic programming,）作为一种多阶段决策,优化过程,的通用方法，它是在,20,世纪,50,年代由一位卓越的美国数学家,Richard Bellman,所发明的。因此，这个技术名字中的,programming,是计划和规划的意思，不是代表计算机中的编程。,规划,（,programming,）的含义意味着一系列的决策，而,动态,（,dynammic,）的含义则传递着这样一种思想，就是所作的决策可能依赖于当前状态，而与此前所作的决策无关。,3.2,举例：最短路径问题,为了找到由,A,到,E,的最短路线，可以将该问题分成,A-B-C-D-E 4,各阶段，在每个阶段都需要作出决策，即在,A,点需要决策下一步到,B1,还是,B2,或,B3,；同样，若到达第二阶段某个状态，比如,B1,需要决定走向,C1,还是,C2,；依次类推，可以看出：各个阶段的决策不同，由,A,到,E,的路线就不同，当从某个阶段的某个状态发出一个决策，则这个决策不仅影响到下一各阶段的距离，而且直接影响后门各个阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策，使这些决策序列所决定的一条线路对应的线路最短。,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,算法总体思想,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,算法总体思想,n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),Why,Divide and Conquer,技术的问题,子问题是相互独立的,如果子问题不是相互独立的,分治方法将重复计算公共子问题,效率很低,优化问题,给定一组约束条件和一个代价函数,在解空间中搜索具有最小或最大代价的优化解,很多优化问题可以分解为多个子问题,子问题相互关联,子问题的解被重复使用,How,使用动态规划的条件,优化子结构,当一个问题的优化解包含了子问题的优化解时,我们说这个问题具有优化子结构,缩小子问题的集合,只要哪些优化问题包含了优化子问题,降低实现复杂性,重叠子问题,在问题的求解过程中,很多子问题的解被多次重复使用,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。,递归地定义最优值。,以自底向上的方式计算出最优值。,根据计算最优值时得到的信息，构造最优解。,3.3,矩阵连乘,（,1,）单个矩阵是完全加括号的；,（,2,）矩阵连乘积 是完全加括号的，则 可,表示为,2,个完全加括号的矩阵连乘积 和,的乘积并加括号，即,16000,10500,36000,87500,34500,完全加括号的矩阵连乘积可递归地定义为：,设有四个矩阵 ，它们的维数分别是：,总共有五中完全加括号的方式,矩阵连乘问题,给定,n,个矩阵 ，其中 与 是可乘的，。考察这,n,个矩阵的连乘积,由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。,若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用,2,个矩阵相乘的标准算法计算出矩阵连乘积,矩阵连乘问题,给定,n,个矩阵,A,1,A,2,A,n,，其中,A,i,与,A,i,+1,是可乘的，,i=1,2,n-1,。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。,穷举法,：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：,对于,n,个矩阵的连乘积，设其不同的计算次序为,P(n),。,由于每种加括号方式都可以分解为两个子矩阵的加括号问题：,(A,1,.A,k,)(A,k,+1A,n,),可以得到关于,P(n),的递推式如下：,矩阵连乘问题,穷举法,动态规划,将矩阵连乘积 简记为,Ai:j,，这里,i,j,考察计算,Ai:j,的最优计算次序。设这个计算次序在矩阵,Ak,和,Ak+1,之间将矩阵链断开，,i,kj,，则其相应完全,加括号方式为,计算量：,Ai:k,的计算量加上,Ak+1:j,的计算量，再加上,Ai:k,和,Ak+1:j,相乘的计算量,分析最优解的结构,特征：计算,Ai:j,的最优次序所包含的计算矩阵子链,Ai:k,和,Ak+1:j,的次序也是最优的。,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为,最优子结构性质,。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,建立递归关系,设计算,Ai:j,，,1ijn,，所需要的最少数乘次数,mi,j,，则原问题的最优值为,m1,n,当,i=j,时，,Ai:j=Ai,，因此，,mi,i=0,，,i=1,2,n,当,ij,时，,可以递归地定义,mi,j,为：,这里 的维数为,的位置只有,种,可能,计算最优值,对于,1ijn,不同的有序对,(i,j),对应于不同的子问题。因此，不同子问题的个数最多只有,由此可见，在递归计算时，,许多子问题被重复计算多次,。这也是该问题可用动态规划算法求解的又一显著特征。,用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法,用动态规划法求最优解,public static void,matrixChain,(int p,int m,int s),int n=p.length-1;,for,(int i=1;i=n;i+)mii=0;,for,(int r=2;r=n;r+),for,(int i=1;i=n-r+1;i+),int j=i+r-1;,mij=mi+1j+pi-1*pi*pj;,sij=i;,for,(int k=i+1;k j;k+),int t=mik+mk+1j+pi-1*pk*pj;,if,(t mij),mij=t;,sij=k;,A1,A2,A3,A4,A5,A6,30,35,35,15,15,5,5,10,10,20,20,25,动态规划算法的基本要素,一、最优子结构,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为,最优子结构性质,。,在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。,利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。,注意：同一个问题可以有多种,方式刻划,它,的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。,这种性质称为,子问题的重叠性质,。,动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。,通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,3.4 0/1,背包问题,给定,n,种物品和一背包。物品,i,的重量是,w,i,，其价值为,v,i,，背包的容量为,C,。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大,?,0-1,背包问题是一个特殊的整数规划问题。,对于,0/1,背包问题，可以通过作出变量,X,1,X,2,.,X,i,的一个决策序列来得到它的解。而对变量,X,的决策就是决定它是取,0,值还是取,1,值。鉴定决策这些,X,的次序为,X,n,X,n-1,.,X,1,。在对,X,n,作出决策之后，问题处于下列两种状态之一：,背包的剩余容量是,X=M,，没有产生任何价值；,剩余容量是,X=M-w,n,，价值增长了,p,n,。,显然，剩余下来对,X,n,X,n-1,.,X,1,的决策相对于决策,X,所产生的问题状态应该是最优的，否则,X,n,X,n-1,.,X,1,就不可能是最优决策序列。,背包问题的实例分析,考虑以下情况的背包问题，,n=3,W=6,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5),f1(1)=maxf0(1),f0(1-w1)+p1=0,f1(2)=maxf0(2),f0(2-w1)+p1=p1=1,f1(3),到,f1(6),与,f1(2),相同,f2(1)=maxf1(1),f1(1-w2)+p2=0,f2(2)=maxf1(2),f1(2-w2)+p2=1,f2(3)=f2(4)=maxf1(3),f1(3-w2)+p2=2,f2(5)=f2(6)=maxf1(5),f1(5-w2)+2=3,f3(6)=maxf2(6),f2(6-w3)+p3=max3,f1(2)+4=4,0-1,背包问题,设所给,0-1,背包问题的子问题,的最优值为,m(i,，,j),，即,m(i,，,j),是背包容量为,j,，在前,i,各物体中，能够装入载重量为,j,的背包中的物体的最大价值。由,0-1,背包问题的最优子结构性质，可以建立计算,m(i,，,j),的递归式如下。,动态规划求解,0/1,背包的算法描述,template,Type knapsack_dynamic(int w,Type p,int n,int m,BOOL x),int I,j,k;,Type v,(*optp)m+1=new Typen+1m+1;,for(i=0;i=n;i+),optpi0=0;xi=FALSE;,for(i=0;i=m;i+),optp0i=0;,/,初始化,动态规划背包算法,for(i=1;i=n;i+),计算,optpij,for(j=1;j=wi)&(optpi-1,j-wi+pi)optpi-1j),optpij=optpi-1,j-wi+pi;,j=m;/,递推装入背包的物体,for(i=n;i0;i-),if(optpijoptpi-1j),xi=FALSE;j=j-wi;,v=optpnm;,Delete optp;,Return v;,/,结束,例题,0/1,背包问题,有五个物体，其重量分别为,2,，,2,，,6,，,5,，,4,，价值分别是,6,，,3,，,5,，,4,，,6,，背包的载重量为,10,，求装入背包的物体及其总价值表。,0,1,2,3,4,5,6,7,8,9,10,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,6,6,6,6,6,6,6,6,6,2,0,0,6,6,9,9,9,9,9,9,9,3,0,0,6,6,9,9,9,9,11,11,14,4,0,0,6,6,9,9,9,10,11,13,14,5,0,0,6,6,9,9,12,12,15,15,15,答案是,11001,3.5,最长公共子序列,若给定序列,X=x,1,x,2,x,m,，则另一序列,Z=z,1,z,2,z,k,，是,X,的子序列是指存在一个严格递增下标序列,i,1,i,2,i,k,使得对于所有,j=1,2,k,有：,z,j,=x,i,j,。例如，序列,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=x,1,x,2,x,m,和,Y=y,1,y,2,y,n,，找出,X,和,Y,的最长公共子序列。,最长公共子序列的结构,设序列,X=x,1,x,2,x,m,和,Y=y,1,y,2,y,n,的最长公共子序列为,Z=z,1,z,2,z,k,，则,(1),若,x,m,=y,n,，则,z,k,=x,m,=y,n,，且,z,k-1,是,x,m-1,和,y,n-1,的最长公共子序列。,(2),若,x,m,y,n,且,z,k,x,m,，则,Z,是,x,m-1,和,Y,的最长公共子序列。,(3),若,x,m,y,n,且,z,k,y,n,，则,Z,是,X,和,y,n-1,的最长公共子序列。,由此可见，,2,个序列的最长公共子序列包含了这,2,个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有,最优子结构性质,。,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用,cij,记录序列和的最长公共子序列的长度。其中，,X,i,=x,1,x,2,x,i,；,Yj=y,1,y,2,y,j,。当,i=0,或,j=0,时，空序列是,X,i,和,Y,j,的最长公共子序列。故此时,Cij=0,。其他情况下，由最优子结构性质可建立递归关系如下：,计算最优值,由于在所考虑的子问题空间中，总共有,(mn),个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,Algorithm,lcsLength,(x,y,b),1:m,x.length-1;,2:n,y.length-1;,3:ci0=0;c0i=0;,4:,for,(int i=1;i=m;i+),5:,for,(int j=1;j=cij-1),10:cij=ci-1j;,11:bij=2;,12:,else,13:cij=cij-1;,14:bij=3;,构造最长公共子序列,Algorithm lcs,(int i,int j,char x,int b),if,(i=0|j=0),return,;,if,(bij=1),lcs,(i-1,j-1,x,b);,System.out.,print,(xi);,else if,(bij=2),lcs,(i-1,j,x,b);,else lcs,(i,j-1,x,b);,动态规划 最长公共子序列 例题,求,A=xyxzyxyzzy,B=xzyzxyzxyzxy,的最长公共子序列。,解：用两个表，来分别用来存放搜索过程中所得到的子序列的长度,cij,和状态,bij.,最终得到的最长公共子序列是,A(1,2,3,4,6,7,8,10)=xyxzxyzy,最长公共子序列的两个存储表,0,1,2,3,4,5,6,7,8,9,10,11,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,2,0,1,1,2,2,2,2,2,2,2,2,2,2,3,0,1,1,2,2,3,3,3,3,3,3,3,3,4,0,1,2,2,3,3,3,4,4,4,4,4,4,5,0,1,2,3,3,3,4,4,4,5,5,5,5,6,0,1,2,3,3,4,4,4,5,5,5,6,6,7,0,1,2,3,3,4,5,5,5,6,6,6,7,8,0,1,2,3,4,4,5,6,6,6,7,7,7,9,0,1,2,3,4,4,5,6,6,6,7,7,7,10,0,1,2,3,4,4,5,6,6,7,7,7,8,子序列的长度表,最长公共子序列的状态表及搜索,0,1,2,3,4,5,6,7,8,9,10,11,12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,3,3,3,1,3,3,1,3,3,1,3,2,0,2,2,1,3,3,1,3,3,1,3,3,1,3,0,1,2,2,2,1,3,3,1,3,3,1,3,4,0,2,1,2,1,2,2,1,3,3,1,3,3,5,0,2,2,1,2,2,1,2,2,1,3,3,1,6,0,1,2,2,2,1,2,2,1,2,2,1,3,7,0,2,2,1,2,2,1,3,2,1,3,2,1,8,0,2,1,2,1,2,2,1,3,2,1,3,2,9,0,2,1,2,1,2,2,1,2,2,1,2,2,10,0,2,2,1,2,2,1,2,2,1,2,2,1,3.6,最大子段和,给定由,n,个整数,(,可能为负整数,),组成的序列,a1,a2,an,，,求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为,0,。,例如，当（,a1,a2,a3,a4,a5,a6,）,=-2,11,-4,13,-5,-2,时，最大子段和为,20,。,简单算法,由题意直接求解，用数组,a,存储给定的,n,个整,a1,a2,an,。,int MaxSum(int n,int*a),int max=0;,for(int i=1;i=n;i+),for(int j=I;j=n;j+),int tmp=0;,for(int k=i;kmax),max=tmp;,return max;,时间复杂度为,O(n3),动态规划算法,若记,bj,为从第,i,个数加到第,j,个数的最大值。那么最大字段和就是,b1,b2,bn,中的最大值。,由,bj,的定义易知，当,bj-10,时,bj=bj-1+aj,否则,bj=aj,。,由此可得计算,bj,的动态规划递归式,bj=maxbj-1+aj,aj,1=j=n,动态规划代码,int MaxSum(int n,int*a),int max=0,b=0;,for(int i=1;i0),b+=ai;,else,b=ai;,if(bmax),max=b;,return max;,