0

ShinChan's Blog

 3 months ago
source link: http://chenqx.github.io/2015/03/16/Introduction-to-Divide-and-Conquer-Algorithm/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

  在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”(Divide and Conquer),就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……
  任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。

基本思想及策略

  分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
  分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
  如果原问题可分割成k个子问题,1< k≤n,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

分治法适用的情况

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

  • 该问题的规模缩小到一定的程度就可以容易地解决。绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加

  • 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。这条特征是应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用。

  • 利用该问题分解出的子问题的解可以合并为该问题的解。这条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。
  • 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。这条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

  分治法在每一层递归上都有三个步骤:
  step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
  step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
  step3 合并:将各个子问题的解合并为原问题的解。

  它的一般的算法设计模式如下:

Divide-and-Conquer(P)
    1. if |P|≤n0
    2. then return(ADHOC(P))
    3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
    4. for i←1 to k
    5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
    6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
    7. return(T)

  其中|P|表示问题P的规模;n0为一阈值,表示当问题P的规模不超过n0时,问题已容易直接解出,不必再继续分解。ADHOC(P)是该分治法中的基本子算法,用于直接解小规模的问题P。因此,当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法,用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。

复杂性分析

  一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:

T(n)=kT(n/m)+f(n)T(n)=kT(n/m)+f(n)

  通过迭代法求得方程的解:
  递归方程及其解只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的,从而当 mi≤n< mi+1 时,T(mi)≤T(n)< T(mi+1)。

示例: 归并排序

  归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。以二路归并为例:
二路归并排序示例
  代码示例:

#include <iostream>
using namespace std;
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[]){
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n){
if (a[i] <= a[j])
temp[k++] = a[i++];
temp[k++] = a[j++];
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
void mergesort(int a[], int first, int last, int temp[]){
if (first < last){
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
bool MergeSort(int a[], int n){
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
int main(){
int arr[] = {1, 5, 2, 4, 6, 3, 2, 6};
MergeSort(arr, 8);
for (int i = 0; i < 8; ++i){
cout<<arr[i]<<" ";
cout<<endl;

可使用分治法求解的一些经典问题

  • 大整数乘法
  • Strassen矩阵乘法
  • 线性时间选择
  • 最接近点对问题
  • 循环赛日程表

分治法设计程序时的思维过程

  实际上就是类似于数学归纳法,找到解决本问题的求解方程公式,然后根据方程公式设计递归程序。
  1、一定是先找到最小问题规模时的求解方法;
  2、然后考虑随着问题规模增大时的求解方法;
  3、找到求解的递归函数式后(各种规模或因子),设计递归程序即可。   

auther: 红脸书生


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK