ch05 基于归纳的算法设计

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第五章,基于归纳的算法设计,1,原理,(1),解决问题的一个小规模事例是可能的,(,基础事例,),(2),每一个问题的解答都可以由更小规模问题的解答构造出来,(,归纳步骤,),。,关键：如何简化问题。,2,多项式求值,问题：给定一串实数,a,n,，,a,n-1,，,，,a,1,，,a,0,，,和一个实数,x,，,计算多项式,P,n,(x,)=a,n,x,n,+a,n-1,x,n-1,+a,1,x+a,0,的值。,归纳假设：已知如何在给定,a,n-1,，,，,a,1,，,a,0,和点,x,的情况下求解多项式,(,即已知如何求解,P,n-1,(x),。,P,n,(x,)= P,n-1,(x)+a,n,x,n,需要,n(n+1)/2,次乘法和,n,次加法运算。,观察：有许多冗余的计算，即,x,的幂被到处计算。,更强的归纳假设：已知如何计算多项式,P,n-1,(x),的值，也知道如何计算,x,n-1,。,计算,x,n,仅需要一次乘法，然后再用一次乘法得到,a,n,x,n,，,最后用一次加法完成计算，总共需要,2n,次乘法和,n,次加法。,3,多项式求值,归纳假设,(,翻转了顺序的,),：已知如何计算,P,/,n-1,(x)=a,n,x,n-1,+a,n-1,x,n-2,+a,1,。,P,n,(x,)=xP,/,n-1,(x)+a,0,。,所以，从,P,/,n-1,(x),计算,P,n,(x,),仅需要一次乘法和一次加法。,该算法仅需要,n,次乘法和,n,次加法，以及一个额外的存储空间。,窍门是很少见的从左到右地考虑问题的输入，而不是直觉上的从右到左。另一个常见的可能是对比自上而下与自下而上,(,当包含一个树结构时,),。,4,最大导出子图,令,G=(V,，,E),是一个无向图。一个,G,的导出子图是一个图,H=(U,，,F),，,满足,U,V,且,U,中两顶点若在,E,中有边则该边也包含在,F,中。,问题：给定一个无向图,G=(V,，,E),和一个整数,k,，,试找到,G,的一个最大规模的导出子图,H=(U,，,F),，,其中,H,中所有顶点的度,k,，,或者说明不存在这样的子图。,解决问题的一个直接方法是把度,k,的顶点删除。当顶点连同它们连接的边一起被删除后，其它顶点的度也可能会减少。当一个顶点的度变成,k,后它也会被删除。但是，删除的次序并不清楚。我们应该首先删除所有度,k,的顶点，然后再处理度减少了的顶点呢？还是应该先删除一个度,k,的顶点，然后继续处理剩下受影响的顶点？,5,最大导出子图,任何度,k,的顶点都可以被删除。删除的次序并不重要。这种删除是必须的，而删除后剩下的图必定是最大的,6,寻找一对一映射,问题：给定一个集合,A,和一个从,A,到自身的映射,f,，,寻找一个元素个数最多的子集,S,A,，,S,满足：,(1) f,把,S,中的每一个元素映射到,S,中的另一元素,(,即，,f,把,S,映射到它自身,),，,(2) S,中没有两个元素映射到相同的元素,(,即，,f,在,S,上是一个一对一函数,),。,7,寻找一对一映射,归纳假设：对于包含,n-1,个元素的集合，如何求解问题是已知的。,假定有一个包含,n,个元素的集合,A,，,并且要寻找一个满足问题条件的子集。我们断言，任何没有被其它元素映射到的元素,i,，,不可能属于,S,。,否则，如果,i,S,且,S,有,k,个元素，则这,k,个元素映射到至多,k-1,个元素上，从而这个映射不可能是一对一的。如果存在这样的一个,i,，,则我们简单地把它从集合中删除。现在我们得到集合,A,/,=A-i,，,其元素个数为,n-1,，,f,作在上面；由归纳假设，我们已知对,A,/,如何求解。如果不存在这样的一个,i,，,则映射是一对一的，即为所求，结束。,8,映射算法,Algorithm Mapping(f,n),Input: f (an array of integers whose values are between 1 to n),Output: S (a subset of the integers from 1 to n, such that f is one-to-one on S),begin,S:=A; A is the set of numbers from 1 to n,for j:=1 to n do cj:=0;,for j:=1 to n do increment cfj;,for j:=1 to n do,if cj=0 then put j in Queue;,while Queue is not empty,remove i from the top of the queue;,S:=S-i;,decrement cfi;,if cfi=0 then put fi in Queue,end,总共的步骤数是,O(n),9,社会名流问题,在,n,个人中，一个被所有人知道但却不知道别人的人，被定义为社会名流。,最坏情况下可能需要问,n(n-1),个问题。,问题：给定一个,n,n,邻接矩阵，确定是否存在一个,i,，,其满足在第,i,列所有项,(,除了第,ii,项,),都为,1,，并且第,i,行所有项,(,除了第,ii,项,),都为,0,。,10,社会名流问题,考察,n-1,个人和,n,个人问题的不同。由归纳法，我们假定能够在,n-1,个人中找到社会名流。由于至多只有一个社会名流，所以有三种可能：,(1),社会名流在最初的,n-1,人中，,(2),社会名流是第,n,个人，,(3),没有社会名流。但仍有可能需要,n(n-1),次提问,“倒推”考虑问题。确定一个社会名流可能很难，但是确定某人不是社会名流可能会容易些。如果我们把某人排除在考虑之外，则问题规模从,n,减小到,n-1,。,算法如下：问,A,是否知道,B,，,并根据答案删除,A,或者,B,。,假定删除的是,A,。,则由归纳法在剩下的,n-1,个人中找到一个社会名流。如果没有社会名流，算法就终止；否则，我们检测,A,是否知道此社会名流，而此社会名流是否不知道,A,。,11,Algorithm Celebrity(Know),Input: Know (an n*n Boolean matrix),Output: celebrity,begin,i=1;,j=2;,next=3;,in the first phase we eliminate all but one candidate,while next=n+1 do,if Knowi,j then i=next,else j=next;,next=next+1;,if i=n+1 then candidate=j,else candidate=i,now we check that the candidate is indeed the celebrity,wrong:=false;,k=1;,Knowcandidate,candidate=false;,while not wrong and k=n do,if Knowcandidate,k then wrong=true;,if not Knowk,candidate then,if candidate!=k then wrong=true;,k=k+1;,if not wrong then celebrity=candidate,else celebrity=0,end,算法被分为两个阶段：,1,）通过消除只留下一个候选者，,2,）检查这个候选者是否就是社会名流。,至多要询问,3(n-1),个问题：,第一阶段的,n-1,个问题用于消除,n-1,个人，,而为了验证侯选者就是社会名流至多要,2(n-1),个问题。,12,一个分治算法：轮廓问题,问题：给定城市里几座矩形建筑的外形和位置，画出这些建筑的,(,两维,),轮廓，并消去隐藏线。,建筑,B,i,通过三元组,(L,i,，,H,i,，,R,i,),来表示。,L,i,和,R,i,分别表示建筑的左右,x,坐标，而,H,i,表示建筑的高度。一个轮廓是一列,x,坐标以及与它们相连的高度，按照从左到右排列。,直接方法：每次加一个建筑，求出新的轮廓线，但总的步数为,O(n2),13,一个分治算法：轮廓问题,分治算法后的关键思想是：在最坏情况下，把一栋建筑与已有轮廓合并只需要线性的时间，并且两个不同轮廓合并也只需要线性的时间。,使用类似于把一栋建筑与已有轮廓合并的算法，就能够把两个轮廓合并。我们从左到右同时扫描两个轮廓，匹配,x,坐标，并在需要时调整高度。这个合并可以在线性时间内完成，因此在最坏情况下完整的算法运行时间是,O(nlogn,),。,14,在二叉树中计算平衡因子,令,T,是一个根为,r,的二叉树。节点,v,的高度是,v,和树下方最远叶子的距离。节点,v,的平衡因子被定义成它的左子树的高度与右子树的高度的差,问题：给定一个,n,个节点的二叉树,T,，,计算它的所有节点的平衡因子,归纳假设：我们已知如何计算节点数,n,的二叉树的全部节点的平衡因子。,然而，根的平衡因子，并不依赖于它的儿子的平衡因子，而是依赖于它们的高度。,更强的归纳假设：已知如何计算节点数,n,的二叉树的全部节点的平衡因子和高度。,15,寻找最大连续子序列,问题：给定实数序列,x,1,，,x,2,，,，,x,n,(,不需要是正数,),，寻找连续子序列,x,i,，,x,i+1,，,，,x,j,，,使得其数值之和在所有的连续子序列数值之和中为最大。称这个子序列为最大子序列。,归纳假设：已知如何找到规模,1,的序列,S=(x,1,，,x,2,，,，,x,n,),。,由归纳假设已知如何在,S,/,=(x,1,，,x,2,，,，,x,n-1,),中找到最大子序列。如果其最大子序列为空，则,S,/,中所有的数值为负数，我们仅需考察,x,n,。,假设通过归纳法在,S,/,中找到的最大子序列是,S,/,M,=(x,i,，,x,i+1,，,，,x,j,),，,1,i,j,n-1,。,如果,j=n-1(,即最大子序列是,S,/,后缀,),，则容易把这个解扩展到,S,中：若,X,n,是正数，则把它加到,S,/,M,中；否则，,S,/,M,仍是最大子序列。如果,jn-1,，,则或者,S,/,M,仍是最大，或者存在另一个子序列，它在,S,/,中不是最大，但在增加了,x,n,的,S,中是最大者。,16,更强的归纳假设：已知如何找到规模,Global_max then,Suffix_Max:=Suffix_Max+xi;,Global_Max:=Suffix_Max,else if xi+Suffix_Max0 then,Suffix_Max:=xi+Suffix_Max,else Suffix_Max:=0,end,18,增强归纳假设,当试图用归纳方式证明时，我们经常遇到以下情节：用,P,来表示定理，归纳假设可以用,P(n),表示，而证明必须推导出,P(n),，即,P(n),P(n),。,在许多情况下，我们可以增加另一个假设，称之为,Q,，,从而使证明变得容易，即证明,P and Q(n),P(n),比证明,P(n),P(n),容易,在使用这个技巧时，人们最易犯的错误是增加的额外假设本身必须也有相应的证明。换句话说，当他们证明,P and Q(=0 then,if Pi-1,k-Si.exist then,Pi,k.exist:=true;,Pi,k.belong:=true;,end,22,常见错误,与已经讨论的归纳证明的常见错误类似。例如，忘记了基础情形是比较常见的。在递归过程中，基础情形对于终止递归是必需的。另一常见错误是，把对于,n,的解扩展到问题对于,n+1,时的一个特定实例的解，而不是对于任意实例。无意识的改变假设是另一个常见错误。,23,小结,通过把问题的一个实例归约到一个或多个较小规模的实例，可以使用归纳原理来设计算法。如果归约总是能实现，并且基础情形可以被解决，则算法可通过归纳进行设计。因此，主要的思想是如何归约问题，而不是直接对问题求解。,把问题规模减小的一种最容易的方法是去除问题中的某些元素。这个技术应该是处理问题首要手段，可以有许多不同的方式，除了简单地去除元素外，把两个元素合并为一个也是可能的，或者找到一个在特定,(,容易,),情况下可以处理的元素，或者引入一个新元素来取代原来的两个或几个元素。,可以用多种方式来归约问题的规模。然而，不是所有的归约都有同样的效率，因此要考虑所有归约的可能性，特别是考虑不同的归纳次序。,24,小结,减小问题规模的一个最有效的方法是把它分成两个,(,或多个,),相等规模的部分。如果问题可以被分割，则分治法非常有效，其中子问题的输出可以容易地生成全问题的输出。,由于归约只能改变问题的规模，并不改变问题本身，所以应该寻找尽可能独立的小规模的子问题。,有一种方法来克服归约问题必须与原始问题一致的局限：改变问题的描述。这是一个经常使用的非常重要的方法，有时候，它比削弱假设要好，可获得一个较弱的算法并作为完整算法中的一个步骤来使用。,这些技术可以同时一起使用，或者作不同的组合。,25,