计算机算法基础(第4章).ppt

2017-2-23 第 4 章分治法——“分”而治之 一般方法?对大规模问题的求解?利用分治法求解大规模问题 。为解决一个大问题,可以(1)把它分解成两个或多个更小的问题;( 2)分别解决每个小问题;( 3)把各小问题的解答组合起来,即可得到原问题的解。小问题通常与原问题相似或同质,因而可以递归地使用分而治之策略解决。 2017-2-23 分而治之的优点和缺点分而治之算法通常包括一个或者多个递归方法的调用, 当这些调用将数据分隔成为独立的集合从而处理较小集合的时候,分而治之的策略将会有很高的效率,而在数据进行分解的时候,分而治之的策略可能会产生大量的重复计算,导致性能的降低分而治之的概念分而治之是使用递归解决问题的算法,技巧是将一个大的复杂的问题划分为多个子问题,而这些子问题可以作为终止条件,或者在一个递归步骤中得到解决,所有子问题的解决结合起来就构成了对原问题的解决 2017-2-23 通常,子问题与原始问题“同质” 2017-2-23 例[找伪币] 假设 16 枚金币中有一枚是伪造的,真假金币的区别仅是重量不同(伪币轻一些),利用一个没有砝码的天平作工具,找出这枚伪造的金币方法 1:比较硬币 1和2的重量,有一个轻则找到; 否则比较硬币 3和4,依次比较下去,直到找到。最多8次比较方法 2:利用分治法。 16 个硬币分为两组,每组 8个, 比较重量,伪币在轻的一组。将轻的一组再分为两组,每组 4个……继续划分下去,依次每组 2个,每组1个,此时找到 2017-2-23 注: ? SMALL(p,q ):布尔函数,判断输入规模 q-p+1 是否足够小而无需再进一步分就可求解; ? G(p,q) :输入规模为 q-p+1 的子问题求解( SMALL(p,q) 为真); ? DIVIDE() :对输入规模为 q-p+1 的子问题进一步分解,返回值为[p,q] 区间进一步的分割点( SMALL(p,q) 不为真时); ? COMBINE(x,y) :子结果的合并函数,将区间[p,m] 和[m+1,q] 上的子问题的解合并成上级区间[p,q] 上的“较完整”的解。当 p=1,q=n 时,得到整个问题的解。 2. 分治策略的抽象化控制算法 分治策略的抽象化控制 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 // BINE(DANDC(p,m), DANDC(m+1,q))) endif end DANDC 2017-2-23 二分检索(折半查找) a 1 , a 2 , …, a n,判定某给定的元素 x是否在该表中?若是,则找出 x在表中的位置并返回其下标?否则,则返回 0 2017-2-23 分治求解策略分析: ?定义问题的形式描述: I=(n, a 1 , a 2 , …,a n ,x) ?问题分解:选取下标 k,由此将 I分解为 3个子问题: I 1 =(k-1, a 1 , a 2 , …,a k-1 ,x) I 2 =(1, a k ,x) I 3 =(n-k, a k+1 , a k+2 , …,a n ,x) ?对于 I 2,若 a k =x ,则有解 k,对 I 1、I 3不用再求解;否则, ?若 x< a k,则只在I 1中求解,对 I 3不用求解; ?若 x> a k,则只在 I 3中求解,对 I 1不用求解; I 1 、I 3上的求解可再次采用分治方法划分后求解(递归过程) 2017-2-23 2. 二分检索算法算法 二分检索 procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low ← 1; high ← n; while low ≤ high do mid ← case :x< A(mid ): high ← mid-1 :x> A(mid ): low ← mid+1 : else:j ← mid ; return endcase