信息学竞赛之分治算法.doc资源-CSDN文库

版权申诉

文档资料

136 浏览量 2022-05-06 10:59:59 上传评论收藏 196KB DOC 举报

资源推荐

资源详情

资源评论

信息学竞赛必备算法系列

分治算法

君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计

过程中。本章将首先介绍怎样在算法设计领域应用这一古老的策略，然后将利用这一策略

解决如下问题：最小最大问题、矩阵乘法、残缺棋盘、排序、选择和一个计算几何问题—

—找出二维空间中距离最近的两个点。

本章给出了用来分析分而治之算法复杂性的数学方法，并通过推导最小最大问题和排

序问题的复杂性下限来证明分而治之算法对于求解这两种问题是最优的（因为算法的复杂

性与下限一致）。



1 算法思想



分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1)

把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起

来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来

解决。

例 2-1 [找出伪币] 给你一个装有 1 6 个硬币的袋子。1 6 个硬币中有一个是伪造的，

并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你

完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两

组硬币的重量是否相同。比较硬币 1 与硬币 2 的重量。假如硬币 1 比硬币 2 轻，则硬币 1

是伪造的；假如硬币 2 比硬币 1 轻，则硬币 2 是伪造的。这样就完成了任务。假如两硬币

重量相等，则比较硬币 3 和硬币 4。同样，假如有一个硬币轻一些，则寻找伪币的任务完

成。假如两硬币重量相等，则继续比较硬币 5 和硬币 6。按照这种方式，可以最多通过 8

次比较来判断伪币的存在并找出这一伪币。

另外一种方法就是利用分而治之方法。假如把 1 6 硬币的例子看成一个大的问题。第

一步，把这一问题分成两个小问题。随机选择 8 个硬币作为第一组称为 A 组，剩下的 8 个

硬币作为第二组称为 B 组。这样，就把 1 6 个硬币的问题分成两个 8 硬币的问题来解决。

第二步，判断 A 和 B 组中是否有伪币。可以利用仪器来比较 A 组硬币和 B 组硬币的重量。

假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，

并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先

1 6 个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论 A 组还是 B

组中有伪币，都可以推断这 1 6 个硬币中存在伪币。因此，仅仅通过一次重量的比较，就

可以判断伪币是否存在。

现在假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注

意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬

币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6 硬币的问题就被

分为两个 8 硬币（A 组和 B 组）的问题。通过比较这两组硬币的重量，可以判断伪币是否

存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设 B 是轻

的那一组，因此再把它分成两组，每组有 4 个硬币。称其中一组为 B1，另一组为 B2。比

较这两组，肯定有一组轻一些。如果 B1 轻，则伪币在 B1 中，再将 B1 又分成两组，每组

有两个硬币，称其中一组为 B1a，另一组为 B1b。比较这两组，可以得到一个较轻的组。

由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪

一个硬币轻一些。较轻的硬币就是所要找的伪币。

例 2-2 [金块问题] 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现

信息学竞赛必备算法系列

分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员

将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得

到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个

月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次

数找出最轻和最重的金块。

假设袋中有 n 个金块。可以用函数 M a x（程序 1 - 3 1）通过 n-1 次比较找到最重的

金块。找到最重的金块后，可以从余下的 n-1 个金块中用类似的方法通过 n-2 次比较找出

最轻的金块。这样，比较的总次数为 2n-3。程序 2 - 2 6 和 2 - 2 7 是另外两种方法，前

者需要进行 2n-2 次比较，后者最多需要进行 2n-2 次比较。

下面用分而治之方法对这个问题进行求解。当 n 很小时，比如说， n≤2，识别出最重

和最轻的金块，一次比较就足够了。当 n 较大时（n＞2），第一步，把这袋金块平分成两

个小袋 A 和 B。第二步，分别找出在 A 和 B 中最重和最轻的金块。设 A 中最重和最轻的金

块分别为 HA 与 LA，以此类推，B 中最重和最轻的金块分别为 HB 和 LB。第三步，通过

比较 HA 和 HB，可以找到所有金块中最重的；通过比较 LA 和 LB，可以找到所有金块中

最轻的。在第二步中，若 n＞2，则递归地应用分而治之方法。

假设 n= 8。这个袋子被平分为各有 4 个金块的两个袋子 A 和 B。为了在 A 中找出最

