分治法（Divide-and-Conquer-）

治法（Divide-and-Conquer-）"/>

分治法（Divide-and-Conquer-）

分治法（Divide-and-Conquer-）

基本概念

分治法：将原问题（通常是规模较大的问题）分解为若干个结构相似且相互独立的子问题，递归的求解这些子问题，最后将子问题的解合并起来，得到原问题的解。

即将原问题分而治之，再合并得到结果。

分治法适用的问题

能够用分治法解决的问题，通常有以下四个特点：

1. 当划分出的子问题规模足够小的时候，可以直接求解
2. 该问题能够划分成若干个规模更小的子问题
3. 划分出来的子问题的解合并之后即为原问题的解
4. 该问题分解得到的各个子问题是相互独立的

第二条特征也符合递归的思想，所以分治法与递归经常一起出现。

分治法的操作步骤

分治法在每一层递归中都实现三个步骤：

• 分解（Divide）：将现问题分解成若干个规模更小的子问题
• 求解（Conquer）：若子问题可直接求解，则直接求解；否则，递归的求解子问题（即将子问题继续分解）
• 合并（Merge）：将子问题的解合并起来得到父问题的解

其伪代码如下：

Divide-and-Conquer(P)1. if |P|≤n02. then return(ADHOC(P))3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk4. for i←1 to k5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi6. T ← MERGE(y1,y2,...,yk) △ 合并子问题7. return(T)

∣ P ∣ |P| ∣P∣表示问题的规模， n 0 n0 n0为阙值，如果 ∣ P ∣ ≤ n 0 |P|≤n0 ∣P∣≤n0，则用 A D H O C ( ) ADHOC() ADHOC()函数直接求解问题P，

如果问题规模 ∣ P ∣ > n 0 |P|>n0 ∣P∣>n0，则将问题P分解为较小的子问题 P 1 , P 2 , P 3 , . . . , P k P_1,P_2,P_3,...,P_k P1​,P2​,P3​,...,Pk​，递归地求解子问题

最后将子问题 P 1 , P 2 , P 3 , . . . , P k P_1,P_2,P_3,...,P_k P1​,P2​,P3​,...,Pk​的解合并为原问题P的解

实例

• 二分搜索

二分搜索是一个典型的运用了分治法的算法

def BinarySearch(array, value):low = 0high = len(array) - 1while low <= high:mid = (low + high) // 2if value == array[mid]:return mid elif value < array[mid]:high = mid - 1else:low = mid + 1

在一个数组中查找一个值，分解为在前半个数组或者后半个数组中查找一个值，不断递归求解，直到数组的长度为1，即问题的规模小到一定程度，可以直接求解，得到的结果就是原问题的解，自然符合合并之后的解为原问题的解这一条。