447f250657aef0ec333c89554c2d9eca
分治算法

1 概念

  分治算法,根据字面意思解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

2 算法策略

  分治策略:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。
  在平时日常生活中,分治思想也是随处可见的。例如:当我们打牌时,在进行洗牌时,若牌的数目较多,一个人洗不过来,则会将牌进行分堆,单独洗一小堆牌是相对容易的,每一堆牌都洗完之后再放到一起,则完成洗牌过程。

3 使用场景

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

4 基本步骤

分治法在每一层递归上都有三个步骤:
  (1)分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题。
  (2)求解:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题。
  (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的规模,n0为一阈值,表示当问题P的规模不超过n0时,问题已容易直接解出,不必再继续分解。ADHOC(P)是该分治法中的基本子算法,用于直接解小规模的问题P。因此,当P的规模不超过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)递归继续上面的步骤。

  通过二分查找的流程可以看出,二分查找是将原有序数列划分为左右两个子序列,然后在对两个子序列中的其中一个在进行划分,直至查找成功。

代码实现:

#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);//在后半部分继续二分查找
    }
    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开头的排列。现在这些问题有能继续分解,比如以1开头的排列中,只确定了1的位置,没有确定2,3,4的位置,把2,3,4三个又看成大问题继续分解,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)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 即先划分为两个部分,最后进行合并。

归并排序

归并排序

伪代码:

top Created with Sketch.