简介
对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
分治法的基本思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。
分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
如果原问题可分割成k个子问题,1<k≤n ,且这些子问题都可解,并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。
分治法的适用条件
分治法所能解决的问题一般具有以下几个特征:
- 该问题的规模缩小到一定的程度就可以容易地解决;
- 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
- 利用该问题分解出的子问题的解可以合并为该问题的解;
- 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。
分治法的基本步骤
分治法在每一层递归上都有三个步骤:
-
分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
-
解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
-
合并:将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下:
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的解。
根据分治法的分割原则,原问题应该分为多少个子问题才较适宜?各个子问题的规模应该怎样才为适当?这些问题很难予以肯定的回答。但人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。换句话说,将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显,如下面的例1,例2;有些问题合并方法比较复杂,或者是有多种合并方案,如例3,例4;或者是合并方案不明显,如例5。究竟应该怎样合并,没有统一的模式,需要具体问题具体分析。
分治法的复杂性分析
从分治法的一般设计模式可以看出,用它设计出的程序一般是一个递归过程。因此,分治法的计算效率通常可以用递归方程来进行分析。为方便起见,设分解阈值n0=1,且算法ADHOC解规模为1的问题耗费1个单位时间。又设分治法将规模为n的问题分成k个规模为n/m的子问题去解,而且,将原问题分解为k个子问题以及用算法MERGE将k个子问题的解合并为原问题的解需用f(n)个单位时间。如果用T(n)表示该分治法Divide-and-Conquer(P)解规模为|P|=n的问题P所需的计算时间,则有:
(1)
用算法的复杂性中递归方程解的渐进阶的解法介绍的解递归方程的迭代法,可以求得(1)的解:
(2)
注意,递归方程(1)及其解(2)只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常,我们可以假定T(n)是单调上升的,从而当mi≤n<mi+1时,T(mi)≤T(n)<T(mi+1)。
另一个需要注意的问题是,在分析分治法的计算效率时,通常得到的是递归不等式:
(3)
由于我们关心的一般是最坏情况下的计算时间复杂度的上界,所以用等于号(=)还是小于或等于号(≤)是没有本质区别的。
分治法的几种变形
-
二分法 dichotomy
一种每次将原问题分解为两个子问题的分治法,是一分为二的哲学思想的应用。这种方法很常用,由此法产生了许多经典的算法和数据结构。
-
分解并在解决之前合并法 divide and marriage before conquest
一种分治法的变形,其特点是将分解出的子问题在解决之前合并。
-
管道传输分治法 pipelined divide and conquer
一种分治法的变形,它利用某种称为“管道”的数据结构在递归调用结束前将其中的某些结果返回。此方法经常用来减少算法的深度。
注:divide and marriage before conquest和pipelined divide and conquer 方法我并不太了解,只在某些参考文献上看过其名称。其原文定义如下:
divide and marriage before conquest:A variant of divide and conquer in which subproblems created in the "divide" step are merged before the "conquer" step.
pipelined divide and conquer:A divide and conquer paradigm in which partial results from recursive calls can be used before the calls complete. The technique is often useful for reducing the depth of an algorithm.
注作者:Starfish.h@china.com
分享到:
相关推荐
快速排序 快速排序(Quicksort)是一种常见的、高效的排序算法,它基于分治(Divide and Conquer)的思想
分治算法课件。分治算法是算法设计中的重要部分,体现了算法设计大化小的思想。
归并排序(Merge sort)(台灣譯作:合併排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两...
分而治之的算法分而治之的算法分而治之的算法分而治之的算法
title: Tree and Divide Conquer date: 2020-03-24 20:11:09 tags: Algorithm Tree and Divide Conquer 最近做二叉树相关的题,被递归搞的晕头转向...由于树的结构,这种数据结构很适合用分治(Divide Conquer) Divi
python 实现 分治法 (Divide-and-conquer algorithm) 课程设计 代码 包括 Closest Pair Of Points Convex Hull Heaps Algorithm Heaps Algorithm Iterative Inversions Kth Order Statistic Max ...
超稳定超快速分治特征值分解_SuperDC Stable superfast divide-and-conquer eigenvalue decomposition.pdf
具有多项式独立项的半递归分治的显式解_Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent term.pdf
九章算法之二叉树与分治法(Binary Tree & Divide Conquer) 多看多思考
分治法(Divide and Conquer) Our first design strategy: Divide and Conquer(算法设计策略) Often recursive, at least in definition(通常是递归形式的) Strategy(策略思想): Break a problem into 1 or more ...
分治 divide and conquer 分而治之 问题可分解多个子问题,且子问题没有传递性,合并子问题不复杂情况下使用 c) 回溯 backtracking 类似枚举、几乎能解决所有问题 分多个阶段决策,每阶段处理多种策略,通过剪枝或...
分治法找一组数的最大值.Divide and conquer, find the maximum in a sequence of numbers
该算法是采用分治法(DivideandConquer)的一个非常典型的应用。合并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体...
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为: 从数列中挑出一个元素,称为“基准”(pivot), 重新排序数列,所有比基准值小的元素摆放在基准前面...
该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 算法步骤: 1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 2. 设定两个指针,最初位置分别为两个已经排序序列的...
合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
采用分治算法寻找序列A中第k个大的值,Divide and Conquer的方法能够有效地降低问题的时间复杂度。
归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。