分治法

来自计算思维百科
跳转至: 导航搜索
分治法3.png

分治法(Divide-and-Conquer)是将复杂问题分成若干个与原问题同类型的简单子问题进行解决,然后合并子问题的解得到原问题的解。

基本描述

孙子兵法》曰:用兵之法,十则围之,五则攻之,倍则战之,敌则能分之,少则能逃之,不若则能避之。其意思是:实际作战中运用的原则是:我十倍于敌,就实施围歼,五倍于敌就实施进攻,两倍于敌就要努力战胜敌军,势均力敌则设法分散各个击破。兵力弱于敌人,就避免作战。其中的各个击破是指利用优势兵力将被分割开的敌军一部分一部分消灭,也指将问题逐个解决,或分别逐个击败对方。

分治法(Divide-and-Conquer)的本质即是各个击破、分而治之。它的基本原理是:将一个复杂的问题,分成若干个与原问题同类型的简单子问题进行解决。然后,对子问题的结果进行合并,得到原问题的解。如果子问题还比较大,可反复使用分治算法,直到最后的子问题可以直接求解。分治法中子问题与原问题相同,只是数据不同,也用到了递归思想。

分治策略是解决工作、学习和生活中常见问题的一种方法,被广泛的应用于组织管理和军事等各领域。如某大企业的销售公司,由于其许多产品优质而非常畅销,总部会到各地建立分支机构(子公司),这其中就蕴涵着分治思想。各种大型体育赛事通常分为初赛和决赛,世界杯足球赛要从报名参赛的200多支球队中选出成绩最好的32支球队,难度很大,成本也高。因此通过分区预选赛选出成绩最好的32支球队进入决赛圈,这种做法也包含分治思想并降低了难度和复杂度。

应用

分治法是解决工作、学习和生活中常见的一种方法,被广泛地应用于组织管理和军事等各领域。分治法能解决的问题一般具有以下几个特征:

1.该问题的规模缩小到一定程度就可以容易地解决;

2.该问题可以分解为若干个规模较小的相同问题;

3.利用该问题分解出的子问题的解可以合并为该问题的解;

4.该问题所分解出的各个子问题是相互独立的,子问题之间不包含公共的子问题。

MapReduce的分治思想

谷歌在全球有36个数据中心,服务器不计其数,如此庞大的计算和规模,是很多企业、不可想象的。它的三大核心技术是MapReduce、GFS(Google File System)、BigTable,其中GFS是google公司为了存储海量搜索数据而设计的专用文件系统,BigTable是Google设计的一种用来处理海量数据的非关系型分布式数据库系统,而MapReduce是一个并行计算编程模型,用于海量数据的的并行计。

MapReduce的名字源于这个模型中的两项核心操作:Map(映射)和Reduce(归约)。

可以用这样一个简单例子理解MapReduce。假设一篇文章,共4页,现需要统计其中计算思维和算法两个词出现的次数。可让两个人来做这件事,第一个人统计1、2页,第二人统计3、4,假设统计结果分别是:

1、2页:计算思维:出现5次、算法:出现3次;

3、4页:计算思维:出现3次、算法:出现4次;

最后将两个人的统计结果合并就得到这篇文章的单词出现次数:计算思维:8次、算法:7次。

在这个工作过程中,两个人所做的即是Map的工作,它将一组数据(文章)映射为另一组数据(单词统计);最后的合并操作是Reduce的工作,它对Map的计算结果进行归约,求和、求最大值等。显然,这一过程由划分、治理、合并三个步骤组成,是分治策略的完美应用。

为进一步理解MapReduce,图1给出了MapReduce处理大数据的流程。

                                9.2.5.png                                                                 

                                            图1 MapReduce处理大数据的过程

二分查找

二分查找('Binary Search')是种高效率的查找算法,用于在n个元素的有序序列{ai,i≤i≤n}(假设升序)中查找指定元素e。该算法的思想是:将n个元素分成个数大致相同的两半,取an/2与欲查找的e作比较,如果e=an/2,则找到e,算法终止;如果e<an/2,则只需在数组a的前半部分继续二分查找e;如果x>an/2,则只需在数组a的后半部分继续二分查找e。二分查找每次比较将数据减少一半,也称折半查找。

                           RTENOTITLE

                              图1 二分查找在列表中查找John元素的计算过程
图1给出了二分查找的一个操作实例。假设在初始列表中查找元素John。

第一次查找,初始列表中间元素为Harry,按字典排序小于John,新的查找子表为初始列表的后半部分;第二次查找,第一个子表的中间元素为Larry,大于John,在其前半部分查找John;第三次查找,第二个子表的中间元素为John,找到。

对二分查找,中间元素等于e,找到。但也存在初始列表不含元素e,即找不到的情况。

使用方法及步骤

步骤一:将问题的实例划分为同一个问题的几个较小的实例,最好拥有同样的规模;

步骤二:对这些较小的实例求解(一般使用递归方法,但在问题规模足够小的时候,又是也会利用另一个算法);

步骤三:如果必要的话,合并这些较小问题的解,以得到原始问题的解。

应用案例

应用1-企业销售

案例:某大企业的销售公司,由于其许多产品优质而非常畅销,为了使得销售总额得到提高,总部就会到各地建立分支机构(子公司),这其中就蕴含着分治思想。

应用2-棋盘覆盖小游戏

案例: 在一个4×4的方格组成的棋盘中,有一个特殊方格,要用如下不同形式的L型骨牌把棋盘上除了特殊方格的其他所有方格覆盖,且骨牌之间不能有重叠,怎样摆放呢?

分治法1.png

解决步骤:

L型骨牌的特点是只要再加一个方格就能变成2×2的方格,而正好棋盘中给出了一个特殊方格在左上角的2×2方格中,那么我们就可以在其他三个2×2的方格中构造出特殊方格,保证每个2×2的方格中都有一个特殊方格,那么第一个骨牌应该如下摆放。这样每个2×2的方格都有一个特殊方格,接下来我们只要按照形状摆放就好。

分治法2.png

可以体现的计算思维

递归能够将一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,只需少量步骤就可描述出解决问题过程所需要的多次重复工作,大大地减少了工作量。分治法体现的是计算思维中“递归”的特点。