重和最轻的金块，A 中的 4 个金块被分成两组 A1 和 A2。每一组有两个金块，可以用一次

比较在 A 中找出较重的金块 HA1 和较轻的金块 LA1。经过另外一次比较，又能找出 HA 2

和 LA 2。现在通过比较 HA1 和 HA2，能找出 HA；通过 LA 1 和 LA2 的比较找出 LA。这

样，通过 4 次比较可以找到 HA 和 LA。同样需要另外 4 次比较来确定 HB 和 LB。通过比

较 HA 和 HB（LA 和 LB），就能找出所有金块中最重和最轻的。因此，当 n= 8 时，这种

分而治之的方法需要 1 0 次比较。如果使用程序 1 - 3 1，则需要 1 3 次比较。如果使用程

序 2 - 2 6 和 2 - 2 7，则最多需要 1 4 次比较。设 c(n)为使用分而治之方法所需要的比较

次数。为了简便，假设 n 是 2 的幂。当 n= 2 时，c(n) = 1。对于较大的 n，c(n) =

2c(n/ 2 ) + 2。当 n 是 2 的幂时，使用迭代方法（见例 2 - 2 0）可知

c(n) = 3n/ 2 - 2。在本例中，使用分而治之方法比逐个比较的方法少用了 2 5％的比较次

数。

例 2-3 [矩阵乘法] 两个 n×n 阶的矩阵 A 与 B 的乘积是另一个 n×n 阶矩阵 C，C 可

表示为假如每一个 C(i, j) 都用此公式计算，则计算 C 所需要的操作次数为 n3 m+n2 (n-

1) a，其中 m 表示一次乘法，a 表示一次加法或减法。

为了得到两个矩阵相乘的分而治之算法，需要： 1) 定义一个小问题，并指明小问题

是如何进行乘法运算的； 2) 确定如何把一个大的问题划分成较小的问题，并指明如何对

这些较小的问题进行乘法运算； 3) 最后指出如何根据小问题的结果得到大问题的结果。

为了使讨论简便，假设 n 是 2 的幂（也就是说， n 是 1，2，4，8，1 6，.）。

首先，假设 n= 1 时是一个小问题，n> 1 时为一个大问题。后面将根据需要随时修改

这个假设。对于 1×1 阶的小矩阵，可以通过将两矩阵中的两个元素直接相乘而得到结果。

考察一个 n> 1 的大问题。可以将这样的矩阵分成 4 个 n/ 2×n/ 2 阶的矩阵

A1，A2，A3，和 A4。当 n 大于 1 且 n 是 2 的幂时，n/ 2 也是 2 的幂。因此较小矩阵也

满足前面对矩阵大小的假设。矩阵 Bi 和 Ci 的定义与此类似.

根据上述公式，经过 8 次 n/ 2×n/ 2 阶矩阵乘法和 4 次 n/ 2×n/ 2 阶矩阵的加法，就

可以计算出 A 与 B 的乘积。因此，这些公式能帮助我们实现分而治之算法。在算法的第二

步，将递归使用分而治之算法把 8 个小矩阵再细分（见程序 2 - 1 9）。算法的复杂性为

(n3 )，此复杂性与程序 2 - 2 4 直接使用公式（2 - 1）所得到的复杂性是一样的。事实上，

由于矩阵分割和再组合所花费的额外开销，使用分而治之算法得出结果的时间将比用程序

信息学竞赛必备算法系列

2 - 2 4 还要长。

为了得到更快的算法，需要简化矩阵分割和再组合这两个步骤。一种方案是使用 S t r

a s s e n 方法得到 7 个小矩阵。这 7 个小矩阵为矩阵 D, E, ., J，矩阵 D 到 J 可以通过 7 次

矩阵乘法， 6 次矩阵加法，和 4 次矩阵减法计算得出。前述的 4 个小矩阵可以由矩阵 D 到

J 通过 6 次矩阵加法和两次矩阵减法得出.

用上述方案来解决 n= 2 的矩阵乘法。将某矩阵 A 和 B 相乘得结果 C，如下所示：

因为 n> 1，所以将 A、B 两矩阵分别划分为 4 个小矩阵，每个矩阵为 1×1 阶，仅包

含一个元素。1×1 阶矩阵的乘法为小问题，因此可以直接进行运算。利用计算 D～J 的公

式，得：

D= 1（6-8）=-2

