化繁为简：分治法（Divide and conquer）

大家好，欢迎来到IT知识分享网。

背景

1、如何在一台PC上实现一个实现大规模的矩阵乘法计算？

2、MapReduce 在 Google 最大的应用是做网页的索引，其中的Map和Reduce分别代表什么意思？

分治法（Divide and conquer）

分治算法是一个解决复杂问题的好工具，它可以把问题分解成若干个子问题，把子问题逐个解决，再组合到一起形成大问题的答案。

分治法是建基于多项分支递归的一种很重要的算法范型。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

实现步骤

只需要三步。

1、分解：Divide

将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。

2、解决：Conquer

若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。

3、合并：Merge

将各子问题的解合并为原问题的解。

示例代码

分治法在高级语言中主要的一个思想是递归，LISP语言中的体现出了极丰富的分治法。

以下是归并排序示例代码，输入参数中，需要排序的数组为array[],起始索引为first，终止索引为last。

void merge_sort(int array[], unsigned int first, unsigned int last) { int mid = 0; if(first<last) { mid = (first+last)/2; merge_sort(array, first, mid); merge_sort(array, mid+1,last); merge(array,first,mid,last); } }

在程序中可以看出分治法的应用：在merge_sort()中，将原来针对索引first到last的数组排序的问题，分为二份较小的问题。

1、先针对索引first到mid的数组排序。

2、再针对索引mid+1到last的数组排序。

3、最后再进行二个数组的合并。

最近点对问题

最近点对问题是计算几何问题：给定度量空间中的 n 点，找到一对点之间距离最小的点。

最接近的点对以红色显示

分治法实现最近点对问题的解题思路：

1、划分点集：

将点集划分为两个子集，每个子集包含点数相等。

2、在每个子集中找到最近的点对：

对于每个子集，使用快速排序或其他排序算法找到子集中距离最近的两个点。

3、合并结果：

计算两个子集中最近的点对之间的距离。这个距离可能是全局最近的距离，但也可能不是。为了找到全局最近的距离，可以采用以下策略：a. 检查第一个子集中的每个点是否与第二个子集中的点更接近，如果是，则更新全局最近的距离。b. 反之，检查第二个子集中的每个点是否与第一个子集中的点更接近，如果是，则更新全局最近的距离。

4、递归地处理子集：

如果子集的大小大于1，继续将子集划分为两个子集，并递归地执行步骤1至3。

否则，直接返回当前子集中的最近点对作为全局最近的点对。

以下是一个用Python实现的最近点对问题的示例：

import math import sys def hoare_partition(A, lo, hi, c): i = lo+1 j = hi p = A[lo][c] while True: while((A[i][c] <= p) and (i < hi)): i += 1 while((A[j][c] >= p) and (j > lo)): j-= 1 if (i >= j): break temp = A[i] A[i] = A[j] A[j] = temp temp = A[j] A[j] = A[lo] A[lo] = temp return j # 修改后的快速排序用于排序元组列表。c 是用于排序顺序的元组组件。 def quick_sort(A, lo, hi, c): if(lo < hi): # 应用Hoare分区 s = hoare_partition(A, lo, hi, c) # 递归地排序左子和右子数组 quick_sort(A, lo, s-1, c) quick_sort(A, s+1, hi, c) # 递归实现最近对的算法 def closest_pair(A): # 预处理步骤 # 按 x 坐标的非递减顺序对点列表进行排序 quick_sort(A, 0, len(A)-1, 0) # 按 y 坐标非递减顺序排序 Q = A.copy() quick_sort(Q, 0, len(Q)-1, 1) # 全递归最近对算法 return closest_pair_rec(A, Q, 0, len(A)-1) def closest_pair_rec(A, Q, lo, hi): # 使用暴力解决递归 if((hi-lo+1) <= 3): return closest_pair_brute(A, lo, hi) else: # 递归地调用左和右子部分 mid = lo + math.floor((hi-lo)/2) p1_L, p2_L = closest_pair_rec(A, Q, lo, mid) p1_R, p2_R = closest_pair_rec(A, Q, mid+1, hi) if(dist(p1_L, p2_L) <= dist(p1_R, p2_R)): p1, p2 = p1_L, p2_L d = dist(p1_L, p2_L) else: p1, p2 = p1_R, p2_R d = dist(p1_R, p2_R) # 分区边界的 x 坐标 m = A[mid][0] # 从 y 坐标排序列表中复制以 m 为中心、宽度为 2*d min 的范围内的所有点 # （这些点位于距分区边界 d 的水平距离内） S= [p for p in Q if (abs(p[0] - m) < d)] # 找到距离小于当前已知的最接近点对的最接近点对 for i in range(len(S)-2): # 需要将条带中的每个点与按 y 坐标排序的最多接下来 5 个点进行比较 for k in range(i+1, min(i+5, len(S)-1)): dmin = dist(S[i], S[k]) if(dmin <= d): # 替换为最接近的新对 p1, p2 = S[i], S[k] d = dmin return p1, p2 # 最近对问题的暴力算法 def closest_pair_brute(A, lo, hi): if((hi-lo+1) == 2): return A[lo], A[lo+1] else: d = sys.float_info.max for i in range(lo, hi): for j in range(i+1, hi+1): if(dist(A[i], A[j]) <= d): d = dist(A[i], A[j]) p1 = A[i] p2 = A[j] return p1, p2 # 二维中两点之间的欧氏距离的平方 def dist(p1, p2): return ((p1[0]-p2[0])2 + (p1[1]-p2[1])2)

import matplotlib.pyplot as plt import numpy as np # 测试数据点 np.random.seed(1) Ax = np.random.randint(-200,201, size=(99)) Ay = np.random.randint(-200,201, size=(99)) A = [(x,y) for x,y in zip(Ax,Ay)] p1, p2 = closest_pair(A) p1s, p2s = closest_pair_brute(A, 0, len(A)-1) print(f"最接近的一对（分而治之）: {p1}, {p2}, distance: {np.sqrt(dist(p1, p2))}") print(f"最接近的一对（暴力）: {p1s}, {p2s}, distance: {np.sqrt(dist(p1s, p2s))}") A_wo_closest_pair = [(p[0],p[1]) for p in A if ((p != p1) and (p != p2))] x = [p[0] for p in A_wo_closest_pair] y = [p[1] for p in A_wo_closest_pair] plt.figure(figsize=(16,16)) plt.scatter(x,y) plt.scatter([p1[0], p2[0]],[p1[1], p2[1]], color='red') plt.grid() plt.show()

最接近的一对（分而治之）: (80, 138), (82, 140), distance: 2.61903 最接近的一对（暴力）: (80, 138), (82, 140), distance: 2.61903

可视化结果：

小结

对于分支法的理解可以分为三个层次：

第一层次：了解它的皮毛，会做算法书上的一些练习题，比如上面。

第二层次：能够灵活运用它的思想方法，用计算机来解决日常业务场景中遇到的问题。

第三层次：将分治法发扬光大，解决那些在别人看来无解的问题，比如云计算工具MapReduce和人工智能工具Google Brain。