優(yōu)化 | 淺談什么是分治算法

立志德美 2019-05-31

展開全文

『運籌OR帷幄』轉載

作者：進階的HelloWorld

編者按

在計算機科學中，分支算法是一種很重要的算法。任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)。這篇文章從概念、算法策略、使用場景、經典案例、算法步驟等角度簡要介紹了分治算法的作用并在經典案例中也給出了相應的代碼。

文章轉載自微信公眾號五分鐘學算法（id: CXYxiaowu）

1 概念

??分治算法，根據字面意思解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

2 算法策略

??分治策略：對于一個規(guī)模為 n 的問題，若該問題可以容易地解決（比如說規(guī)模 n 較小）則直接解決，否則將其分解為 k 個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。
??在平時日常生活中，分治思想也是隨處可見的。例如：當我們打牌時，在進行洗牌時，若牌的數目較多，一個人洗不過來，則會將牌進行分堆，單獨洗一小堆牌是相對容易的，每一堆牌都洗完之后再放到一起，則完成洗牌過程。

3 使用場景

??（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決。
??（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質。
??（3）利用該問題分解出的子問題的解可以合并為該問題的解。
??（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

4 基本步驟

分治法在每一層遞歸上都有三個步驟：
??（1）分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題。
??（2）求解：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題。
??（3）合并：將各個子問題的解合并為原問題的解。

5 偽代碼

    Divide-and-Conquer(P)
    if |P| ≤ n0
        then return(ADHOC(P))
    將P分解為較小的子問題 P1 ,P2 ,...,Pk
        for i←1 to k
            do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi
        T ← MERGE(y1,y2,...,yk) △ 合并子問題
    return(T)

??其中，|P| 表示問題 P 的規(guī)模，n0 為一閾值，表示當問題 P 的規(guī)模不超過 n0 時，問題已容易直接解出，不必再繼續(xù)分解。ADHOC(P) 是該分治法中的基本子算法，用于直接解小規(guī)模的問題 P。因此，當 P 的規(guī)模不超過n0 時直接用算法 ADHOC(P) 求解。算法 MERGE(y1,y2,…,yk) 是該分治法中的合并子算法，用于將 P 的子問題 P1 ,P2 ,…,Pk 的相應的解 y1 , y2 ,…, yk 合并為 P 的解。

6 典型案例

6.1 二分查找

??二分查找是典型的分治算法的應用。需要注意的是，二分查找的前提是查找的數列是有序的。

算法流程：
??（1）選擇一個標志 i 將集合分為二個子集合。
??（2）判斷標志 L(i) 是否能與要查找的值 des 相等，相等則直接返回。
??（3）否則判斷 L(i) 與 des 的大小。
??（4）基于判斷的結果決定下步是向左查找還是向右查找。
??（5）遞歸繼續(xù)上面的步驟。

??通過二分查找的流程可以看出，二分查找是將原有序數列劃分為左右兩個子序列，然后在對兩個子序列中的其中一個在進行劃分，直至查找成功。

代碼實現：

#include<string.h>
#include<stdio.h>
int k;
int binarysearch(int a[],int x,int low,int high)//a表示需要二分的有序數組（升序），x表示需要查找的數字，low，high表示高低位
{
    if(low>high)
    {
        return -1;//沒有找到
    }
    int mid=(low+high)/2;
    if(x==a[mid])//找到x
    {
        k=mid;
        return x;
    }
    else if(x>a[mid]) //x在后半部分
    {
        binarysearch(a,x,mid+1,high);//在后半部分繼續(xù)二分查找
    }
    else//x在前半部分
    {
        binarysearch(a,x,low,mid-1);
    }
}

int main()
{
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    printf('請輸入需要查找的正數字：\n');
    int x;
    scanf('%d',&x);
    int r=binarysearch(a,x,0,9);
    if(r==-1)
    {
        printf('沒有查到\n');
    }
    else
    {
        printf('查到了,在數列的第%d個位置上\n',k+1);
    }
    return 0;
}