E= 4（7-5）= 8

F=（3 + 4）5 = 3 5

G=（1 + 2）8 = 2 4

H=（3-1）（5 + 6）= 2 2

I=（2-4）（7 + 8）=-3 0

J=（1 + 4）（5 + 8）= 6 5

根据以上结果可得：

对于上面这个 2×2 的例子，使用分而治之算法需要 7 次乘法和 1 8 次加/减法运算。

而直接使用公式（2 - 1），则需要 8 次乘法和 7 次加/减法。要想使分而治之算法更快一

些，则一次乘法所花费的时间必须比 11 次加/减法的时间要长。

假定 S t r a s s e n 矩阵分割方案仅用于 n≥8 的矩阵乘法，而对于 n<8 的矩阵乘法

则直接利用公式（2 - 1）进行计算。则 n= 8 时，8×8 矩阵相乘需要 7 次 4×4 矩阵乘法

和 1 8 次 4×4 矩阵加/减法。每次矩阵乘法需花费 6 4m+ 4 8a 次操作，每次矩阵加法或

减法需花费 1 6a 次操作。因此总的操作次数为 7 ( 6 4m+ 4 8a) + 1 8 ( 1 6a) = 4 4

8m+ 6 2 4a。而使用直接计算方法，则需要 5 1 2m+ 4 4 8a 次操作。要使 S t r a s s

e n 方法比直接计算方法快，至少要求 5 1 2-4 4 8 次乘法的开销比 6 2 4-4 4 8 次加/减

法的开销大。或者说一次乘法的开销应该大于近似 2 . 7 5 次加/减法的开销。

假定 n<1 6 的矩阵是一个“小”问题，S t r a s s e n 的分解方案仅仅用于 n≥1 6 的情

况，对于 n<1 6 的矩阵相乘，直接利用公式（ 2 - 1）。则当 n= 1 6 时使用分而治之算

法需要 7 ( 5 1 2m+ 4 4 8a) +1 8 ( 6 4a) = 3 5 8 4m+ 4 2 8 8a 次操作。直接计算

时需要 4 0 9 6m+ 3 8 4 0a 次操作。若一次乘法的开销与一次加/减法的开销相同，则 S

t r a s s e n 方法需要 7 8 7 2 次操作及用于问题分解的额外时间，而直接计算方法则需

要 7 9 3 6 次操作加上程序中执行 f o r 循环以及其他语句所花费的时间。即使直接计算方

法所需要的操作次数比 St r a s s e n 方法少，但由于直接计算方法需要更多的额外开销，

因此它也不见得会比 S t r a s s e n 方法快。

n 的值越大，Strassen 方法与直接计算方法所用的操作次数的差异就越大，因此对于足

够大的 n，Strassen 方法将更快。设 t (n) 表示使用 Strassen 分而治之方法所需的时间。

因为大的矩阵会被递归地分割成小矩阵直到每个矩阵的大小小于或等于 k（k 至少为 8，也

许更大，具体值由计算机的性能决定）. 用迭代方法计算，可得 t(n) = (nl og27 )。因为 l

og27 ≈2 . 8 1，所以与直接计算方法的复杂性(n3 )相比，分而治之矩阵乘法算法有较大

的改进。

注意事项

分而治之方法很自然地导致了递归算法的使用。在许多例子里，这些递归算法在递归

程序中得到了很好的运用。实际上，在许多情况下，所有为了得到一个非递归程序的企图

信息学竞赛必备算法系列

都会导致采用一个模拟递归栈。不过在有些情况下，不使用这样的递归栈而采用一个非递

归程序来完成分而治之算法也是可能的，并且在这种方式下，程序得到结果的速度会比递

归方式更快。解决金块问题的分而治之算法（例 2 - 2）和归并排序方法（ 2 . 3 节）就可

以不利用递归而通过一个非递归程序来更快地完成。

例 2-4 [金块问题] 用例 2 - 2 的算法寻找 8 个金块中最轻和最重金块的工作可以用二

叉树来表示。这棵树的叶子分别表示 8 个金块（a, b,., h)，每个阴影节点表示一个包含其

子树中所有叶子的问题。因此，根节点 A 表示寻找 8 个金块中最轻、最重金块的问题，而

节点 B 表示找出 a,b,c 和 d 这 4 个金块中最轻和最重金块的问题。算法从根节点开始。由

