数学建模社区-数学中国

标题: 分治算法 ——数学建模 [打印本页]

作者: kennethchen 时间: 2011-9-3 13:36
标题: 分治算法 ——数学建模
在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于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 则可以直接给出结果，如果大小为 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;
}

作者: helenliu1990 时间: 2011-9-4 08:47
内容很不错啊，但是分治算法是一种单独的算法，还是很多算法的思想是分治算法？

作者: sursky 时间: 2011-11-10 18:48
其实递归这个玩意不是啥好主意，试试斐波那契数列，递归30次就行了，卡死你~

作者: jt202010 时间: 2011-11-11 13:40

作者: hdzhangliang 时间: 2011-11-12 23:06

sursky 发表于 2011-11-10 18:48
其实递归这个玩意不是啥好主意，试试斐波那契数列，递归30次就行了，卡死你~

这个斐波那契数列增长太快！写个高精度再递归应该不会卡吧！！！

作者: dyun 时间: 2011-11-23 20:05
thx for share

作者: yezia 时间: 2011-11-24 11:12

谢啦

作者: xieeyawen 时间: 2011-11-27 08:52

作者: z0y0h0 时间: 2011-12-2 15:22
谢谢了谢谢了谢谢了

作者: 无__没 时间: 2011-12-11 15:38
分治法？？？？？

作者: 无__没 时间: 2011-12-11 15:39

作者: hdzhangliang 时间: 2011-12-19 22:47

sursky 发表于 2011-11-10 18:48
其实递归这个玩意不是啥好主意，试试斐波那契数列，递归30次就行了，卡死你~

你那是什么机器啊！三十次就卡？！！！

作者: alair006 时间: 2012-2-7 16:19
恩，参考一下。。6068568819021368

作者: 李扬@ 时间: 2012-2-7 21:25
真好真好真好真好……………………

作者: cai_er 时间: 2012-7-5 17:25
我也来学习了，谢谢您~

作者: winecar 时间: 2012-7-17 17:03

作者: winecar 时间: 2012-7-18 16:15

winecar 发表于 2012-7-17 17:03

看其他人用了纯表情，就学习了下，怎么就收到了个被警告的消息！！！！！！！！！！这个警告应该在贴中明显出现才好啊，否则又有人不知道，继续沿用下去了。

作者: darker50 时间: 2012-7-18 17:47

winecar 发表于 2012-7-18 16:15
看其他人用了纯表情，就学习了下，怎么就收到了个被警告的消息！！！！！！！！！！这个警告应该在贴中明 ...

这个系统的警告本来就不明显，谢谢给的建议。下次我加上点评，这样应该够明显的。

作者: winecar 时间: 2012-7-19 10:18

darker50 发表于 2012-7-18 17:47
这个系统的警告本来就不明显，谢谢给的建议。下次我加上点评，这样应该够明显的。

darker50 管理员给力，支持下。

作者: darker50 时间: 2012-7-19 11:29

winecar 发表于 2012-7-19 10:18
darker50 管理员给力，支持下。

奖罚必须分明，有意见虚心听取，大家共同进步。

作者: 千叶迦南 时间: 2013-8-12 08:50
楼主好人！

作者: 千叶迦南 时间: 2013-8-12 08:51
但貌似分治算法只是一种思想吧

作者: 模天大楼 时间: 2014-8-10 23:49
喜欢就收下了，O(∩_∩)O~

作者: chke1993 时间: 2014-8-18 20:28
很好的资料，很强大的

作者: c..luo 时间: 2014-8-20 20:46
thx for share

作者: 流雨星月 时间: 2014-8-30 16:10
顶一个。。。。。。。。

作者: whx_isun 时间: 2015-2-1 13:37
赞一赞更健康！

作者: LYJA 时间: 2015-5-20 20:28
楼主好人，谢谢！！！！！！！！！！！！！！！！！！！！！！

作者: tmdxx 时间: 2015-12-11 12:45
都是很厉害的样子，强啊

作者: 远行的小船儿666 时间: 2016-1-24 21:44
内容是挺不错的

作者: lile19940907 时间: 2016-1-27 21:38
楼主的帖子怎么样？赶紧试试这里的快顶一个！！！！！！！！！！！！！！速回复给楼主点评论吧

作者: lile19940907 时间: 2016-1-27 21:38
顶一个！！！！！！！！！！！！！！

作者: souluki 时间: 2016-4-21 21:48

谢谢了谢谢了谢谢了

作者: 深梦沉睡 时间: 2016-5-7 00:05
看看，学习学习

作者: 陈华林 时间: 2016-9-29 16:36
好，谢谢楼主啦

作者: hexinghui 时间: 2017-9-18 23:04
棒棒的，楼主最喜欢你这样的了

作者: 2249039642 时间: 2017-11-11 15:17
一般都把问题分为两部分把

作者: 2244161204 时间: 2018-4-13 14:56

谢谢您的分享

作者: peter1977 时间: 2018-6-4 15:08
之前了解分治算法不多，学习了，谢谢！

作者: 1151429830 时间: 2018-7-19 20:59
赞！感谢楼主分享！

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)