算法设计与实践-作业5-1 分治算法解决最近对问题
分治算法解决最近对问题
1. 问题
设P1(x1, y1)，P2(x2, y2)，P3(x3, y3), P4(x4, y4) …，是平面上n个散列点构成的集合S，最近对问题就是找出集合S中距离最近的点对。
2. 解析
将集合S分成两个子集S1和S2，每个子集中有n/2个点。然后在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，有两种可能：
① 集合S 中最接近的两个点都在子集S1或S2中
② 这两个点分别在S1和S2中。
最近对问题的分治策略是：
⑴ 划分：将集合S分成两个子集S1和S2，最近点对会出现三种情况：
① 两个点都在S1内
② 两个点都在S2内
③ 一个点在S1内一个点在S2内
⑵求解子问题：对于划分阶段的情况①和②可递归求解，如果最近点对分别在集合S1和S2中，问题就比较复杂了。
⑶合并：比较在划分阶段三种情况下最近点对，取三者之中较小者为原问题的解。
具体实例如下：
在集合S内有9个点，
① 分别按x由小到大排序(x 相同再按y由小到大排)；
② 取中位数点5(4,2)为中心，作一条x = 4的垂线将集合S分为集合S1和集合S2，再以S1，S2为新的集合继续递归划分成两个新的集合，递归的终止条件为当集合只剩下2个点或一个点时，直接求出距离，并记录下S1和S2的最短距离，将D = min（D1,
D2），其中D1，D2分别是S1和S2的最短距离。
③ 接下来我们来分析如果最近点对分别在S1和S2内的情况，以中心点向外分别作两条垂线x = 3 和 x = 5(原因：如果最近点对分别在S1和S2内，则它们的距离一点小于S1和S2内的最短距离D),将x = 3 到 x = 5区域内的点按y排序，求出所有点之间的距离与D比较，求出集合S中的最近点对。