算法设计与问题求解PPT课件（共8单元）-4-DivideAndConquer.pptxVIP

算法分析与设计引子治国孙子兵法“凡治众如治寡，分数是也 ”引子齐家引子治国齐家编算个整数的排序 一个地图个点，找出最近两个点1PB的网页文本中进行关键字统计分治算法基本思想分 — 将大规模的原问题分割成 k 个更小规模的 子问题，如果子问题的规模仍然不够小，则再划分为 k 个“子 子”问题，如此递归地进行下去，直到子问题规模足够小（基础问题），很容易求出其解为止。原问题子问题子问题子问题 ……………………… 分治算法基本思想治 — 求解规模足够小的基础问题。原问题子问题子问题子问题 ………………………√√√√√√√√√√√√√√√√√√√√√√√√分治算法基本思想合 — 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。√√√√√√√√√√√√√√√√√√√√√√√√√√√√√………………………√√√√√√√√分治算法基本思想分治策略算法细分为三个阶段： Divide 、 Conquer 、 Combine 。 Divide 阶段是把原问题分割成小问题， Conquer 阶段是递归处理流程， Combine 阶段是运用小问题的答案合成出原问题的解答。“分治合”策略√CombineConquerDivide√√√√√√分治策略框架程序(1) if ( | P | = n0) adhoc(P); //递归出口，用特定程序解决基础问题(2) divide P into smaller subinstances P1,P2,...,Pk；//分解出子问题(3) for (i = 1, i = k, i++) yi = divide-and-conquer(Pi); //递归求解各子问题(4) return merge(y1,...,yk); //将各子问题的解合并为原问题的解 }divide-and-conquer(P){?|P|表示问题P的规模，是一个预先定义的阈值，表示当问题P的规模不超过时，问题已容易求解，不必要继续分解和递归调用。adhoc(P)是分治算法中的子程序，对应治过程（或者说conquer），一般是常数时间复杂度的子函数或者子过程。分治策略框架程序(1) if ( | P | = n0) adhoc(P); //递归出口，用特定程序解决基础问题(2)divide P into smaller subinstances P1,P2,...,Pk；//分解出子问题(3) for (i = 1, i = k, i++) yi = divide-and-conquer(Pi); //递归求解各子问题(4) return merge(y1,...,yk); //将各子问题的解合并为原问题的解 }divide-and-conquer(P){设计划分策略，把原问题P分解成k个规模较小的子问题，这个步骤是分治算法的基础和关键，人们往往遵循两个原则：平衡子问题原则，分割出的k个子问题其规模最好大致相当；独立子问题原则，分割出的k个子问题之间重叠越少越好，最好k个子问题是相互独立，不存在重叠子问题。分治策略基本原理(1) if ( | P | = n0) adhoc(P); //递归出口，用特定程序解决基础问题(2) divide P into smaller subinstances P1,P2,...,Pk；//分解出子问题(3) for (i = 1, i = k, i++) yi = divide-and-conquer(Pi); //递归求解各子问题(4) return merge(y1,...,yk); //将各子问题的解合并为原问题的解 }divide-and-conquer(P){merge合并子程序，把k个子问题的解合并得到原问题的解。合并子程序因求解问题而异，即使是同一个问题，如果第二步的划分策略不同，其合并子程序也往往不一样。分治策略算法框架(1) if ( | P | = n0) adhoc(P); //递归出口，用特定程序解决基础问题(2) divide P into smaller subinstances P1,P2,...,Pk；//分解出子问题(3) for (i = 1, i = k, i++) yi = divide-and-conquer(Pi); //递归求解各子问题(4) return merge(y1,...,yk); //将各子问题的解合并为原问题的解 }divide-and-conquer(P){?假设：Adh