算法设计与分析

分治策略

1.分治策略基本原理

有道是“凡治众如治寡,分数是也”。它反映了一种广泛使用的策略:将一个难以直接解决的大问题,分解成一些规模较小的相同问题,以便分而治之,各个击破。在日常生活中,人们也常常应用类似的策略来处理问题。比如,搬家时为了把一个庞大的组合柜从旧楼房转移到新楼房,人们往往先把大组合柜拆成若干个小的单元,然后转移每一个小单元,最后在新楼房里把所有小单元拼装成大组合柜。显然,在计算机问题求解中,可以采用类似的策略来设计求解程序。即先把原问题分割成若干个子问题,然后分别求解这些子问题,最后合并这些子问题的解得到原问题的解。

分治并不是一个特定的算法,而是一种普适的问题求解策略。这种思想来源于人们偏好处理简单的事情,因为简单的事情比复杂的事情容易处理。另外,现实世界的复杂事物也是由简单的事物构成的,比如将物质不断分解,发现其最后的构成都是一样的。

分治法的基本思想是先将一个规模为n 的大问题分解为k 个规模较小的子问题,这些子问题相互独立而且与原问题性质相同,然后递归地求解这些子问题,最后将各个子问题的解合并得到原问题的解。其框架程序如下所示:

adhoc(P)是分治算法中的子程序,对应治过程(或者说conquer),一般是常数时间复杂度的子函数或者子过程。

设计划分策略是分治算法的基础和关键,人们往往遵循两个原则:① 平衡子问题原则,分割出的k个子问题其规模最好大致相当;② 独立子问题原则,分割出的k个子问题之间重叠越少越好,最好k个子问题是相互独立,不存在重叠子问题。

merge合并子程序,把k个子问题的解合并得到原问题的解。合并子程序因求解问题而异,即使是同一个问题,如果第二步的划分策略不同,其合并子程序也往往不一样。

在上述三个步骤中,划分策略是关键。总体上说,划分策略可以分为两大类:(1)黑盒划分策略,此策略根据问题的规模对原问题进行划分,而不考虑划分对象的属性值,所以形象地称之为黑盒划分。合并排序和逆序对问题的求解算法属于黑盒划分策略。(2)白盒划分策略,此策略根据划分对象的特定属性值(也称之为参照值)把对象集合划分为若干个子集。快速排序和最接近点对问题的求解算法可归属于白盒划分策略。

特别地,对于某些问题,应用白盒划分策略分解成多个子问题时,可能部分子问题完全相同,或者可判定部分子问题不可能包含问题的解,此时这些子问题可以忽略而无须求解。这类策略本书称之为减治策略,比如指数运算和二分查找等。


2.典型例题

1)集合划分

2)火星货币

3)元素交换

4)最接近点对

5)第K大的数


3.课件下载

Algorithm-4-Divide and conquer.pptx

4.扩展阅读

MapReduce是当前主流的大数据处理的架构,其基本思想也是采用分治策略,建议大家阅读这篇高引用高影响的论文。

Ref3-1 MapReduce: simplified data processing on large clusters.pdf