概念编辑本段回目录
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
分治法解题的一般步骤：
（1）分解，将要解决的问题划分成若干规模较小的同类问题；
（2）求解，当子问题划分得足够小时，用较简单的方法解决；
（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。
算法设计模式编辑本段回目录
它的一般的算法设计模式如下：
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)子问题的思想，它几乎总是比子问题规模不等的做法要好。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案，或者是合并方案不明显，如例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） T(1) = 1
T(n) = kT(n/m) + f(n)
用算法的复杂性中递归方程解的渐进阶的解法介绍的解递归方程的迭代法，可以求得(1)的解:
logm(n-1)
（2）T(n) = n^(logmK) + ∑ (k^j)*f(n/(m^j))
j=0
注意，递归方程(1)及其解(2)只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常，
我们可以假定T(n)是单调上升的，从而当mi≤nn0
由于我们关心的一般是最坏情况下的计算时间复杂度的上界，所以用等于号(=)还是小于或等于号(≤)是没有本质区别的分治法的几种变形。
几种分治的方法 编辑本段回目录
1.二分法 dichotomy一种每次将原问题分解为两个子问题的分治法，是一分为二的哲学思想的应用。这种方法很常用，由此法产生了许多经典的算法和数据结构。
2.分解并在解决之前合并法 divide and marriage before conquest一种分治法的变形，其特点是将分解出的子问题在解决之前合并。
3.管道传输分治法 pipelined divide and conquer一种分治法的变形，它利用某种称为“管道”的数据结构在递归调用结束前将其中的某些结果返回。此方法经常用来减少算法的深度
举例编辑本段回目录
国际象棋棋盘上某个位置的一只马它是否可能只走63步正好走过除起点外的其他63个位置各一次?试设计一个分治算法
算法步骤：
1 ：从左上角起，给棋盘编号（1，1），（1，2），。。。。。。（8，8），计为集合qp。tracks记录走过的每个点. （可以想象为坐标（x,y））
2：设起点为（1，1），记为 当前位置 cp，
3：搜索所有可走的下一步，根据“马行日”的走步规则，可行的点的坐标是x坐标加减1，y坐标加减2，
或是x加减2，y加减1； （例如起点（1，1），可计算出（1+1，1+2），（1+1，1-2），（1-1，1+2），（1-1，1-2），（1+2，1+1），（1+2，1-1），（1-2，1+1），（1-2，1-1） 共8个点）， 如果没有搜到可行点，程序结束。
4：判断计算出的点是否在棋盘内，即是否在集合qp中；判断点是否已经走过，即是否在集合tracts中，不在才是合法的点。（在上面的举例起点（1，1），则合法的下一步是（2，3）和 （3，2））
5：将前一步的位置记录到集合tracts中，即tracts.add（cp）；选择一个可行点，cp=所选择点的坐标。
6：如果tracts里的点个数等于63，退出程序，否则回到步骤3继续执行。
