请稍侯

分治算法(Divide And Conquer Method)

08 October 2015
更多

重要性

  • 要我说呢,这是算法中基础中的基础,但并不是不重要,相反,非常重要,而且有一定理解难度,至少对初学者,或者我来说,完全理解并灵活运用,绝非易事。
  • 所以,这个分治法(Divide-And-Conquer-Method)得反复看.尤其是递归的时候,必须反思反思分治法.

一、基本思路

  • 1.将问题的实例分为几个较小的实例,最好具有相等规模(事实上,一般说分为2个实例居多,并且注意是递归的分.);
  • 2.对这些较小的实例求解(一般使用递归的方法, 但在问题规模足够小的时候也可以采用另一个算法(停止递归));
  • 3.如果有必要的话,合并这些较小问题的解,以得到原始问题的解.(事实上, 一个分支算法的精华就在于合并解的过程).

二、分析: T(n) = aT(n/b) + f(n)

  • 大多数都是规模规模为n的问题,被规划为2个规模为n/2的问题.
  • 一般情况下:
    • 一个规模为n的实例可以被划分为b个规模为n/b的实例, 其中a个实例是需要求解的.
    • 递推式: T(n) = aT(n/b) + f(n)
    • T(n): 原始问题的解法;
    • n: 原始问题的规模, 与b区别;
    • a: a个实例, 一般等于n/b;
    • b: 原始问题划分成小问题后, 每个问题的最小实例的规模;
    • f(n): 表示将求解得到的a个子问题的解合并起来所需要的时间复杂度.
  • 对于«分治法»中主定理的理解, 得慢慢消化;

三、适用情况

  • 有点类是标题二的文字版
  • 能用分治法解决的问题T(n)的4个特征:
    • 1)该问题的规模缩小到一定程度b可以很容易解决T(n/b)(类似数学归纳法第一步)
    • 2)该问题可以分解为若干(a个实例)规模较小(规模为b)的相同问题, 即该问题具有最优子结构性质(T(n) ~= aT(n/b));
    • 3)利用该问题费解出的子问题就可以合并为该问题的解(T(n) = aT(b/n) + f(n));
    • 4)该问题分解出的各个子问题T(n/b)是相互独立的, 即子问题之间不包含公共的子问题.
  • 分析:
    • 每个特征都是下一个特征的前提, 呈上下属关系;
    • 第二个特征是应用分治法的前提, 反应在递归思想的运用;
    • 第三个特征是关键, 能否利用分治法完全取决于问题是否具有第三个特征;
      • 如果具备了第一、二个特征,而不具备第三个特征,可以考虑贪心法或者动态规划法;
    • 第四个特征设计到算法效率
      • 如果各个子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题(递归计算的诟病),此时虽然可以用分治法,但一般使用动态规划法较好.

四、分治法的基本步骤

  • 根据前两个标题的讲述,分治法在每一层递归上有三个步骤:
    • Step 1 分解: 将原问题T(n)分解为若干(a个)规模(为b)较小,相互独立,与原问题相同形式的子问题T(n/b);
    • Step 2 解决: 若子问题规模较小而容易被解决,则直接解,否则递归解决各个子问题; (递归的递归)
    • Step 3 合并: 将各个子问题的解合并为原来问题的解: T(n)=aT(n/b)+f(n);

五、设计模式

  • Divide-and-Conquer(P)
    • 1) if P <= n0 // P 表示问题P的规模, n0为阈值
    • 2) then return (ADHOC(P))
    • 3) 将P分解为较小规模的子问题P1, P2,…, Pk
    • 4) for I = 1 -> k
    • 5) do answerI <- Divide-and-Conquer(Pi); // 递归解决子问题Pi=T(b/n)
    • 6) T <- MERGE(answer1, answer2,…, answerk); // 合并子问题T(n)=aT(n/b)+f(n)
    • 7) return (T)
  • 分析:
    • 1): 表示当问题规模足够小到不超过n0是,问题已经容易直接解出,不必再继续分解.
    • 2): ADHOC(P)是该分治算法中的基本子算法,用于独立地、直接地解决小规模的问题.
    • 6): 算法MERGE(answer1,…,answerk)是原问题P的各个子问题的合并算法.

六、复杂性分析

  • 一个分治法将规模为n的问题分成a个规模为n/b的子问题去解;
  • 设费解阈值n0=1, 且adhoc解规模为1的问题耗时1个单位时间;
  • 再设将原问题分解为k个子问题以及用merge将a个子问题的解合并为原问题的解所需要f(n)个单位时间;
  • 用T(n)表示该分支算法解规模为 P =n的问题所需要的计算时间, 则有:
    • T(n) = aT(n/b) + f(n)
  • 通过迭代法求得方程的解:
    • 递归方程及其解只给出n等于b的方幂时T(n)的值, 但是如果认为T(n)足够平滑, 那么由n等于b的方幂时T(n)的值可以估计T(n)的增长速度.通常嘉定T(n)是单调上升的,从而当bi <= n <= bi+1时,T(bi) <= T(n) <= T(bi+1).

七、经典问题案例:

  • (1) [二分搜索]https://moeover.com/2015/10/05/one-out-of-eight-kinds-of-algorithm-1-1-halfinsertsort.html)(又称折半查找法)
  • (2) 大乘数法
  • (3) Strassen矩阵乘法
  • (4) 棋盘覆盖
  • (5) 合并排序
  • (6) 快速排序
  • (7) 线性时间选择
  • (8) 最接近点对问题
  • (9) 循环赛日程表
  • (10) 汉诺塔

八、总结

  • 依据分治法设计程序时的思维过程
    • 实际上类似于数学归纳法,眨动解决问题的求解方程公式,然后根据方程公式设计递归程序.
      • 1、一定是先找到最小问题规模时的求解方法;
      • 2、然后考虑随着问题规模增大时的求解方法;
      • 3、找到求解的递归函数式后(各种规模或因子),实际递归程序即可.
    整篇说了这么多,无不是在重复分治法这一思想,为的是说明分治法真的很重要!
            分治法, 很重要!
            分治法, 很重要!
            分治法, 很重要!
            Divide-And-Conquer-Method ! important;

参考