【技术文档】《算法设计与分析导论》R.C.T.Lee等·第4章 分治策略

分治策略有一种“大事化小,小事化了”的境界,它的思想是将原问题分解成两个子问题,两个子问题的性质和原问题相同,因此这两个子问题可以再用分治策略求解,最终将两个子问题的解合并成原问题的解。有时,我们会有这样的疑惑:分治策略是将原问题分解成子问题,子问题又用分治策略求解,那分治策略到底是什么?这种感觉就像听到有人说“因为我说我没有做错事,所以我没有做错事”一样,让我们不知道他“没有做错事”的真正原因是什么。

对于上面的困惑,我本科的老师告诫过我们:“对于分治策略,当你们想不明白的时候只需记住两点:一是怎样将问题分解成两个子问题,二是要有递归出口。”举个小例子:八个小伙伴为确定谁是领头,决定比武论,两两比较,胜者将进入下一轮再进行两两比较,最终将决出一个领头,如果我们将这个思路倒过来想就是分治策略了,八个人分成两组,此时每组四人,每组决出一个领头,再比较这两个组的领头就能决出最终那个领头,而每组领头的决出又采用将该组分成两组,每组两人,这时直接比较就能决出领头的,无需再分,此处就是递归的出口。说了这么多,总结一下分治策略的步骤:

  1. 如果问题规模足够小,那么采取方法解决它;否则,继续将问题划分为两个子问题(小事化了
  2. 对于子问题仍采用分治策略(大事化小
  3. 将子问题的解合并成原问题的解(特别注意)

第一步、第二步是思维的问题,只要我们不陷入思维的漩涡,记住处理递归出口就没有问题,而第三步是细节问题,我们常常忽略,而且不易处理,下面举两个例子来加以说明。

求二维极大点问题。在二维空间中,如果x1>x2且y1>y2,那么称点(x1,y1)支配点(x2,y2)。在一个二维点集中,如果一个点没有被其它点支配,则称这个点是极大点。为了找出这个点集的所有极大点,可以采用分治策略,将点集划分成点数更少的两个点集,递归出口是:当点集只有一个点时,这个点就是这个点集的极大点。对于合并子问题的解的时候就要小心了,并不是简单地取它们的并集,而要考虑这两个点集的极大点之间是否存在支配与被支配的关系,处理的方法很简单:如果左子点集的极大点的y值小于右子点集中的某个极大点,则舍弃左子点集的该极大点。

最近点对问题:一个平面上有n个点,找出距离最近的那对点。采用分治策略,第一二步就不说了。当我们合并这个子点集的最近点对时需要注意:原点集的最近点对的两个端点可能在不同的子点集中,这就需要我们考虑,以分割线附近的点为圆心,以两子点集较小的点对的距离为半径画圆,判断圆内是否存在另个点集中的点,如果存在,最短距离将更改,如果没有,最短距离就是两子点集较小的点对的距离


在大学老师告诫我们的两点,加上合并注意事项,就构成了采用分治策略应注意的三点:

  1. 思考如何将大问题分解成两个小问题
  2. 记住递归出口
  3. 处理合并解的问题
原文地址:https://www.cnblogs.com/pangblog/p/3260609.html