天津科技大学算法设计与分析第4章分治法

《天津科技大学算法设计与分析第4章分治法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章分治法4.1概述4.2递归4.3排序问题中的分治法4.4组合问题中的分治法4.5几何问题中的分治法8/6/20211算法设计与分析--分治法4.1概述4.1.1分治法的设计思想4.1.2分治法的求解过程8/6/20212算法设计与分析--分治法将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。4.1.1分治法的设计思想更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个

2、更大规模的问题的解，自底向上逐步求出原问题的解。8/6/20213算法设计与分析--分治法2.独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。1.平衡子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k＝2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。启发式规则：8/6/20214算法设计与分析--分治法子问题1的规模是n/2子问题1的解子问题2的解子问题2的规模是n/2原问题的解原问题的规模是n分治法的典

3、型情况8/6/20215算法设计与分析--分治法4.1.2分治法的求解过程一般来说，分治法的求解过程由以下三个阶段组成：（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。8/6/20216算法设计与分析--分治法例：计算an，应用分治技术得到如下计算方法：34323281313193

4、13193333分解问题求解每个子问题合并子问题的解不是所有的分治法都比简单的蛮力法更有效。分析时间性能ëûéùîíì>´==1122naanaannn如果如果8/6/20217算法设计与分析--分治法4.2递归4.2.1递归的定义4.2.2递归函数的运行轨迹4.2.3递归函数的内部执行过程8/6/20218算法设计与分析--分治法4.2.1递归的定义递归（Recursion）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。递归的两个基本要素：⑴边界条件：确定递归到何时终止；⑵递归模式：大问题是如何分解为小问题的。递归通常用来

5、解决结构自相似的问题。8/6/20219算法设计与分析--分治法在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。递归函数的经典问题——汉诺塔问题8/6/202110算法设计与分析--分治法三个步骤实现（1）将塔A上的n-1个碟子借助塔C先移到塔B上。（2）把塔A上剩下的一个碟子移到

6、塔C上。（3）将n-1个碟子从塔B借助塔A移到塔C上。显然，这是一个递归求解的过程8/6/202111算法设计与分析--分治法8/6/202112算法设计与分析--分治法算法4.2——汉诺塔算法1voidHanoi(intn,charA,charB,charC)//第一列为语句行号2{3if(n==1)Move(A,C);//Move是一个抽象操作，表示将碟子从A移到C上4else{5Hanoi(n-1,A,C,B);6Move(A,C);7Hanoi(n-1,B,A,C);8}9}C++描述8/6/202113算法设计与分析--分治法4.2.2递归函数的运行轨迹在递归函数中，调

7、用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。采用图示方法描述递归函数的运行轨迹，从中可较直观地了解到各调用层次及其执行情况。8/6/202114算法设计与分析--分治法Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move(A,C)Move(A,B)Hanio(1,C