递归与分治策略.ppt

1、第二章理解递归和分治策略、学习要点：递归的概念。 掌握为制定有效算法的分散战略。 下面的示例学习分布式策略设置修订技巧： (1)河流动力学技术(2)大整数乘法(3)Strassen矩阵的乘法(4)棋盘的遮挡(5)重新排列和快速重新排列的组合(6)线性时间的选择(7)最近接点对问题(8)联盟计划。 将要求解的大问题分割成k个更小的子问题。 算法整体的思想，n、T(n/2 )、T(n/2 )、T(n/2 )、T(n/2 )、T(n/2 )、T(n )、=、对子问题的规模如果还不小于一盏茶，则进一步分为k个子问题，递归进行直到问题的规模小于一盏茶，容易求出其解为止整个算法的思想，把这k个子问题分开解

2、。 如果子问题的规模还不小于一盏茶，则进一步分为k个子问题，循环进行，直到问题的规模小于一盏茶，容易求出其解为止。 将n、T(n )、=、求出的小规模问题的解合并为一个更大规模的问题的解，从下而上逐次求出原来的问题的解。 整个算法的思想是，把求得的小规模问题的解整合到更大规模的问题的解中，从下而上的阶段求得原来的问题的解。 n、T(n )、=、整个算法的思想，将求出的小问题的解合并为一个更大的问题的解，从下而上依次求出原来的问题的解。 分治法的设定修订思想是，将难以直接解决的大问题，分割成几个规模小的相同问题，分别击破，分割治理。 2.1递归概念，直接或间接调用自身的算法称为递归算法。 用函数

3、本身给出定义的函数称为递归函数。 分治法子问题多为原问题的小模型，使用递归技术方便。 在这种情况下，重复应用分割统治单元，虽然子问题能够与原来的问题类型一致，但是其规模正在缩小，最终能够缩小到容易直接求出子问题的解。 这当然会引起递归的过程。 治愈和递归类似于孪生子的兄弟，经常应用于算法设置修订云同步，从而产生许多高效算法。 来喀呖声，让我们看几个例子。2.1递归概念，例如1阶乘函数阶乘函数递归地是边界条件、递归方程、边界条件和递归方程是递归函数的两个要素，递归函数只具备这些个的两个要素，在有限次校正运算后可得到结果。 2.1递归概念，例如2称为Fibonacci数列无限数列1、1、2、3、5

4、、8、13、21、34、55、Fibonacci数列。 这是递归式的，其中，边界条件、递归方程式、第n个Fibonacci数是int Fibonacci (intn ) if (n=1)返回1； 返回光纤(n-1 )光纤(n-2 )； 2.1递归概念，示例3 Ackerman函数将此函数称为双递归函数(如果函数及其变量是由函数本身定义的)。 Ackerman函数A(n，m )的定义如下：2.1递归概念，例子3 Ackerman函数的前两个例子的函数都能够找到对应的非递归定义：本例子的Ackerman函数不能找到非递归定义。 2.1递归概念为示例3 Ackerman函数A(n，m )的参数m的每

5、个值定义了一个单变量函数：当M=0时，A(n，0)=n 2 M=1时，A(n，1 2 )，2 )=2na (n-1，2，2 )，a (1，2 )=a 2.1递归概念，例如，对于Ackerman函数定义的单变量的Ackerman函数A(n )，A(n)=A(n，n )。 对其伪逆函数(n )进行定义的是(n)=minkA(k)n。 即，(n )是使nA(k )成立的最小的k值。 (n )在复杂度分析中很常见。 对于通常所见的正整数n，存在(n)4。 但是，理论上没有(n )上界，随着n的增加，以无法想象的慢速度趋向正无限大。2.1递归概念，例如4阵列问题递归算法，以生成n个元素r1、r2、rn的

6、全阵列。设R=r1、r2、 rn进行排列的n个元素体、Ri=R-ri。 集合x中元素的全部数组标记为perm(X )。 perm(X )表示在所有数组perm(X )的各个数组之前加上前缀的数组。 可总括地定义r的所有数组：当n=1时，在perm(R)=(r )，其中r是集合r中的唯一元素。 在n1的情况下，perm(R )由(r1)perm(R1)、(r2)perm(R2)、(rn)perm(Rn )构成。 2.1递归概念，例如5整数分割问题，其中正整数n表示为一系列正整数之和： n=n1 n2 nk，其中n1n2nk1，k-1。 这种正整数n的表达被称为正整数n的划分。 求正整数n的不同划

7、分个数。 例如，正整数6有以下11种不同的区分： 6 5 1 42、41 33、321、3111。 22、221、21111。 十一一一。 q (n，m)=q(n，n )和mn。 最大加数n1实际上不能大于n。 因此，q(1，m)=1。 1) q(n，1)=1，n1； 当最大增加数n1等于或小于1时，所有正整数n只有(4) q(n，m)=q(n，m-1) q(n-m，m )和nm1的划分形式。 正整数n的最大增加数n1为m以下的部分由n1=m的部分和n1n-1的部分构成。 3) q(n，n)=1 q(n，n-1 )； 正整数n的划分由n1=n的划分部分和n1n-1的划分部分组成。 在2.1递归

