分治算法(Divide&Conquer)

一、简介

        分治算法从字面上理解就是分而治之，即把一个复杂的大问题分成若干个相同或者相似的子问题，在把子问题划分成更多小问题，直到最后子问题是简单一下就能解出来为止；然后开始把简单的子问题向上合并，最终得到大问题的解。

        举个例子：16枚硬币，其中有一个假币，假币的重量和真币的重量不一样，请问比较多少次能够找出假币。首先我们把这个大问题分成两个小问题，随机选择8枚硬币作为第一组，剩下来的8枚硬币作为第二组。利用仪器判断假币在那一堆里。在剩下的那组里再取出两组4枚，进行称重，依此类推。最后，找出假币。此过程如图1所示

二、适用条件

采用分治法解决的问题一般具有的特征如下：

1. 1. 问题的规模缩小到一定的规模就可以较容易地解决；

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

   3. 合并问题分解出的子问题的解可以得到问题的解；

   4. 问题所分解出的各个子问题之间是独立的，即子问题之间不存在公共的子问题；

三、步骤 

1. 划分步：把输入的问题划分为k个子问题，并尽量使这k个子问题的规模大致相同。

2. 治理步：当问题的规模大于某个预定的值n0时，治理步由k个递归调用组成。

3. 组合步：组合步把各个子问题的解组合起来，它对分治算法的实际性能至关重要，算法的有效性很大地依赖于组合步的实现。

分治法的关键是算法的组合步。究竟应该怎样合并，没有统一的模式，因此需要对具体问题进行具体分析，以得出比较好的合并算法。

四、实现框架

        对于一个规模为n的问题，若该问题可以轻而易举地解决，则直接进行解决，否则将其分为k个规模较小的问题，这些子问题相互独立，递归地解决这些子问题，最后将这些问题合并，从而得到原题的解。

        分治算法伪代码：

{
	if(|p|<=n0)
	{
		resolve(P);
		return;
	}
	for(int i=1; i<=k; i++)
	{
		yi=Divide_and_Conquer(Pi);
	}
	T=MERGE(y1,y2,…,yk);
	return T;
}

---

感谢阅读！