6.2 全排列問題

問題描述：
??有1，2，3，4個數，問你有多少種排列方法，并輸出排列。
問題分析：
??若采用分治思想進行求解，首先需要把大問題分解成很多的子問題，大問題是所有的排列方法。那么我們分解得到的小問題就是以 1 開頭的排列，以 2 開頭的排列，以 3 開頭的排列，以 4 開頭的排列。現在這些問題有能繼續(xù)分解，比如以 1 開頭的排列中，只確定了 1 的位置，沒有確定 2 ，3 ，4 的位置，把 2，3，4 三個又看成大問題繼續(xù)分解，2 做第二個，3 做第二個，或者 4 做第二個。一直分解下去，直到分解成的子問題只有一個數字的時候，不能再分解。只有一個數的序列只有一種排列方式，則子問題求解容易的多。
代碼實現：

public class Test {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4 };
        fullSort(arr, 0, arr.length - 1);
    }
    public static void fullSort(int[] arr, int start, int end) {
        // 遞歸終止條件
        if (start == end) {
            for (int i : arr) {
                System.out.print(i);
            }
            System.out.println();
            return;
        }
        for (int i = start; i <= end; i++) {
            swap(arr, i, start);
            fullSort(arr, start + 1, end);
            swap(arr, i, start);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

6.3 歸并排序

??歸并排序：歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。即先劃分為兩個部分，最后進行合并。

歸并排序

偽代碼：

算法 MergeSort(A, p, r)
輸入：數組A[p...r]
輸出：有序數組A
if(p < r)
    then q <- (p+r)/2//折半劃分
        MergeSort(A, p ,q)//子問題1
        MergeSort(A, p ,q)//子問題2
        Merge(A, p ,q, r)//合并求解

代碼實現：

public class MergeSort {
    //兩路歸并算法，兩個排好序的子序列合并為一個子序列
    public void merge(int []a,int left,int mid,int right){
        int []tmp=new int[a.length];//輔助數組
        int p1=left,p2=mid+1,k=left;//p1、p2是檢測指針，k是存放指針
        while(p1<=mid && p2<=right){
            if(a[p1]<=a[p2])
                tmp[k++]=a[p1++];
            else
                tmp[k++]=a[p2++];
        }

        while(p1<=mid) tmp[k++]=a[p1++];//如果第一個序列未檢測完，直接將后面所有元素加到合并的序列中
        while(p2<=right) tmp[k++]=a[p2++];//同上

        //復制回原素組
        for (int i = left; i <=right; i++) 
            a[i]=tmp[i];
    }

    public void mergeSort(int [] a,int start,int end){
        if(start<end){//當子序列中只有一個元素時結束遞歸
            int mid=(start+end)/2;//劃分子序列
            mergeSort(a, start, mid);//對左側子序列進行遞歸排序
            mergeSort(a, mid+1, end);//對右側子序列進行遞歸排序
            merge(a, start, mid, end);//合并
        }
    }
}

6.4 快速排序

??快速排序的基本思想：當前待排序的無序區(qū)為 A[low..high] ，利用分治法可將快速排序的基本思想描述為：
（1）分解：
??在A[low..high]中任選一個記錄作為基準(pivot)，以此基準將當前無序區(qū)劃分為左、右兩個較小的子區(qū)間R[low..pivotpos-1) 和 R[pivotpos+1..high] ，并使左邊子區(qū)間中所有記錄的關鍵字均小于等于基準記錄(不妨記為pivot)的關鍵字 pivot.key，右邊的子區(qū)間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot則位于正確的位置( pivotpos )上，它無須參加后續(xù)的排序。

（2）求解：
??通過遞歸調用快速排序對左、右子區(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
（3）合并：
??因為當'求解'步驟中的兩個遞歸調用結束時，其左、右兩個子區(qū)間已有序。對快速排序而言，'組合'步驟無須做什么，可看作是空操作。

快速排序

代碼實現：

#include <iostream>
using namespace std;
void QuickSort(int arr[], int low, int high){
    if (high <= low) return;
    int i = low;
    int j = high + 1;
    int key = arr[low];
    while (true)
    {
        /*從左向右找比key大的值*/
        while (arr[++i] < key)
        {
            if (i == high){
                break;
            }
        }
        /*從右向左找比key小的值*/
        while (arr[--j] > key)
        {
            if (j == low){
                break;
            }
        }
        if (i >= j) break;
        /*交換i,j對應的值*/
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /*中樞值與j對應值交換*/
    int temp = arr[low];
    arr[low] = arr[j];
    arr[j] = temp;
    QuickSort(arr, low, j - 1);
    QuickSort(arr, j + 1, high);
}

6.5 漢諾塔

漢諾塔（Hanoi Tower）問題也是一個經典的遞歸問題，該問題描述如下：

漢諾塔問題：古代有一個梵塔，塔內有三個座A、B、C，A座上有64個盤子，盤子大小不等，大的在下，小的在上。有一個和尚想把這個盤子從A座移到B座，但每次只能允許移動一個盤子，并且在移動過程中，3個座上的盤子始終保持大盤在下，小盤在上。

① 如果只有 1 個盤子，則不需要利用 B 塔，直接將盤子從 A 移動到 C 。
② 如果有 2 個盤子，可以先將盤子 2 上的盤子 1 移動到 B ；將盤子 2 移動到 C ；將盤子 1 移動到 C 。這說明了：可以借助 B 將 2 個盤子從 A 移動到 C ，當然，也可以借助 C 將 2 個盤子從 A 移動到 B 。
③ 如果有 3 個盤子，那么根據 2 個盤子的結論，可以借助 C 將盤子 3 上的兩個盤子從 A 移動到 B ；將盤子 3 從 A 移動到 C ，A 變成空座；借助 A 座，將 B 上的兩個盤子移動到 C 。
④ 以此類推，上述的思路可以一直擴展到 n 個盤子的情況，將將較小的 n-1個盤子看做一個整體，也就是我們要求的子問題，以借助 B 塔為例，可以借助空塔 B 將盤子A上面的 n-1 個盤子從 A 移動到 B ；將A 最大的盤子移動到 C ， A 變成空塔；借助空塔 A ，將 B 塔上的 n-2 個盤子移動到 A，將 C 最大的盤子移動到 C， B 變成空塔。。。

代碼實現：

    public static void hanoi(int n, String sourceTower, String tempTower, String targetTower) {
        if (n == 1) {
            //如果只有一個盤子1，那么直接將其從sourceTower移動到targetTower
            move(n, sourceTower, targetTower);
        } else {
            //將（盤子n-1~盤子1）由sourceTower經過targetTower移動到tempTower
            hanoi(n - 1, sourceTower, targetTower, tempTower);
            //移動盤子n由sourceTower移動到targetTower
            move(n, sourceTower, targetTower);
            //把之前移動到tempTower的（盤子n-1~盤子1），由tempTower經過sourceTower移動到targetTower
            hanoi(n - 1, tempTower, sourceTower, targetTower);
        }
    }

    //盤子n的從sourceTower->targetTower的移動
    private static void move(int n, String sourceTower, String targetTower) {
        System.out.println('第' + n + '號盤子 move:' + sourceTower + '--->' + targetTower);
    }

7 總結分析

??分治法將規(guī)模為 n 的問題分成 k 個規(guī)模為 n／m 的子問題去解。設分解閥值 n0 = 1 ，且 adhoc 解規(guī)模為 1 的問題耗費 1 個單位時間。再設將原問題分解為 k 個子問題以及用 merge 將 k 個子問題的解合并為原問題的解需用 f(n) 個單位時間。用T(n)表示該分治法解規(guī)模為 |P| = n 的問題所需的計算時間，則有：
??T（n）= k T(n/m) + f(n)

文章作者：進階的HelloWorld