ch05 基于归纳的算法设计.ppt

第五章 基于归纳的算法设计 原理 (1) 解决问题的一个小规模事例是可能的(基础事例) (2) 每一个问题的解答都可以由更小规模问题的解答构造出来(归纳步骤)。 关键：如何简化问题。 多项式求值 问题：给定一串实数an，an-1，…，a1，a0，和一个实数x，计算多项式Pn(x)=anxn+an-1xn-1+…+a1x+a0的值。 归纳假设：已知如何在给定an-1，…，a1，a0和点x的情况下求解多项式(即已知如何求解Pn-1(x))。 Pn(x)= Pn-1(x)+anxn 需要n(n+1)/2次乘法和n次加法运算。 观察：有许多冗余的计算，即x的幂被到处计算。 更强的归纳假设：已知如何计算多项式Pn-1(x)的值，也知道如何计算xn-1。 计算xn仅需要一次乘法，然后再用一次乘法得到anxn，最后用一次加法完成计算，总共需要2n次乘法和n次加法。 多项式求值 归纳假设(翻转了顺序的)：已知如何计算P/n-1(x)=anxn-1+an-1xn-2+…+a1。 Pn(x)=xP/n-1(x)+a0。所以，从P/n-1(x)计算Pn(x)仅需要一次乘法和一次加法。 该算法仅需要n次乘法和n次加法，以及一个额外的存储空间。 窍门是很少见的从左到右地考虑问题的输入，而不是直觉上的从右到左。另一个常见的可能是对比自上而下与自下而上(当包含一个树结构时)。 最大导出子图 令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的顶点，然后继续处理剩下受影响的顶点？ 最大导出子图 任何度k的顶点都可以被删除。删除的次序并不重要。这种删除是必须的，而删除后剩下的图必定是最大的 寻找一对一映射 问题：给定一个集合A和一个从A到自身的映射f，寻找一个元素个数最多的子集S?A，S满足： (1) f把S中的每一个元素映射到S中的另一元素(即，f把S映射到它自身)， (2) S中没有两个元素映射到相同的元素(即，f在S上是一个一对一函数)。 寻找一对一映射 归纳假设：对于包含n-1个元素的集合，如何求解问题是已知的。 假定有一个包含n个元素的集合A，并且要寻找一个满足问题条件的子集。我们断言，任何没有被其它元素映射到的元素i，不可能属于S。否则，如果i?S且S有k个元素，则这k个元素映射到至多k-1个元素上，从而这个映射不可能是一对一的。如果存在这样的一个i，则我们简单地把它从集合中删除。现在我们得到集合A/=A-{i}，其元素个数为n-1，f作在上面；由归纳假设，我们已知对A/如何求解。如果不存在这样的一个i，则映射是一对一的，即为所求，结束。 映射算法 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 c[j]:=0; for j:=1 to n do increment c[f[j]]; for j:=1 to n do if c[j]=0 then put j in Queue; while Queue is not empty remove i from the top of the queue; S:=S-{i}; decrement c[f[i]]; if c[f[i]]=0 then put f[i] in Queue end 社会名流问题 在n个人中，一个被所有人知道但却不知道别人的人，被定义为社会名流。 最坏情况下可能需要问n(n-1)个问题。 问题：给定一个n?n邻接矩阵，确定是否存在一个i，其满足在第i列所有项(除了第ii项)都为1，并且第i行所有项(除了第ii项)都为0。 社会名流问题 考察n-1个人和n个人