【计算机算法设计与分析】最近点对问题（C++_分治）

问题描述

????????我们给定了一个平面上由 n 个点组成的数组，问题是找出数组中最接近的一对点。这个问题在很多应用中都会出现。例如，在空中交通管制中，您可能想要监控靠得太近的飞机，因为这可能预示着可能会发生碰撞。下式表示两点 p 和 q 之间的距离。

算法原理

最近点对问题的暴力解法为 O(n^2)，计算每对点间的距离，并返回最小的距离。

分治算法求解当前问题时，每次分治都将二维平面分成左右两半，那么显然最近点对要么两个点都在左侧、要么都在右侧、要么左右各一个。针对点对在左侧和右侧的情况，我们只需要不断分治，直到一侧只有两个点的时，最近点对距离就是这两个点之间的距离dis；对于左右各一个点的情况，我们先按照之前的策略找到中线两侧分别的最近距离，然后再在中线两侧以两侧最短距离dis为界划出一个宽为2*dis的区域，再在这个区域内按照暴力解法找最近点对即可（按照鸽巢原理，只需要暴力遍历六个点即可）。

现有点集S={(x1,y1), (x2, y2), …, (xn, yn)}，分治解法分为以下几步：

1. 对所有的点对按照x排序，以便后从中位数划分区域。
2. 如果n=1，则返回无穷大，算法结束。（递归出口1）
3. 如果n=2，则返回当前两点之间的距离，算法结束。（递归出口2）
4. 计算中位数(之前已经排过序了)：mid=(left+right)/2。
5. 递归计算左/右两侧最近点对距离：mindis1和mindis2。
6. 计算两侧最近点对mindis=min(mindis1, mindis2)。
7. 对当前（left，right）的所有点按照y排序。
8. 遍历找到所有x在中间区域（mid-mindis， mid+mindis）的点。
9. 计算中间区域点对的最短距离middis并更新最近点对距离mindis=min(mindis, mindis)。

算法实现

#include <bits/stdc++.h>
#define pN 1000
using namespace std;

struct Node
{
	double x, y;
};
int pointNumber = pN;
Node P[pN];

bool cmp(Node& a, Node& b) {
	return a.x < b.x;
}

void Merge(int l, int r) {//归并排序的归并操作（对y排序）
	int mid = (l + r) / 2, i = l, j = mid + 1;
	vector<Node> temp;
	while (i <= mid && j <= r) {
		if (P[i].y < P[j].y) 
			temp.push_back(P[i++]);
		else 
			temp.push_back(P[j++]);
	}
	while (i <= mid)
		temp.push_back(P[i++]);
	while (j <= r)
		temp.push_back(P[j++]);
	for (int i = l; i < temp.size(); i++)
		P[i] = temp[i];
}
void CreatePoints(Node Points[], int pointNumber) {//随机生成点数据
	srand(time(NULL));
	for (int i = 0; i < pointNumber; i++) {
		Points[i].x = rand();
		Points[i].y = rand();
		//每1000个数据乘以一个特定的数，将数据尽量分散，减少重复
		Points[i].x *= ((i / 1000.0) + 1);
		Points[i].y *= ((i / 1000.0) + 1);
		for (int j = 0; j < i; j++) {//遍历已经生成的所有点，一旦发现重合则重新生成该点
			if (Points[j].x == Points[i].x && Points[j].y == Points[i].y) {
				i--;
				break;
			}
		}
	}
}
double dis(Node p1, Node p2) {//计算点对距离
	return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
double mergeMethod(Node P[], int l, int r, Node &p1, Node &p2) {//分治思路处理最近点对问题
	if (r - l <= 1)
		return INT_MAX;
	else if (r - l == 2) {
		Merge(l, r);//确保每个小单元的两个点对的y轴是有序的，才能保证后续对y归并排序的复杂度
		p1 = P[l];
		p2 = P[r];
		return dis(p1, p2);
	}
	else {
		Node l1, l2, r1, r2;
		int mid = (l + r) / 2;
		double mindis=INT_MAX;
		double middleX = P[mid].x; //中线
		double mindis1 = mergeMethod(P, l, mid, l1, l2); //左侧最近点对
		double mindis2 = mergeMethod(P, mid + 1, r, r1, r2); //右侧最近点对
		if (mindis1 < mindis2) {
			mindis = mindis1;
			p1 = l1;
			p2 = l2;
		}
		else{
			mindis = mindis2;
			p1 = r1;
			p2 = r2;
		}
		vector<Node> temp;
		Merge(l, r);//按照y排序
		for (int i = l; i <= r; i++) {  //找到在中间区域的点
			if (fabs(P[i].x - middleX) <= mindis) {
				temp.push_back(P[i]);
			}
		}
		double tempDis = INT_MAX;
		for (int i = 0; i < temp.size(); i++) {  //遍历中间数组，每个点最多遍历其他点6次，记录最短距离和点对
			for (int j = i + 1; j < i + 1 + 6 && j < temp.size(); j++) {
				tempDis = dis(temp[i], temp[j]);
				if (tempDis < mindis) {
					mindis = tempDis;
					p1 = temp[i];
					p2 = temp[j];
				}
			}
		}
		temp.clear();
		return mindis;
	}
}

void NPOP() {
	CreatePoints(P, pointNumber);  //随机生成测试数据
	cout << "所有点对：" << endl;
	for (int i = 0; i < pointNumber; i++)
		cout << "（" << P[i].x << ", " << P[i].y << "）" << endl;
	cout << "------------------"<<endl;
	Node minPoint1, minPoint2;
	sort(P, P + pointNumber, cmp);  //对x进行快排
	double dis = mergeMethod(P, 0, pointNumber - 1, minPoint1, minPoint2);  //分治算法求解最近点对
	cout << "最近点对距离："<< dis << endl;
	cout << "最近点对：（" << minPoint1.x << "," << minPoint1.y << "）-（" << minPoint2.x << "," << minPoint2.y << ")" << endl;
}

参考资料

1. 4.7 最近点对问题
2. 分治法与蛮力法求最近点对问题（分治法时间复杂度O(nlogn))