计算机算法设计-第三章.ppt

计算机算法设计 与分析,第三章 动态规划,引言,分治法求解问题的关键是原问题可分解，而且分解得到的子问题相互对立且可解。 动态规划算法与分治法很类似，其基本思想也是将待求解问题分解成若干子问题，现求解子问题然后再将结果合并。 它们之间有什么不同呢？,引言,不同： 适合用动态规划算法解决的问题经过分解得到的子问题往往并不独立。如果用分治法来解决可能因为分解的子问题数目过多而使算法没有实际意义。,引言,动态规划是如何克服的呢？ 有些操作在子问题间要被执行好多次，为了避免大量的重复操作，动态规划技术利用一个表来记录这些操作的结果，从而保证时间复杂性为多项式时间。 动态规划算法适用于解决最优问题。,引言,通常按照下面4步设计： 找出最优解的性质，并刻画其结构特征； 递归地定义最优值； 以自底向上的方法计算出最优值； 根据计算最优值时得到的信息，构造最优解。 注：动态规划的基本步骤，如果只需要最优值，步骤可以不要。如果需要最优解，则需要执行。,3.1 矩阵连乘问题,练习：有三个矩阵： A1为10*100，A2为100*5，A3为5*50 求A1 * A2 * A3 需要执行基本乘法的最小值。 如果矩阵A是一个p*q的矩阵，B是q*r的矩阵，则乘积C=AB是一个p*r的矩阵。在上述算法中，基本操作的时间复杂性为p*q*r。,void matrixmultiply(int *a,int *b,int *c,int ra, int ca,int rb,int cb) if(ca!=rb) error(“矩阵不可乘”); for(int i=0;ira;i+) for(int j=0;jcb;j+) int sum=ai0*b0j; for(int k=1;kca;k+) sum+=aik*bkj; cij=sum; ,3.1 矩阵连乘问题,给定n个矩阵 ，其中Ai与Ai+1是可乘的，i=1，2，n-1。我们来研究这n个矩阵连乘积。,3.1 矩阵连乘问题,矩阵具有结合律，所以矩阵连乘积可以有许多不同的计算次序。矩阵的次序可以用括号来确定。如果说一个矩阵连乘积的计算次序完全确定，也就说该连乘积已完全加括号，则可以反复调用2个矩阵相乘的标准算法来计算出矩阵连乘积。,3.1 矩阵连乘问题,完全加括号：,3.1 矩阵连乘问题,矩阵连乘问题就是研究给定的n个矩阵的计算次序，从而使得乘积的计算次数最少。 采用什么方法呢？ 穷举法是最容易想到的，但是这样的计算量太大。,3.1 矩阵连乘问题,分析：将n个矩阵在第k个和第k+1个矩阵之间将原矩阵分解两个矩阵，k=1,2,n-1;然后分别对这两子矩阵完全加括号，最后对所的结果加括号。设不同的计算次序P(n)。,3.1 矩阵连乘问题,动态规划法： 1、分析最优解的结构： a. 记Ai:j。我们计算A1:n的最优计算次序，假设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，然后我们分别计算A1:k和Ak+1,n，最后计算这两个结果的乘法。,3.1 矩阵连乘问题,动态规划法： 1、分析最优解的结构： b.这一步骤的关键是确定矩阵连乘具有最优子结构。计算A1:n的最优次序包含的计算矩阵子链A1:k和Ak+1,n的次序也是最优的。,问题的最优子结构是问题可 以利用动态规划法的显著特征。,3.1 矩阵连乘问题,2、建立递归关系：递归的定义最优值 设计算Ai:j，1=i=j=n，所需要的最少数乘次数为mij，则原问题的最优值为m1n。 a 当i=j时，为一个单一矩阵，不需要计算，因此 mii=0;,3.1 矩阵连乘问题,2、建立递归关系：递归的定义最优值 b 当ij时，可以利用最优子结构的性质来计算。如果Ai:j在Ak和Ak+1之间断开，则 mij=mik+mk+1j+pi-1pkpj。 在开始计算时，k不确定，但有j-i种可能。 如果将对应于mij的断开位置k记录到sij中，最可以得到最优解。,3.1 矩阵连乘问题,3、计算最优值 我们采用动态规划法从底向上的方式进行计算。在计算过程中，保存已经解决的子问题答案。保证每个子问题只计算一次，下次需要的时候查表就可以了。,3.1 矩阵连乘问题,void MatrixChain(int *p, int n, int *m, int *s) 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;kj;k+) int t=mik+mk+1j+pi-1*pk*pj; if(tmij) mij=t;sij=k; ,3.1 矩阵连乘问题,c 时间、空间复杂性分析 这个算法的时间主要取决于r，i和k的三重循环。循环体内的计算两位O(1)，而三重循环的总次数O(n3)，所以该算法的时间复杂性为O(n3)。空间复杂性O(n2)。,3.1 矩阵连乘问题,4、构造最优解 第三步只是计算了最优值（最少的数乘次数），但是没有给出最优解。但实在sij中记录了矩阵Aij的最佳方式应在Ak和Ak+1之间断开，即(Ai:k)(Ak+1:j)。以次类推下去，最后就可以获得该问题的最优解。,3.1 矩阵连乘问题,void Traceback(int i, int j, int *s) if(i=j) return; Traceback(i,sij,s); Traceback(sij+1,j,s); cout“Multiply A”i“,”sij; cout“and A”(sij+1)“,”jendl; ,3.2 动态规划算法的基本要素,从计算矩阵连乘的动态规划法可以看出，该算法的有效性依赖于问题本身所具有的两个特性：最优子结构和子问题重叠性质。 我们在判断一个问题是否可以利用动态规划法求解的时候需要考察这两个方面。,3.2 动态规划算法的基本要素,最优子结构 我们在动态规划法的第一步通常需要刻画最优解的结构。当问题的最优解包括了子问题的最优解时，称该问题具有最优子结构性质。一般证明的方法：假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可以构造出比原问题最优解根好的解，导致矛盾。,3.2 动态规划算法的基本要素,重叠问题 在用递归算法自顶向下求解的过程中，有些子问题不是新问题，而是不断的反复求解。动态规划法就是利用这个性质来减少子问题求解的次数。动态规划算法通常指需要多项式时间，从而提高了解题的效率。,3.2 动态规划算法的基本要素,int RecurMatrixChain(int i,int j) if(i=j) return 0; int u=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j) +pi-1*pi*pj; sij=i; for(int k=i+1;kj;k+) int t=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j) +pi-1*pk*pj; if(tu) u=t;sij=k; return u; ,3.2 动态规划算法的基本要素,重叠问题 假设算法中的判断和赋值语句花费常数时间，因此可以得到： 当时，,3.2 动态规划算法的基本要素,重叠问题 可以看到，直接采用递归的方法时间随n指数增长。相比之下，用动态规划法则只需要O(n3)。所以，在相同子问题反复出现，并且不同子问题的个数又相对较小的情况下，用动态规划算法是非常有效的。,3.2 动态规划算法的基本要素,备忘录算法：动态规划算法的变形。 相同：采用表格来记录已经计算过的子问题。 不同：备忘录采用自顶向下的方式。类似于递归的控制方式，区别在于备忘录为每个求解过的子问题建立备忘录，以便需要的时候查看。,3.2 动态规划算法的基本要素,int LookupChain(int i,int j) if(mij0) 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;kj;k+) int t=LookupChain (i,k)+LookupChain (k+1,j) +pi-1*pk*pj; if(tu) u=t;sij=k; mij=u; return u; ,3.2 动态规划算法的基本要素,通过本节的分析，我们可以看到具有前面介绍的两种基本性质的问题，可以采用自底向上的动态规划法和自顶向下的备忘录法来求解。 对于所有的子问题至少要解一次时，用动态规划法比备忘录法要好。,3.3 最长公共子序列,问题描述： 一个给定序列的子序列：在该序列中删去若干元素后得到的序列。确切的说，若给定序列 则另一个序列 ，是X的子序列是指存在一个严格递增下表序列 使得对于所有j=1,2,k有：zj=xij。例如，序列A=A,B,C,B,D,A,B 的子序列：Z=B,C,D,B。相应的下标为2,3,5,7。,3.3 最长公共子序列,问题描述： 2. 给定序列X和Y，如果序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。我们这节的问题就是求解序列X和Y的最长公共子序列。,3.3 最长公共子序列,最长公共子序列的结构：具有最优子结构性质。 设序列 和 的最长公共子序列 ，则： 若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。 若xmyn且zkxm，且Z是Xm-1和Y的最长公共子序列。 若xmyn且zkyn，且Z是X和Yn-1的最长公共子序列。,3.3 最长公共子序列,子问题的递归结构：子问题重叠 由第一步分析可以看到，我们求解最长公共子序列可以采用如下方法：当xm=yn时，找到Xm-1和Yn-1的最长公共子序列，然后再尾部加上xm (yn)。当xmyn时，必须找到两个子问题，即Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列，选择其中较长的作为X和Y的最长公共子序列。（都要计算的Xm-1和Yn-1最长子序列）,3.3 最长公共子序列,计算最优值 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; ,X=A,B,C,B,D,A,B Y=B,D,C,A,B,A,3.3 最长公共子序列,算法的改进 在LCSLength算法中我们可以通过比较ci-1j与cij-1的值来确定最长公共子序列的取值，从而省略数组b。如：X=A,B,C,B,D,A,B Y=B,D,C,A,B,A c26查表可得： c26=2 第一步：c16=1 c25=2 所以Z=B 取X的最后一位 第二步：c15=1 c24=1 所以Z=A,B 取Y的最后一位 虽然省略了b数组，但是实际上并没有减少空间复杂性，因为c数组仍然是m*n。,3.3 最大子段和,问题描述： 给定由n个整数（可能为负整数）组成的序列a1,a2,an，求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。所以，所求的最优值可以表示成：,3.3 最大子段和,例如： -2，11，-4，13，-5，-2 最优值为： 最优解为：,改进的简单算法： int MaxSum(int n, int *a, int ,显然可以看到这个 算法的时间是O(n2),3.3 最大子段和,最大子段和问题的分治算法： 思路：如果将序列a1:n分成长度相等的两段 a1:n/2 和an/2+1：n，分别求出这两个子段的 最大子段，则a1:n的最大子段和有三种情况： a1:n的最大子段和与a1:n/2的最大子段和相同；,-2，11 ，13 ， -4 ，5，2 -2，11 ， -4 ， 13 ，5，-2 -2，11 ，13 ， -4 ，5，-2,3.3 最大子段和,2. a1:n的最大子段和与an/2+1：n的最大子段和相同； 3. a1:n的最大子段和为 ，且1=i=n/2,n/2+1=j=n。,3.3 最大子段和,最大子段和问题的分治算法： 对于第1、2种情况我们可以递归求解，对于第 3种情况则计算 和 则s1+s2则为第3种情况的最优值。,int MaxSubSum(int *a, int left, int right) int sum=0; if(left=right) sum=aleft0?aleft:0; else int center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int rightsum=MaxSubSum(a, center,right); int s1=0; int lefts=0; for(int i=center;i=left;i+) lefts+=ai; if(leftss1) s1=lefts; int s2=0; int rights=0; for(int i=center+1;is2) s2=rights; if(sumleftsum) sum=leftsum; if(sumrightsum) sum=rightsum; return sum; ,T(n)=O(nlogn),3.3 最大子段和,最大子段和问题的动态规划算法 设 可以得到： 最大子段和的问题可以转化成：,3.3 最大子段和,int MaxSum(int n, int *a) int sum=0,b=0; for(int i=1;i0) b+=ai; else b=ai; if(bsum) sum=b; return sum; ,3.3 最大子段和,最大子段和问题与动态规划算法的推广 最大子矩阵和问题 最大m子段和问题,3.3 最大子矩阵和问题,问题描述：给定一个m行n列的整数矩阵A，试求矩阵A的一个子矩阵，使其各元素之和为最大。 例如：,3.3 最大子矩阵和问题,用二维数组aij存放矩阵。记： 则问题为：,3.3 最大子矩阵和问题,3.3最大m子段和问题,问题描述：给定由n个整数组成的序列a1,a2,an ，以及一个正整数m，确定该序列的m个互不相交子段，使这m个子段的总和最大。,3.3最大m子段和问题,例如： -2，11，-4，13，-5，-2，m=2 最优值为： 最优解为：,3.3最大m子段和问题,设b(i,j)表示数组a前j项中i个子段的最大值，且第i个子段包含aj（1=i=m,i=j=n）。,3.3最大m子段和问题,m=2 -2，11，-1，4，13 -2，11，-4，13,3.3最大m子段和问题,3.10 0-1背包问题,问题描述：给定种物品和一背包。物品的重量是wi，其价值为vi，背包的总容量为c。如何选择装入背包的物品，从而使得装入背包中物品的总价值最大？ 条件：在选择装入的物品的时候，对于每一种物品i只有两种选择，即装入或不装入。不能装入多次，也不可以只装入一部分。,3.10 0-1背包问题,问题的形式化描述：给定c