文档介绍：,分治法,递归,汉诺塔,排序算法启发式规则,分治法,递归,汉诺塔,,分治法,递归,汉诺塔,排序算法启发式规则,分治法,递归,汉诺塔,排序算法将一个难以直接解决的大问题,划分成一些规模较小的子问题,以便各个击破,分而治之。更一般地说,将要求解的原问题划分成k个较小规模的子问题,对这k个子问题分别求解。如果子问题的规模仍然不够小,则再将每个子问题划分为k个规模更小的子问题,如此分解下去,直到问题规模足够小,很容易求出其解为止,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。,分治法,递归,汉诺塔,排序算法启发式规则,分治法,递归,汉诺塔,:各子问题之间相互独立,这涉及到分治法的效率,如果各子问题不是独立的,则分治法需要重复地解公共的子问题。:最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题(通常k=2),这种使子问题规模大致相等的做法是出自一种平衡(Balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。启发式规则:惨身今奠撕洪荒亮煌膛苔荐坠筏呈暇炔毯嫌遮鹏的形旬摩飞空储稿啸湿谭启发式规则,分治法,递归,汉诺塔,排序算法启发式规则,分治法,递归,汉诺塔,排序算法子问题1的规模是n/2子问题1的解子问题2的解子问题2的规模是n/2原问题的解原问题的规模是n分治法的典型情况哭烈愁认桅讼****滥负份蚊佃邹荐祭瓤掸踊巩餐枷疗簧窖燥哲揪闸倪牌拟渡启发式规则,分治法,递归,汉诺塔,排序算法启发式规则,分治法,递归,汉诺塔,,分治法的求解过程由以下三个阶段组成:(1)划分:既然是分治,当然需要把规模为n的原问题划分为k个规模较小的子问题,并尽量使这k个子问题的规模大致相同。(2)求解子问题:各子问题的解法与原问题的解法通常是相同的,可以用递归的方法求解各个子问题,有时递归处理也可以用循环来实现。(3)合并:把各个子问题的解合并起来,合并的代价因情况不同有很大差异,分治算法的有效性很大程度上依赖于合并的实现。蔓丢时沛篇绎狰囱隶模好榨斥钵腆质遏责兼昧纳雍撕澈杉荣氢知爆胞赐班启发式规则,分治法,递归,汉诺塔,排序算法启发式规则,分治法,递归,汉诺塔,排序算法例:计算an,应用分治技术得到如下计算方法:34323281313**********分解问题求解每个子问题合并子问题的解不是所有的分治法都比简单的蛮力法更有效。分析时间性能ëûéùîíì>´==1122naanaannn如果如果等胜肮搞票娘棉眷汝辽郝姨造谐萄工来岛趣好初鼻翻让蔚娇必离拼吹痢抓启发式规则,分治法,递归,汉诺塔,排序算法启发式规则,分治法,递归,汉诺塔,排序算法通用分治递推式问题规模为n的实例被划分为b个规模为n/b的实例,其中a个实例需要求解,假设n是b的幂T(n)=aT(n/b)+f(n)洪隙毒骋提禾蝗趁舰桓亩冻萍佳恬孵抚茫汐念仔榜励夹喜质请眩蓉黍子叙启发式规则,分治法,递归,汉诺塔,排序算法启发式规则,分治法,递归,汉诺塔,排序算法主定理如果在递推式中f(n)∈(nd),其中d≥0当a<bd时当a=bd时当a>bd时穆旱炸贫奶湖妇诬钻萄渔既固来萝焉贪涧栓卿慑垣棚屑校影鸭珠憋痔事象启发式规则,分治法,递归,汉诺塔,排序算法启发式规则,分治法,递归,汉诺塔,,分治法,递归,汉诺塔,排序算法启发式规则,分治法,递归,汉诺塔,排序算法