Divide and Conquer Algorithm 分治算法
目录

1. 一般步骤

分治算法的一般步骤:

  1. Divide: 将原问题分解为一组子问题,每个子问题都与原问题类型相同,但是比原问题的规模小;
  2. Conquer: 递归地求解这些子问题;当子问题足够小时,直接求解。
  3. Combine: 将子问题的求解结果合并,得到原问题的解;

2. 最优子结构

如果问题的一个最优解中包含了子问题的最优解,则该问题具有最优子结构

在寻找最优子结构时,可以遵循一种共同的模式:

  • 问题的一个解可以是做一个选择。如矩阵链乘法中选择一个下标以该位置分裂矩阵链。做这种选择会得到一个或多个有待解决的子问题。
  • 假设对一个给定的问题,已知的是一个可以导致最优解的选择。不必关心如何确定这个选择,尽管假设它是已知的。
  • 在已知这个选择后,要确定哪些子问题会随之产生,以及如何描述所得到的子问题的空间。
  • 证明在问题的一个最优解中,使用的子问题的解也是最优解。(反证法)

3. 算法特征

分治法所能解决的问题一般具有以下几个特征:

  1. 该问题的规模缩小到一定的程度就可以容易地解决;
  2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解;
  4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加; 第二条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用; 第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑贪心法或动态规划法。 第四条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

4. 典型应用:

  1. 二叉查找
  2. 归并排序
  3. 快速排序
  4. 大整数乘法

5. 几种变形

  1. 二分法
  2. 分解并在解决之前合并法 divide and marriage before conquest
  3. 管道传输分治法 pipelined divide and conquer

参考:1. [[http://www.ahhf45.com/info/Data_Structures_and_Algorithms/algorithm/technique/divide_and_conquer/chapter2.htm][分治算法]]

发表评论