【算法设计与分析】分治法与最近点对问题

一、问题描述

设，，…，是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。

严格地讲，最接近点对可能多于一对，简单起见，只找出其中的一对作为问题的解。

二、问题分析

用分治法解决最近对问题，很自然的想法就是将集合S分成两个子集 和 ，每个子集中有n/2个点。然后在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，如果集合 S 中最接近的两个点都在子集 或 中，则问题很容易解决，如果这两个点分别在 和 中，问题就比较复杂了。

最近对问题的分治策略是：

⑴划分：将集合S分成两个子集和，设集合S的最近点对是和（），则会出现以下三种情况：

⑵求解子问题：对于划分阶段的情况①和②可递归求解，如果最近点对分别在集合S1和S2中，问题就比较复杂了。

⑶合并：比较在划分阶段三种情况下最近点对，取三者之中较小者为原问题的解。

为了使问题易于理解，先考虑一维的情形。

此时，S中的点退化为x轴上的n个点x1, x2, …, xn。用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S2含有点的个数相同。递归地在S1和S2上求出最接近点对 (p1, p2) 和(q1, q2)，如果集合S中的最接近点对都在子集S1或S2中，则d=min{(p1, p2), (q1, q2)}即为所求，如果集合S中的最接近点对分别在S1和S2中，则一定是(p3, q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。

下面考虑二维的情形，此时S中的点为平面上的点。

关键点1：分割点M的选取问题

仍以一维为例：选取分割点m的一个基本要求是由此导出集合S的一个线性分割，即S=S1∪S2 ，S1∩S2=Φ，且S1={x|x≤m}；S2={x|x>m}。容易看出，一维情况下，如选m=[max(S)+min(S)]/2，可以满足线性分割的要求。选取分割点后，再用O(n)时间即可将S划分成S1={x∈S|x≤m}和S2={x∈S|x>m}。然而，这样选取分割点m，有可能造成划分出的子集S1和S2的不平衡。

例如在最坏情况下，|S1|=1，|S2|=n-1，由此产生的分治法在最坏情况下所需的计算时间T(n)应满足递归方程:

　　T(n)=T(n-1)+O(n)    它的解是T(n)=O(n2)。

这种效率降低现象可通过分治法中“平衡子问题”方法加以解决。即通过适当选择分割点m，使S1和S2中有大致相等个数的点。

因此，用S的n个点的坐标的中位数来作分割点。在选择算法中介绍的选取中位数的线性时间算法使我们可以在O(n)时间内确定一个平衡的分割点m。

以上情况可以方便推广到二维，即二维情况下，m取S中各点x坐标的中位数。—中位数是指将数据按大小顺序排列起来，形成一个数列，居于数列中间位置的那个数据。

关键点2：情况③的求解

为了将平面上的点集S 分割为点的个数大致相同的两个子集S1和S2，选取垂直线x=m来作为分割线，其中，m为S中各点x坐标的中位数。由此将S分割为S1={p∈S | xp≤m}和S2={q∈S | xq＞m}。递归地在S1和S2上求解最近对问题，分别得到S1中的最近距离d1和S2中的最近距离d2，令d=min(d1, d2)，若S的最近对(p, q)之间的距离小于d，则p和q必分属于S1和S2，不妨设p∈S1，q∈S2，则p和q距直线x=m的距离均小于d(否则就p,q的距离就大于d),所以，可以将求解限制在以x=m为中心、宽度为2d的垂直带P1和P2中，垂直带之外的任何点对之间的距离都一定大于d。

假设p(x,y)是P1和P2中y坐标最小的点，由于p 可能在P1或P2，所以需要找与p距离小于d的点，显然，这样点的y轴坐标一定位于区间[y, y+d]之间，而且，这样的点不会超过8个（鸽笼原理可以证明P1和P2 分别为4个）。---如果超过了8个，例如9个，那么必有2两个点距离小于d

处理方法：将P1和P2中的点按y的升序排列，顺序处理P1和P2中的点p(x,y),在y坐标区间中最多取8个点，计算其与点p 的距离。

三、算法设计

四、实验代码

完整VS2017项目：https://github.com/cxh1231/Junior-Algorithm-ClosestPointProblem

#include <iostream>
#include <math.h>
using namespace std;

const int n = 8;

//定义结构体表示集合S中的 点的坐标
struct point{
	int x, y;
};

double Closest(point S[], int low, int high);		//实现求最近对距离
double Distance(point a, point b);					//求两点之间距离
int Partition(point r[], int first, int end);		//划分【课本P62】
void QuickSort(point r[], int first, int end);		//快速排序【课本P63】

//实现求最近对距离
double Closest(point S[], int low, int high){
	double d1, d2, d3, d;
	int mid, i, j, index;
	point P[n];                   //存放点集合 P1和P2

	//如果只有两个点，返回这两个点间的距离
	if (high - low == 1) {
		return Distance(S[low], S[high]);
	}

	//如果有三个点，求最近点对距离
	if (high - low == 2)	{
		d1 = Distance(S[low], S[low + 1]);
		d2 = Distance(S[low + 1], S[high]);
		d3 = Distance(S[low], S[high]);
		if ((d1 < d2) && (d1 < d3))	return d1;
		else if (d2 < d3) return d2;
		else return d3;
	}

	mid = (low + high) / 2;				//计算中间点
	d1 = Closest(S, low, mid);			//递归求解子问题①
	d2 = Closest(S, mid + 1, high);		//递归求解子问题②

	if (d1 <= d2) d = d1;				//已下为求解子问题③
	else d = d2;
	index = 0;
	for (i = mid; (i >= low) && (S[mid].x - S[i].x < d); i--)			//建立点集合P1
		P[index++] = S[i];
	for (i = mid + 1; (i <= high) && (S[i].x - S[mid].x < d); i++)		//建立点集合P2
		P[index++] = S[i];

	//对集合P1、P2按y坐标升序排列
	QuickSort(P, 0, index - 1);
	
	//依次处理集合P1和P2中的点
	for (i = 0; i < index; i++)	{
		for (j = i + 1; j < index; j++)		{
			if (P[j].y - P[i].y >= d)		//超出y坐标的范围，点P[i]处理完毕
				break;
			else			{
				d3 = Distance(P[i], P[j]);
				if (d3 < d)
					d = d3;
			}
		}
	}
	return d;
}

//求两点之间距离
double Distance(point a, point b){
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

//划分【课本P62】
int Partition(point r[], int first, int end){				//划分
	int i = first, j = end;									//初始化待划分区间
	while (i < j)	{
		while (i < j && r[i].y <= r[j].y) j--;				//右侧扫描
		if (i < j) {
			point temp = r[i]; r[i] = r[j]; r[j] = temp;	//将较小记录交换到前面
			i++;
		}
		while (i < j && r[i].y <= r[j].y) i++;				//左侧扫描
		if (i < j) {
			point temp = r[i]; r[i] = r[j]; r[j] = temp;    //将较大记录交换到后面
			j--;
		}
	}
	return i;												// 返回轴值记录的位置
}

//快速排序【课本P63】
void QuickSort(point r[], int first, int end){  //快速排序
	int pivot;
	if (first < end) {
		pivot = Partition(r, first, end);		//划分，pivot是轴值在序列中的位置
		QuickSort(r, first, pivot - 1);			//求解子问题1，对左侧子序列进行快速排序
		QuickSort(r, pivot + 1, end);			//求解子问题2，对右侧子序列进行快速排序
	}
}


int main()
{
	//输入按x坐标升序排列的n个点的集合
	point S[n] = { {1,4},{1,8},{2,1},{3,2},{4,4},{5,1},{6,6},{7,2} };
	double minDist = Closest(S, 0, n - 1);
	//输出最近点对的距离
	cout << "最近点对距离为："<< minDist << endl;
	return 0;
}

五、运行结果

最近点对距离为：1.414……

六、总结

T(n)=O(nlog2n)