Video在线视频

大家好

这一节我们讲算法设计方法之分治

所谓分治法

就是分而治之

如果待求解的问题比较复杂

就可以把它分割为若干个

较小的子问题来各个击破

以降低问题的复杂性

这就是分治的思想

比如

汽车的设计与制造

就可以分成发动机

车架 底盘 变速箱

悬挂系统

然后分别单独设计制造

最后组装起来

分治法解题一般分为三步

一 分解

也就是将要解决的问题

划分成若干个规模较小的子问题

二 求解

当子问题划分得足够小时

选用恰当的方法解决它

三 合并

按原问题的要求

将子问题的解逐层合并

构成原问题的解

分治法在设计搜索引擎

解决巨量数据的排序等问题中

得到了广泛的应用

在科学计算领域

有时候会面对非常巨大的计算任务

又希望在很短很短的时间内完成计算

在这种情况下

靠一台计算机来计算

显然满足不了要求

这个时候分治法就可以派上用场了

比如

两个非常巨大的矩阵相乘

可以先对矩阵进行分解

然后把子任务分解到

若干台计算机上进行计算

最后再把计算结果收集合并起来

比如

假定俩个巨大的矩阵A和B

他们都是N阶方阵

所谓N阶方阵

也就是由N行跟N列组成的矩阵

在这里

N是一个非常大的整数

大到一台计算机存放不下矩阵A或者B

现在要计算它们的乘积C＝A×B

我们知道

两个矩阵相乘

结果也是一个矩阵

现在要求矩阵C

就要计算出矩阵C中的

每一个元素Cnm

这就是Cnm的计算式

如果我们把它展开

就得到这么一个式子

也就是说

做上面的计算要扫描矩阵A中

第n行的所有元素

以及矩阵B中第m列的所有元素

如果一台计算机存不下这么一个矩阵

事情就变得很麻烦

好了

让我们看看用分治法怎么做

首先

假定我们用10台计算机来计算

可把矩阵A

按行拆成10个小的矩阵

分别是A1 A2一直到A10

每一个有N除以10行这么大

就像这样

然后

分别计算每个小矩阵

A1 A2一直到A10

和B的乘积

为了不失一般性

以A1为例来说明

对应的C1中的每一个元素

可按这个式子来计算

这样

就在第一台计算机上

计算出C矩阵中前十分之一的元素

同样道理

可以在第二台

第三台

一直到第十台计算机上

计算出其他元素

当然

细心的读者应该发现了

矩阵B也和矩阵A一样大

一台计算机同样存不下

不过没有关系

我们同样可以按列切分矩阵B

使得每台计算机

只存放矩阵B的十分之一

上述公式可以直接使用

只是这一回只完成了C1的十分之一

这样一来

就需要100台计算机

而不是原来的10台了

这个图

就是第一台计算机的工作

被分配到10台计算机中

这是其中的第五台

要完成的计算任务

于是

在单机上无法求解的大问题

就被分解成多个小问题来解决

我们再看一个简单的例子

给你一个装有16个硬币的袋子

这16个硬币中有一个是假币

并且这个假币比真币要轻一些

请你找出这个假币

为了完成这么一个任务

可以提供一台

用来比较两组硬币重量的仪器

利用这台仪器

可以知道两组硬币的重量是否相同

我们用分治法来求解这个问题

假如把16个硬币看成一个大的问题

要做的第一步

就是随机选择8个硬币作为第一组

不妨称为A组

剩下的8个硬币作为第二组

不妨称之为B组

这样

就把1 6个硬币的问题分解成

两个8个硬币的问题来解决

第二步

假如两组硬币重量相等

则可以判断假币不存在

假如两组硬币重量不相等

则肯定存在假币

并且可以判断它位于

较轻的那一组硬币之中

不妨假定B组是较轻的那一组

我们再把它分成两组

每组就有4个硬币

称其中一组为B1

另一组为B2

比较这两组

肯定有一组轻一些

如果B1轻

则假币肯定在B1之中

再将B1又分成两组

每组就只剩两个硬币了

不妨称其中一组为B11

另一组为B12

比较这两组

可以得到一个较轻的组

由于这个组只剩两个硬币

因此不必再细分

比较这两个硬币的重量

可以立即知道哪一个硬币轻一些

较轻的硬币就是我们要找的假币

这就是算法设计

里面经常用到的分治法

大家应该不难理解

好

这一节就到这

谢谢大家