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

立志德美 2019-05-31

展開全文

『運(yùn)籌OR帷幄』轉(zhuǎn)載

作者：進(jìn)階的HelloWorld

編者按

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

文章轉(zhuǎn)載自微信公眾號五分鐘學(xué)算法（id: CXYxiaowu）

1 概念

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

2 算法策略

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

3 使用場景

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

4 基本步驟

分治法在每一層遞歸上都有三個步驟：
??（1）分解：將原問題分解為若干個規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題。
??（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 為一閾值，表示當(dāng)問題 P 的規(guī)模不超過 n0 時，問題已容易直接解出，不必再繼續(xù)分解。ADHOC(P) 是該分治法中的基本子算法，用于直接解小規(guī)模的問題 P。因此，當(dāng) P 的規(guī)模不超過n0 時直接用算法 ADHOC(P) 求解。算法 MERGE(y1,y2,…,yk) 是該分治法中的合并子算法，用于將 P 的子問題 P1 ,P2 ,…,Pk 的相應(yīng)的解 y1 , y2 ,…, yk 合并為 P 的解。

6 典型案例

6.1 二分查找

??二分查找是典型的分治算法的應(yīng)用。需要注意的是，二分查找的前提是查找的數(shù)列是有序的。

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

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

代碼實(shí)現(xiàn)：

#include<string.h>
#include<stdio.h>
int k;
int binarysearch(int a[],int x,int low,int high)//a表示需要二分的有序數(shù)組（升序），x表示需要查找的數(shù)字，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('請輸入需要查找的正數(shù)字：\n');
    int x;
    scanf('%d',&x);
    int r=binarysearch(a,x,0,9);
    if(r==-1)
    {
        printf('沒有查到\n');
    }
    else
    {
        printf('查到了,在數(shù)列的第%d個位置上\n',k+1);
    }
    return 0;
}

6.2 全排列問題

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

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）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。即先劃分為兩個部分，最后進(jìn)行合并。

歸并排序

偽代碼：

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

代碼實(shí)現(xiàn)：

public class MergeSort {
    //兩路歸并算法，兩個排好序的子序列合并為一個子序列
    public void merge(int []a,int left,int mid,int right){
        int []tmp=new int[a.length];//輔助數(shù)組
        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++];//同上

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

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

6.4 快速排序

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

（2）求解：
??通過遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
（3）合并：
??因?yàn)楫?dāng)'求解'步驟中的兩個遞歸調(diào)用結(jié)束時，其左、右兩個子區(qū)間已有序。對快速排序而言，'組合'步驟無須做什么，可看作是空操作。

快速排序

代碼實(shí)現(xiàn)：

#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對應(yīng)的值*/
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /*中樞值與j對應(yīng)值交換*/
    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）問題也是一個經(jīng)典的遞歸問題，該問題描述如下：

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

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

代碼實(shí)現(xiàn)：

    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經(jīng)過targetTower移動到tempTower
            hanoi(n - 1, sourceTower, targetTower, tempTower);
            //移動盤子n由sourceTower移動到targetTower
            move(n, sourceTower, targetTower);
            //把之前移動到tempTower的（盤子n-1~盤子1），由tempTower經(jīng)過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 總結(jié)分析

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

文章作者：進(jìn)階的HelloWorld

本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自：立志德美 > 《其他技能》

舉報/認(rèn)領(lǐng)