欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

经典算法之分治(Divide)

程序员文章站 2022-07-03 14:22:51
...

1、分治的定义

  分治即分而治之。分治算法就是把一个大的问题分为若干个子问题,然后在子问题继续向下分,一直到base cases,通过base cases的解决,一步步向上,最终解决最初的大问题。分治算法是递归的典型应用。

2、分治的思想

分治法的设计思想是:

1. 分–将问题分解为规模更小的子问题;

2. 治–将这些规模更小的子问题逐个击破;

3. 合–将已解决的子问题合并,最终得出“母”问题的解。

3、分治的要素

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

(2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。

(3)利用该问题分解出的子问题的解可以合并为该问题的解。如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。

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

4、分治算法的典型应用

(1)最近点问题

  假设在坐标平面上分布了一系列的点,那么问题是求取这些点两两之间的最短距离。最naive的做法当然是穷举法,计算所有的两两点间的距离,然后取最小值。穷举法对于小样本总是不错的。但是对于大样本来说,就不是那么合适了,这里我们用divide-and-conquer算法来解决这一问题。

经典算法之分治(Divide)

  首先对于所有的点,按照x坐标将其分为两部分,这就是divide,那么最短距离就是左边部分中的最短距离Dl,右边部分的最短距离Dr,以及左右部分之间的距离Dc。对于Dl以及Dr,可以递归的计算得到,这就是conquer。那么唯一的问题就是Dc。我们知道如果最短距离是Dc的话,那么Dc<=min(Dl,Dr)。因此我们只需要计算距离divide分割线S = min(Dl,Dr)的点就可以了。进一步我们可以看到对于每个在2S区域内的点,只需要计算y坐标距离这一点不大于S的点就可以,这样可以进一步简化运算量。

for(i=0;i<NumPointsInStrip;i++)  
    for(j=i+1;j<NumPointsInStrip;j++)  
        if(Pi and Pj coordinates differ by more than S)  
            break;  
        else  
            if(Dist(Pi,Pj)<S)  
                S = Dist(Pi,Pj);  

(2)其他经典问题

(1)二分搜索
(2)大整数乘法
(3)Strassen矩阵乘法
(4)棋盘覆盖
(5)合并排序
(6)快速排序
(7)线性时间选择
(8)循环赛日程表
(9)汉诺塔

参考:https://www.cnblogs.com/leishitou/p/5436201.html
https://www.cnblogs.com/leishitou/p/5436201.html

相关标签: 分治算法