第4章分治法 “分”而治之
第4章 分治法 —— “分”而治之
主要内容 般方法 2.二分检索 3.找最大和最小元素 4.归并分类 5.快速分类 6.选择问题 7.斯特拉森矩阵乘法
主要内容 1. 一般方法 2. 二分检索 3. 找最大和最小元素 4. 归并分类 5. 快速分类 6. 选择问题 7. 斯特拉森矩阵乘法
31一般方法 令对大规模问题的求解 利用分治法求解大规模问题 1.基本思想 分而治之方法与软件设计的模块化方法非常相似。 为解决一个大问题,可以(1)把它分解成两个或多个 更小的问题;(2)分别解决每个小问题;(3)把各 小问题的解答组合起来,即可得到原问题的解。 小问题通常与原问题相似或同质,因而可以递归地 使用分而治之策略解决
❖ 对大规模问题的求解 ❖ 利用分治法求解大规模问题 1.基本思想 分而治之方法与软件设计的模块化方法非常相似。 为解决一个大问题，可以（1）把它分解成两个或多个 更小的问题；（2）分别解决每个小问题；（3）把各 小问题的解答组合起来，即可得到原问题的解。 小问题通常与原问题相似或同质 ，因而可以递归地 使用分而治之策略解决。 3.1 一般方法
逐步细化的过程 /子问题 /子问题求解 al 问题 子结果 q2 12 A 分解 合并 k k 通常,子问题与原始问题“同质
Q q2 qk q1 子问题 ... a2 ak a1 子问题求解 ... 问题 A 子结果 分解 合并 逐步细化的过程 通常，子问题与原始问题“同质
例1找伪币]假设16枚金币中有一枚是伪造的,真假金 币的区别仅是重量不同,利用一个没有砝码的天平作工具, 找出这枚伪造的金币 例2[金块问题]有一个老板有一袋金块。每个月将有两 名雇员会因其优异的表现分别被奖励一个金块。按规矩, 排第一的雇员将得到袋中最重的金块,排名第二的雇员 将得到袋中最轻的金块。根据这种方式,除非有新金块 快加入袋中,否则第一名雇员所得到的金块总是比第二 名雇员所得到的金块重,如果有新的金块周期性的加入 袋中,则每个月都必须找出最重和最轻的金块。假设有 台比较重量的仪器,希望用最少的比较次数找出最重 和最轻的金块。 问题的分解策略有多种
例1 [找伪币] 假设16 枚金币中有一枚是伪造的，真假金 币的区别仅是重量不同，利用一个没有砝码的天平作工具， 找出这枚伪造的金币。 例2 [金块问题]有一个老板有一袋金块。每个月将有两 名雇员会因其优异的表现分别被奖励一个金块。按规矩， 排第一的雇员将得到袋中最重的金块，排名第二的雇员 将得到袋中最轻的金块。根据这种方式，除非有新金块 快加入袋中，否则第一名雇员所得到的金块总是比第二 名雇员所得到的金块重，如果有新的金块周期性的加入 袋中，则每个月都必须找出最重和最轻的金块。假设有 一台比较重量的仪器，希望用最少的比较次数找出最重 和最轻的金块。 问题的分解策略有多种
例3[矩阵乘法]两个n×n阶的矩阵A与B的乘积是另 个n×n阶矩阵Cc的元素可表示为 C(,j)=∑A(k)*B(k,),1≤i≤n,1≤j≤n 其时间复杂度为o(n3)。可以采用矩阵分块 乘法降低时间复杂度。 先将A、B分别分割为4个n/2×n2的矩阵, 然后组合 分治法自然导致了递归算法的使用。在许多例子 里,这些递归算法在递归程序中得到了很好的运用
例3 [矩阵乘法]两个n×n阶的矩阵A与B的乘积是另 一个n×n阶矩阵C,C的元素可表示为： C i j A i k B k j i n j n n k = = ( , ) ( , ) * ( , ) ,1 ,1 1 其时间复杂度为O(n3 )。可以采用矩阵分块 乘法降低时间复杂度。 先将A、B分别分割为4个n/2×n/2的矩阵， 然后组合。 分治法自然导致了递归算法的使用。在许多例子 里，这些递归算法在递归程序中得到了很好的运用
2.分治策略的抽象化控制 算法31分治策略的抽象化控制注: procedure DANDC(p, q k=2:二分是最常用的分解策略; global, A(1: n) > SMALL(P,q):布尔函数,判断输入 integer m,p,q;∥1≤p≤q≤n∥ 规模q-p+1是否足够小而无需再进 if SMall(p, q) 步分就可求解; then return(G(p, >G(p,q):对输入规模为qp+1的子问 else 题求解( SMALL(pq为真时); m←DVDE(p,q)∥≤mDVDE(pq):对输入规模为q-p+ 的子问题进一步分解,返回值为[pq] return( COMBINE(DANDC(Pm,区间进一步的分割点( SMALL(p,q DANDO(m+1,q)为假时 endif COMBINE(xy):子结果的合并函数, end dand 将区间[p,m和[m+1,q上的子问题 的解合并成上级区间[p,q]上的“较 完整”的解。当p=1,qn时,就得到 整个问题的解
算法3.1 分治策略的抽象化控制 procedure DANDC(p,q) global n，A(1:n); integer m,p,q; //1≤p≤q≤n// if SMALL(p,q) then return(G(p,q)) else m←DIVIDE(p,q) //p≤m＜q// return(COMBINE(DANDC(p,m), DANDC(m+1,q))) endif end DANDC 注： ➢ k=2: 二分是最常用的分解策略； ➢ SMALL(p,q)：布尔函数，判断输入 规模q-p+1是否足够小而无需再进一 步分就可求解； ➢ G(p,q)：对输入规模为q-p+1的子问 题求解（SMALL(p,q)为真时）； ➢ DIVIDE(p.q)：对输入规模为q-p+1 的子问题进一步分解，返回值为[p,q] 区间进一步的分割点（SMALL(p,q) 为假时； ➢ COMBINE(x,y)：子结果的合并函数， 将区间[p,m]和[m+1,q]上的子问题 的解合并成上级区间[p,q]上的“较 完整”的解。当p=1,q=n时，就得到 整个问题的解。 2. 分治策略的抽象化控制
DANDC的计算时间 若所分成的两个子问题的输入规模大致相等,则 DANDC 总的计算时间可用递归关系式表示,如下: g(n) n足够小 2T(m/2)+fn)否则 注: T(n)}:表示输入规模为η的 DANDO计算时间 g(η):表示对足够小的输入规模直接求解的计算时间 f(m):表示 COMBINE对两个子区间的子结果进行合并 的时间 (该公式针对具体问题有各种不同的变形)
❖ DANDC的计算时间 若所分成的两个子问题的输入规模大致相等，则DANDC 总的计算时间可用递归关系式表示，如下： g(n) n足够小 T(n) = 2T(n/2) + f(n) 否则 注： ➢ T(n)：表示输入规模为n的DANDC计算时间 ➢ g(n)：表示对足够小的输入规模直接求解的计算时间 ➢ f(n)：表示COMBINE对两个子区间的子结果进行合并 的时间 （该公式针对具体问题有各种不同的变形）
分治法的另一种模型表示 &o proc dividandconquer(n) 冷ifn≤= no then g(n) elsei divid n into small suninstances n1 n2n3.nk for j=1 to k do yisdividandconquer(ni) return merge(y1.yk)] end dividandconguer Tn)=G(n)n≤≡n0 kT(n/m)+f(n)n>nO 其中,f(n)是合并各部分解的时间,km均为常数
分治法的另一种模型表示 ❖ proc dividandconquer(n) ❖ if nn0 其中，f(n)是合并各部分解的时间，k,m均为常数
进一步思考 n0选择多大合适? ◆原问题应该分解成几个子问题? 大量实践得出子问题的规模大致相当分治的 效率较好 般进行2分法
进一步思考 ❖ n0选择多大合适？ ❖ 原问题应该分解成几个子问题？ ❖ 大量实践得出子问题的规模大致相当分治的 效率较好。 ❖ 一般进行2分法