欢迎大家来到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); } }
欢迎大家来到IT世界,在知识的湖畔探索吧!
在程序中可以看出分治法的应用:在merge_sort()中,将原来针对索引first到last的数组排序的问题,分为二份较小的问题。
1、先针对索引first到mid的数组排序。
2、再针对索引mid+1到last的数组排序。
3、最后再进行二个数组的合并。
最近点对问题
最近点对问题是计算几何问题:给定度量空间中的 n 点,找到一对点之间距离最小的点。
分治法实现最近点对问题的解题思路:
1、划分点集:
将点集划分为两个子集,每个子集包含点数相等。
2、在每个子集中找到最近的点对:
对于每个子集,使用快速排序或其他排序算法找到子集中距离最近的两个点。
3、合并结果:
计算两个子集中最近的点对之间的距离。这个距离可能是全局最近的距离,但也可能不是。为了找到全局最近的距离,可以采用以下策略:a. 检查第一个子集中的每个点是否与第二个子集中的点更接近,如果是,则更新全局最近的距离。b. 反之,检查第二个子集中的每个点是否与第一个子集中的点更接近,如果是,则更新全局最近的距离。
4、递归地处理子集:
如果子集的大小大于1,继续将子集划分为两个子集,并递归地执行步骤1至3。
否则,直接返回当前子集中的最近点对作为全局最近的点对。
以下是一个用Python实现的最近点对问题的示例:
欢迎大家来到IT世界,在知识的湖畔探索吧!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()
欢迎大家来到IT世界,在知识的湖畔探索吧!最接近的一对(分而治之): (80, 138), (82, 140), distance: 2.61903 最接近的一对(暴力): (80, 138), (82, 140), distance: 2.61903
可视化结果:
小结
对于分支法的理解可以分为三个层次:
第一层次:了解它的皮毛,会做算法书上的一些练习题,比如上面。
第二层次:能够灵活运用它的思想方法,用计算机来解决日常业务场景中遇到的问题。
第三层次:将分治法发扬光大,解决那些在别人看来无解的问题,比如云计算工具MapReduce和人工智能工具Google Brain。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/95920.html