《天津科技大学算法设计与分析第4章分治法》由会员分享，可在线阅读，更多相关《天津科技大学算法设计与分析第4章分治法（70页珍藏版）》请在金锄头文库上搜索。
1、2019/2/22,算法设计与分析-分治法,1,第4章 分治法,4.1 概 述,4.2 递 归,4.3 排序问题中的分治法,4.4 组合问题中的分治法,4.5 几何问题中的分治法,2019/2/22,算法设计与分析-分治法,2,4.1 概 述,4.1.1 分治法的设计思想,4.1.2 分治法的求解过程,2019/2/22,算法设计与分析-分治法,3,将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。,4.1.1 分治法的设计思想,更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。,如果子问题的规模仍然不够小，则再将每个子问题划分为k个
2、规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。,2019/2/22,算法设计与分析-分治法,4,2. 独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。,1. 平衡子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。,启发式规则：,2019/2/22,算法设计与分析-分治法,5,
3、分治法的典型情况,2019/2/22,算法设计与分析-分治法,6,4.1.2 分治法的求解过程,一般来说，分治法的求解过程由以下三个阶段组成：,（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。,（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。,（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。,2019/2/22,算法设计与分析-分治法,7,例：计算an，应用分治技术得到如下计算方法：,不是
4、所有的分治法都比简单的蛮力法更有效。,分析时 间性能,2019/2/22,算法设计与分析-分治法,8,4.2 递 归,4.2.1 递归的定义,4.2.2 递归函数的运行轨迹,4.2.3 递归函数的内部执行过程,2019/2/22,算法设计与分析-分治法,9,4.2.1 递归的定义,递归（Recursion）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。,递归的两个基本要素： 边界条件：确定递归到何时终止； 递归模式：大问题是如何分解为小问题的。,递归通常用来解决结构自相似的问题。,2019/2/22,算法设计与分析-分治法,10,在世界刚
5、被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。,递归函数的经典问题汉诺塔问题,2019/2/22,算法设计与分析-分治法,11,三个步骤实现,（1）将塔A上的n-1个碟子借助塔C先移到塔 B上。 （2）把塔A上剩下的一个碟子移到塔C上。 （3）将n-1个碟子从塔B借助塔A移到塔C上。 显然，这是一个递
6、归求解的过程,2019/2/22,算法设计与分析-分治法,12,2019/2/22,算法设计与分析-分治法,13,2019/2/22,算法设计与分析-分治法,14,4.2.2 递归函数的运行轨迹,在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。,反之，退出第i+1层调用应该返回第i层。采用图示方法描述递归函数的运行轨迹，从中可较直观地了解到各调用层次及其执行情况。,2019/2/22,算法设计与分析-分治法,15,Hanio(3,A,B,C),H
7、anio(2,A,C,B),Hanio(1,A,B,C),Move (A,C),Move (A,B),Hanio(1,C,A,B),Move (C,B),Move (A,C),Hanio(2,B,A,C),Hanio(1,B,C,A),Move (B,C),Hanio(1,A,B,C),Move (A,C),Move (B,A),2019/2/22,算法设计与分析-分治法,16,4.2.3 递归函数的内部执行过程,一个递归函数的调用过程类似于多个函数的嵌套调用，只不过调用函数和被调用函数是同一个函数。 为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：,2
8、019/2/22,算法设计与分析-分治法,17,（1）运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址； （2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈； （3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。,2019/2/22,算法设计与分析-分治法,18,汉诺塔算法在执行过程中，工作栈的变化下图所示，其中栈元素的结构为（返回地址，n值，A值，B值，C值），返回地址对应算法中语句的行号。,2019/2/22,算法设计与分析-分治法,19,递归算法结构清晰，可读
9、性强，而且容易用数学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具。 递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。,递归算法的特点,2019/2/22,算法设计与分析-分治法,20,4.3 排序问题中的分治法,4.3.1 归并排序,4.3.2 快速排序,2019/2/22,算法设计与分析-分治法,21,4.3.1 归并排序,二路归并排序的分治策略是： （1）划分：将待排序序列r1, r2, , rn划分为两个长度相等的子序列r1, , rn/2和rn/2
10、1, , rn； （2）求解子问题：分别对这两个子序列进行排序，得到两个有序子序列； （3）合并：将这两个有序子序列合并成一个有序序列。,2019/2/22,算法设计与分析-分治法,22,2019/2/22,算法设计与分析-分治法,23,2019/2/22,算法设计与分析-分治法,24,二路归并排序的合并步的时间复杂性为O(n)，所以，二路归并排序算法存在如下递推式：,根据1.2.4节的主定理，二路归并排序的时间代价是O(nlog2n)。 二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂性为O(n)。,2019/2/22,算法设计与分析-分治法,25,2019/2/
11、22,算法设计与分析-分治法,26,4.3.2 快速排序,（2）求解子问题：分别对划分后的每一个子序列递归处理； （3）合并：由于对子序列r1 ri-1和ri+1 rn的排序是就地进行的，所以合并不需要执行任何操作。,快速排序的分治策略是： （1）划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1 ri-1和ri+1 rn，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；,2019/2/22,算法设计与分析-分治法,27,归并排序按照记录在序列中的位置对序列进行划分， 快速排序按照记录的值对序列进行划分。,2019/2/22,算法设计与分析-
12、分治法,28,以第一个记录作为轴值，对待排序序列进行划分的过程为： （1）初始化：取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；,（2）右侧扫描过程：将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，则j前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序），若ij，则将基准记录与j指向的记录进行交换；,（3）左侧扫描过程：将基准记录与i指向的记录进行比较，如果i指向记录的关键码小，则i后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序），若ij，则将基准记录与i指向的记录交换；,（4）
13、重复（2）（3）步，直到i与j指向同一位置，即基准记录最终的位置。,2019/2/22,算法设计与分析-分治法,29,一次划分示例,2019/2/22,算法设计与分析-分治法,30,2019/2/22,算法设计与分析-分治法,31,以轴值为基准将待排序序列划分为两个子序列后，对每一个子序列分别递归进行排序。,13,27,50,38,49,55,j,i,i,j,13,65,27,50,38,49,55,65,2019/2/22,算法设计与分析-分治法,32,2019/2/22,算法设计与分析-分治法,33,T(n)2 T(n/2)n 2(2T(n/4)n/2)n4T(n/4)2n 4(2T(n/
14、8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n) 因此，时间复杂度为O(nlog2n)。,在最好情况下，每次划分对一个记录定位后，该记录的左侧子序列与右侧子序列的长度相同。在具有n个记录的序列中，一次划分需要对整个待划分序列扫描一遍，则所需时间为O(n)。设T(n)是对n个记录的序列进行排序的时间，每次划分后，正好把待划分区间划分为长度相等的两个子序列，则有：,2019/2/22,算法设计与分析-分治法,34,因此，时间复杂度为O(n2)。,在最坏情况下，待排序记录序列正序或逆序，每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空）。此时，必须经过n
15、-1次递归调用才能把所有记录定位，而且第i趟划分需要经过n-i次关键码的比较才能找到第i个记录的基准位置，因此，总的比较次数为：,2019/2/22,算法设计与分析-分治法,35,在平均情况下，设基准记录的关键码第k小（1kn），则有：,这是快速排序的平均时间性能，可以用归纳法证明，其数量级也为O(nlog2n)。,快速排序的空间复杂性如何?,2019/2/22,算法设计与分析-分治法,36,4.4 组合问题中的分治法,4.4.1 最大子段和问题,4.4.2 棋盘覆盖问题,4.4.3 循环赛日程安排问题,2019/2/22,算法设计与分析-分治法,37,给定由n个整数组成的序列(a1, a2,
16、 , an)，最大子段和问题要求该序列形如 的最大值（1ijn），当序列中所有整数均为负整数时，其最大子段和为0。例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和为：,4.4.1 最大子段和问题,最大子段和问题的分治策略是： （1）划分：按照平衡子问题的原则，将序列(a1, a2, , an)划分成长度相同的两个子序列(a1, , a )和(a 1, , an)，则会出现以下三种情况：,先考虑最大子段和问题的简单算法,2019/2/22,算法设计与分析-分治法,38, a1, , an的最大子段和a1, ,a 的最大子段和； a1, , an的最大子段和a 1, , an的最大子段和； a1, , an的最大子段和 ，且,（2）求解子问题：对于划分阶