8、概念，例如5个整数分割问题之前的一些示例中，问题本身具有相对明显的递归关系，使得易于在递归函数中直接求解。 在本例子中，当将p(n )设为正整数n的分割数时，难以发现递归关系。因此，可以考虑增加自变量：最大增加数n-1小于等于m的分割数设为q(n，m )。 可以建立q(n，m )的以下递归关系。 在、2.1递归的概念，例子5整数分割问题之前的一些例子中，问题本身具有比较明显的递归关系，所以容易用递归函数直接解。 在本例子中，当将p(n )设为正整数n的分割数时，难以发现递归关系。因此，可以考虑增加自变量：最大增加数n-1小于等于m的分割数设为q(n，m )。 可以建立q(n，m )的以下递归关

9、系。 正整数n的分割数p(n)=q(n，n )。 2.1递归概念，例6 Hanoi塔题设a、b、c为三个塔座。 最初，塔座a上堆积了合订n个圆盘，这些个的圆盘从下到上，从大到小。 各盘从小到大编号为1，2，n，当前要求将该盘在塔基a上的层叠移动到塔基b上并以相同的顺序进行层叠。 移动磁盘时，请遵循以下移动规则。 规则1 :一次只能移动一个磁盘规则2 :不允许随时将大磁盘压在小磁盘上规则3 :在满足移动规则1和2的基础上，可以将磁盘移动到a、b、c中的任意一个塔座。 如果问题的规模很大，很难找到一般的方法，所以尝试使用递归技术来解决这个问题。 n=1时，问题比较简单。 此时，将编号1的圆盘从塔架

10、a直接移动到塔架b即可。 在n-1的情况下，需要利用塔座c作为辅助塔座。 此时，可以按照移动规则将n-1个小圆盘从塔座a移动到塔座c，然后，将剩馀的最大圆盘从塔座a移动到塔座b，最后，按照移动规则将n-1个小圆盘从塔座c移动到塔座b。 因此，n个圆盘的移动问题可以将n-1个圆盘的移动问题分为2次，这可以递归地用上述方法进行。 由此，解决Hanoi塔问题的递推算法可以如下设定、修改。 2.1递归概念，例如，6 Hanoi塔问题，void Hanoi (进入、进入a、进入b、进入c ) if (n0) Hanoi (n-1、a、c )。 移动(a，b )； 汉诺I (n-1，c，b，a )； 递归

11、总结优点：结构清晰，可读性强，数学归纳法上更容易证明算法的精准性，便于设置和修改算法、调试程序。 缺点：递归算法的执行效率低，即使花费校正时间，存储容量也比非递归算法大。 解决方法：在递归算法中删除递归调用，并将其转换为非递归算法。 1 .使用自定义栈内存模拟系统的递归调用工作栈内存。 该方法通用性高，但本质上是递归的，本来只是人工进行了编译程序，最优化的效果不明显。2 .递归地实现递归函数。 3 .可以通过变换将一些递归转换为尾递归以迭代地确定结果。 后两种方法对时空复杂性有很大改进，但其适用范围有限。 递归总结，分治法的适用条件，分治法可以解决的问题一般具有以下特点：这个问题的规模缩小到一

12、定程度就可以很容易解决，这个问题可以分解为几个小规模的相同问题，即这个问题具有最好的子结构性质， 利用该问题分解的子问题的解可以集成到该问题的解中该问题分解的各个子问题是相互独立的，即，在子问题之间不包含共同的子问题。 由于问题的纠正复杂性随着问题规模的增加而增加，所以大多数问题都满足这一特征。 这一特征是适用分治法的前提，可以满足大多数问题，这一特征反映了递归思想的适用，能否利用分治法完全取决于问题是否具有这一特征，具有前两个特征，不具有第三个特征则是贪婪算法和动态修正计划这个特征关系到分治法的效率，如果各个子问题不独立，分治法就会做很多不必要的工作，需要反复解决公共子问题，这种情况下分治法

13、也可以利用，但一般来说还是使用动态修订画比较好。 分配和计数器(p ) if (|p|=n0) ad hoc (p )。 /解决小规模问题dividepintosmallersubinstancesp 1，P2，Pk； /分解问题(i=k，i=k，I ) yi=分配和计数器(pi )； /递归地求解各子问题return merge(y1，yk )。 /将各子问题的解合并到原问题的解、分治法的基本步骤中，从很多实践中可以看出，用分治法设定算法时，希望子问题的规模大致相同。 即，将一个问题分成相同大小的k个子问题的处理方法是有效的。 这种使子问题规模大致相等的做法来自平衡子问题的思想，它几乎总比子问题规模不同的做法好。 分治法的复杂性分析，一个分治法将规模n的问题分为k个规模n