当前位置:主页 >> Java基础 >> 正文
五大算法之一--分治法
阅读:313 输入:2014-05-22 07:02:48

一、分治法

在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。

分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题,1<k≤n ,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

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

1) 该问题的规模缩小到一定的程度就可以容易地解决;

2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;

3) 利用该问题分解出的子问题的解可以合并为该问题的解;

4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

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

分治法的基本步骤

分治法在每一层递归上都有三个步骤:

分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;

解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题

合并:将各个子问题的解合并为原问题的解。

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

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的问题所需的计算时间,则有:

通过迭代法求得方程的解:

递归方程及其解只给出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)。

例子

1话说递归与HANOI塔


递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现像。

程序调用自身的编程技巧称为递归(recursion)。

一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。

一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

注意:

(1) 递归就是在过程或函数里调用自身;

(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

递归算法一般用于解决三类问题:

(1)数据的定义是按递归定义的。(Fibonacci函数)

(2)问题解法按递归算法实现。(回溯)

(3)数据的结构形式是按递归定义的。(树的遍历,图的搜索)

递归的缺点:

递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

递归与HANOI塔

HANOI塔问题递归算法的最典型的例题。

本程序可同时将HANOI塔问题的解题步骤的中间结果显示在屏幕上和保存在文本文件中。(后一点对于显示结果很多无法在一屏中显示时,特别有用)

程序思路很简单,看注释就明白了。

/*

Name: hanoi2.c

Author:   zhuqing

Description:  HANOI塔问题的递归解

Date: 06-08-03 11:44

Copyright:

*/

#include <stdio.h>

#define N 5

/* 原柱,中间柱,目标柱初值数组 */

char a[]={'1','2','3','4','5'};

char b[]={'0','0','0','0','0'};

char c[]={'0','0','0','0','0'};

int step=0;

main(){

FILE *fp;

int i;

if((fp=fopen("c:\\hanoi2.txt","w"))==NULL){

printf("\nCannot open the file!\n");

getch();

exit(0);

}

printf("\n============ HANOI TOWER ============\n");

print(N);

fprint(N,fp);

move(N,a,b,c,fp);

fclose(fp);

getch();

}

/* 递归函数 */

void move(int n,char a[],char b[],char c[],FILE* fp)

{

if(n>0){

move(n-1,a,c,b,fp);

c[n-1]=a[n-1];

a[n-1]='0';

print(N);

fprint(N,fp);

move(n-1,b,a,c,fp);

}

}

/*  打印输出结果到屏幕的函数*/

void print(n)

int n;

{

int i;

printf("\nSTEP%d",step++);

printf("\na:");

for(i=0;i<n;i++)

printf("%3c",a[i]);

printf("\nb:");

for(i=0;i<n;i++)

printf("%3c",b[i]);

printf("\nc:");

for(i=0;i<n;i++)

printf("%3c",c[i]);

printf("\n-------------------------------------\n");

}

/*  打印输出结果到文本文件的函数*/

void fprint(n,fp)

int n;

FILE *fp;

{

int i;

fputs("\na:",fp);

for(i=0;i<n;i++)

fputc(a[i],fp);

fputs("\nb:",fp);

for(i=0;i<n;i++)

fputc(b[i],fp);

fputs("\nc:",fp);

for(i=0;i<n;i++)

fputc(c[i],fp);

fputs("\n-------------------------------------\n",fp);

}


2二分法求方程近似解


二分法求方程近似解:求方程f(x) = x^3 + x^2 - 1 = 0在[0,1]上的近似解,精确度为0.01。

算法分析:二分法求方程近似解的基本思想是将方程的有解区间平分为两个小区间,然后判断解在哪个小区间;继续把有解的区间一分为二进行判断,如此周而复始,直到求出满足精确要求的近似解。

二分法求方程近似解的算法步骤:

⑴确定区间[a,b],验证f(a).f(b) < 0,给定精确度e

⑵求区间(a, b)的中点mid

⑶计算f(mid)

若f(mid) = 0,则mid就是函数的零点

若f(a).f(mid) < 0,则令b = mid(此时零点a < x0 < mid)

若f(mid).f(b) < 0,则令a = mid(此时零点mid < x0 < b)

⑷判断是否达到精确度e:即若|a-b| < e,则得到零点近似值a(或b);否则重复⑵-⑷。

代码如下:

double F(double a, double b, double c, double d, double x)//函数表达式

{

return (((a * x + b) * x) * x + d) / c;

}

double Function(double a, double b, double c, double d, double low, double high, double e)

{

double mid = (low + high) / 2;

if (F(a, b, c, d, mid) == 0)

return mid;

while ((high-low) >= e)

{

mid = (low + high) / 2;

if (F(a, b, c, d, mid) == 0)

return mid;

if (F(a, b, c, d, low)*F(a, b, c, d, mid) < 0)

high = mid;

else

low = mid;

}

return low;

}


3用C++实现合并排序


合并排序的思想:当只有一个元素时终止排序,超过一个元素的话,将所有元素分成大致相同的两个集合,分别对两个集合进行排序,最后将排好序的子集合合并为所要求的排好序的集合。

在最坏情况下,时间复杂度为O(nlogn),它是一个渐进的最优算法。

#include <iomanip.h>

#include <iostream.h>

//这个函数将b[0]至b[right-left+1]拷贝到a[left]至a[right]

template <class T>

void Copy(T a[],T b[],int left,int right){

int size=right-left+1;

for(int i=0;i<size;i++){

a[left++]=b[i];

}

}

//这个函数合并有序数组a[left:i],a[i+1:right]到b,得到新的有序数组b

template <class T>

void Merge(T a[],T b[],int left,int i,int right){

int a1cout=left,//指向第一个数组开头

a1end=i,//指向第一个数组结尾

a2cout=i+1,//指向第二个数组开头

a2end=right,//指向第二个数组结尾

bcout=0;//指向b中的元素

for(int j=0;j<right-left+1;j++)//执行right-left+1次循环

{

if(a1cout>a1end){b[bcout++]=a[a2cout++];continue;}//如果第一个数组结束,拷贝第二个数组的元素到b

if(a2cout>a2end){b[bcout++]=a[a1cout++];continue;}//如果第二个数组结束,拷贝第一个数组的元素到b

if(a[a1cout]<a[a2cout]){b[bcout++]=a[a1cout++];continue;}//如果两个数组都没结束,比较元素大小,把较小的放入b

else

{b[bcout++]=a[a2cout++];continue;}

}

}

//对数组a[left:right]进行合并排序

template <class T>

void MergeSort(T a[],int left,int right){

T *b=new int[right-left+1];

if(left<right){

int i=(left+right)/2;//取中点

MergeSort(a,left,i);//左半边进行合并排序

MergeSort(a,i+1,right);//右半边进行合并排序

Merge(a,b,left,i,right);//左右合并到b中

Copy(a,b,left,right);//从b拷贝回来

}

}

int main(){

int n;

cout<<"how many numbers to sort:";

cin>>n;

int *a=new int[n];

cout<<"input "<<n<<" numbers:";

for(int i=0;i<n;i++)

{cin>>a[i];}

MergeSort( a, 0, n-1);

for(int j=0;j<n;j++){

cout<<setw(5)<<a[j];

}

return 1;

}


4求最大值和最小值的分治算法


实践题目:

给定一个顺序表,编写一个求出其最大值和最小值的分治算法。

分析:

由于顺序表的结构没有给出,作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义,数据随机生成。我们知道如果数组大小为 1 则可以直接给出结果,如果大小为 2则一次比较即可得出结果,于是我们找到求解该问题的子问题即: 数组大小 <= 2。到此我们就可以进行分治运算了,只要求解的问题数组长度比 2 大就继续分治,否则求解子问题的解并更新全局解以下是代码。

*/

/*** 编译环境TC ***/

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#define M 40

/* 分治法获取最优解 */

void PartionGet(int s,int e,int *meter,int *max,int *min){

/* 参数:

* s 当前分治段的开始下标

* e  当前分治段的结束下标

* meter 表的地址

* max 存储当前搜索到的最大值

* min 存储当前搜索到的最小值

*/

int i;

if(e-s <= 1){ /* 获取局部解,并更新全局解 */

if(meter[s] > meter[e]){

if(meter[s] > *max)

*max = meter[s];

if(meter[e] < *min)

*min = meter[e];

}else{

if(meter[e] > *max)

*max = meter[s];

if(meter[s] < *min)

*min = meter[s];

}

return ;

}

i = s + (e-s)/2; /* 不是子问题继续分治,这里使用了二分,也可以是其它 */

PartionGet(s,i,meter,max,min);

PartionGet(i+1,e,meter,max,min);

}

int main(){

int i,meter[M];

int max = INT_MIN;   /* 用最小值初始化 */

int min = INT_MAX;   /* 用最大值初始化 */

printf("The array's element as followed:\n\n");

randomize();/* 初始化随机数发生器 */

for(i = 0; i < M; i ++){  /* 随机数据填充数组 */

meter[i] = rand()%10000;

if(!((i+1)%10))   /* 输出表的随机数据 */

printf("%-6d\n",meter[i]);

else

printf("%-6d",meter[i]);

}

PartionGet(0,M - 1,meter,&max,&min); /* 分治法获取最值 */

printf("\nMax : %d\nMin : %d\n",max,min);

system("pause");

return 0;

}