根节点表示的 8 金块问题被划分成由节点 B 和 C 所表示的两个 4 金块问题。在 B 节点，4

金块问题被划分成由 D 和 E 所表示的 2 金块问题。可通过比较金块 a 和 b 哪一个较重来解

决 D 节点所表示的 2 金块问题。在解决了 D 和 E 所表示的问题之后，可以通过比较 D 和 E

中所找到的轻金块和重金块来解决 B 表示的问题。接着在 F，G 和 C 上重复这一过程，最

后解决问题 A。

可以将递归的分而治之算法划分成以下的步骤：

1) 从图 2 - 2 中的二叉树由根至叶的过程中把一个大问题划分成许多个小问题，小问

题的大小为 1 或 2。

2) 比较每个大小为 2 的问题中的金块，确定哪一个较重和哪一个较轻。在节点

D、E、F 和 G 上完成这种比较。大小为 1 的问题中只有一个金块，它既是最轻的金块也是

最重的金块。

3) 对较轻的金块进行比较以确定哪一个金块最轻，对较重的金块进行比较以确定哪一

个金块最重。对于节点 A 到 C 执行这种比较。

根据上述步骤，可以得出程序 1 4 - 1 的非递归代码。该程序用于寻找到数组 w [ 0 :

n - 1 ]中的最小数和最大数，若 n < 1，则程序返回 f a l s e，否则返回 t r u e。

当 n≥1 时，程序 1 4 - 1 给 M i n 和 M a x 置初值以使 w [ M i n ]是最小的重量，w

[ M a x ]为最大的重量。

首先处理 n≤1 的情况。若 n>1 且为奇数，第一个重量 w [ 0 ]将成为最小值和最大值

的候选值，因此将有偶数个重量值 w [ 1 : n - 1 ]参与 f o r 循环。当 n 是偶数时，首先将

两个重量值放在 for 循环外进行比较，较小和较大的重量值分别置为 Min 和 Max，因此也

有偶数个重量值 w[2:n-1]参与 for 循环。

在 for 循环中，外层 if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工

作与前面提到的分而治之算法步骤中的 2) 相对应，而内层的 i f 负责找出较小重量值和较

大重量值中的最小值和

最大值，这个工作对应于 3 )。for 循环将每一对重量值中较小值和较大值分别与当前的最

小值 w [ M i n ]和最大值 w [ M a x ]进行比较，根据比较结果来修改 M i n 和 M a x（如

果必要）。

下面进行复杂性分析。注意到当 n 为偶数时，在 for 循环外部将执行一次比较而在 f o

r 循环内部执行 3 ( n / 2 - 1 )次比较，比较的总次数为 3 n / 2 - 2。当 n 为奇数时，f o r

循环外部没有执行比较，而内部执行了 3(n-1)/2 次比较。因此无论 n 为奇数或偶数，当

n>0 时，比较的总次数为「3n/2ù-2 次。

程序 14-1 找出最小值和最大值的非递归程序

template<class T>

bool MinMax(T w[], int n, T& Min, T& Max)

{// 寻找 w [ 0 : n - 1 ]中的最小和最大值

// 如果少于一个元素，则返回 f a l s e

剩余25页未读，继续阅读

评论收藏

内容反馈

版权申诉

老帽爬新坡

粉丝: 83
资源: 2万+

信息学竞赛之分治算法.doc

信息学竞赛之回溯算法.doc

江苏省信息学竞赛用算法介绍.doc

算法艺术与信息学竞赛.pdf

信息学竞赛之动态规划算法.doc

算法艺术和信息学竞赛

算法艺术与信息学竞赛

部分贪心在信息学竞赛中的应用.doc

浅谈数形结合思想在信息学竞赛中的应用.doc

信息学奥赛一本通-教程PPT课件（第五版）算法部分 第七章 分治算法.pdf

第16届绍兴市少儿信息学竞赛复赛试题.doc

matlab遗传算法学习和全局化算法.doc

第17届绍兴市少儿信息学竞赛复赛试题.doc

密码学与网络安全试题.doc

算法合集之《基本数据结构在信息学竞赛中的应用》.doc

全国中学生生物学竞赛模拟考试题.doc

【老生谈算法】matlab遗传算法学习和全局化算法.doc

最新资源

信息学奥赛一本通-教程PPT课件（第五版）算法部分第七章分治算法.pdf