算法设计与分析_王红梅_第4章 分治法.ppt

算法设计与分析清华大学出版社第4章分治法 概述 递归 排序问题中的分治法 组合问题中的分治法 几何问题中的分治法 实验项目——最近对问题算法设计与分析清华大学出版社 分治法的设计思想 分治法的求解过程算法设计与分析清华大学出版社将一个难以直接解决的大问题,划分成一些规模较小的子问题,以便各个击破,分而治之。更一般地说,将要求解的原问题划分成 k个较小规模的子问题,对这 k个子问题分别求解。如果子问题的规模仍然不够小,则再将每个子问题划分为 k个规模更小的子问题,如此分解下去,直到问题规模足够小,很容易求出其解为止,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。 分治法的设计思想算法设计与分析清华大学出版社 2. 独立子问题:各子问题之间相互独立,这涉及到分治法的效率,如果各子问题不是独立的,则分治法需要重复地解公共的子问题。 1. 平衡子问题:最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的 k个子问题(通常 k=2),这种使子问题规模大致相等的做法是出自一种平衡( Balancing )子问题的思想,它几乎总是比子问题规模不等的做法要好。启发式规则: 算法设计与分析清华大学出版社子问题 1的规模是 n /2 子问题 1的解子问题 2的解子问题 2的规模是 n /2 原问题的解原问题的规模是 n 分治法的典型情况算法设计与分析清华大学出版社 分治法的求解过程一般来说,分治法的求解过程由以下三个阶段组成: (1)划分:既然是分治,当然需要把规模为 n的原问题划分为 k个规模较小的子问题,并尽量使这 k个子问题的规模大致相同。(2)求解子问题:各子问题的解法与原问题的解法通常是相同的,可以用递归的方法求解各个子问题,有时递归处理也可以用循环来实现。(3)合并:把各个子问题的解合并起来,合并的代价因情况不同有很大差异,分治算法的有效性很大程度上依赖于合并的实现。算法设计与分析清华大学出版社例:计算 an,应用分治技术得到如下计算方法: 3 4 3 2 3 2 81 3 1 3 1 9 3 1 3 1 9 3 3 3 3 分解问题求解每个子问题合并子问题的解不是所有的分治法都比简单的蛮力法更有效。分析时间性能???????????1 1 22naa naa nn n如果如果算法设计与分析清华大学出版社 递归 递归的定义 递归函数的运行轨迹 递归函数的内部执行过程算法设计与分析清华大学出版社 递归的定义递归( Recursion )就是子程序(或函数)直接调用自己或通过一系列调用语句间接调用自己,是一种描述问题和解决问题的基本方法。递归有两个基本要素: ⑴边界条件:确定递归到何时终止; ⑵递归模式:大问题是如何分解为小问题的。算法设计与分析清华大学出版社递归函数的经典问题——汉诺塔问题在世界刚被创建的时候有一座钻石宝塔(塔 A),其上有 64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔(塔 B和塔 C)。从世界创始之日起,婆罗门的牧师们就一直在试图把塔 A 上的碟子移动到塔 C上去,其间借助于塔 B的帮助。每次只能移动一个碟子,任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时,世界末日也就到了。