分治法（Divide-and-Conquer-）

分治法（Divide-and-Conquer-）

基本概念

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

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

分治法适用的问题

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

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

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

分治法的操作步骤

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

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

其伪代码如下：

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$n0为阙值，如果$|P|≤n0$∣P∣≤n0，则用$ADHOC()$ADHOC()函数直接求解问题P，

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

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

实例

• 二分搜索

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

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

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