治法(Divide-and-Conquer-)"/>
分治法(Divide-and-Conquer-)
分治法(Divide-and-Conquer-)
基本概念
分治法:将原问题(通常是规模较大的问题)分解为若干个结构相似且相互独立的子问题,递归的求解这些子问题,最后将子问题的解合并起来,得到原问题的解。
即将原问题分而治之,再合并得到结果。
分治法适用的问题
能够用分治法解决的问题,通常有以下四个特点:
- 当划分出的子问题规模足够小的时候,可以直接求解
- 该问题能够划分成若干个规模更小的子问题
- 划分出来的子问题的解合并之后即为原问题的解
- 该问题分解得到的各个子问题是相互独立的
第二条特征也符合递归的思想,所以分治法与递归经常一起出现。
分治法的操作步骤
分治法在每一层递归中都实现三个步骤:
- 分解(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,即问题的规模小到一定程度,可以直接求解,得到的结果就是原问题的解,自然符合合并之后的解为原问题的解这一条。
更多推荐
分治法(Divide-and-Conquer-)
发布评论