【Divide-and-Conquer】

程序员文章站 2022-06-02 11:52:24

...

The Closest-Pair Problem.

Description of problem.

Let P be a set of n>1 points in the Cartesian plane. For the sake of simplicity,we assume that the points are distinct.We can also assume the all the points are ordered in nondecreasing order of their x coordinate.If they were not, we could sort them first by an efficient sorting algorithm such as mergesort. It will also convenient to have the points sorted in a seperate list in nondecreasing order of the y coordinate; we denote such a list Q.
If 2≤n≤3, the problem can be solved by the obvious brute-force algorithm. If n>3, we can divide the points into 2 subsets P $_l$ and P $_r$ of n/2 points, respectively, by drawing a vertical line through the median m of the vertex x coordinates so that n/2 point lie to the left or on the line itself, and n/2 points lie to the right or on the line.
Then we can solve the Closest-Pair Problem recursively for subset P $_l$ and P $_r$ . Let d $_l$ and d $_r$ be the smallest distances between pairs of points in P $_l$ and P $_r$ , respectively,and let d=min(d $_l$ ,d $_r$ ).
Note that d is not necessarily the smallest distance between all the point pairs because points of a closer pair can lie on the opposite sides of the separating line. Therefore, as a step combining the solutions to the smaller subproblems, we need to examine such points. Obviously, we can limit our attention to the points inside the symmetric vertical strip of width 2d around the separating line, since the distance between any other pair of points is at least d.
【Divide-and-Conquer】
Let S be the list of points inside the strip of width 2d around the separating line, obtained from Q and hence ordered in nondecreasing of their y coordinate. We will scan this list, updating the information about d $_{min}$ , the minimum distance seen so far, if we encounter a closer pair of points. Initially, d $_{min}$ =d, and subsequently d $_{min}$ ≤d.Let p(x,y) be a point on this list.for a point p $_1$ (x $_1$ ,y $_1$ ) to have a chance to be closer to p than d $_{min}$ .The point p $_1$ must follow p on list S and the difference between their y coordinates must be less than d $_{min}$ .Geometrically, this means that p $_1$ must belong to the rectangle shown below.
【Divide-and-Conquer】
The principal insight exploited by the algorithm is the observation that the rectangle can contain just a few such points. Because the points in each half(up and down) of the rectangle must be at least d apart. It is easy to prove that the total number of such points in the rectangle,including p, does not exceed eight(divide the rectangle into 8 squares). A more careful analysis reduces this number to six by dividing this rectangle into 6 smaller rectangles whose length is d/2 and width is 2d/3. Thus, the algorithm can consider no more than five next points following p on the list, before moving up to the next poing.

Here is the pseudocode of the algorithm.
And the source of the EfficientClosestPair are showing as follows.

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

class Node
{
public:
	int x = 0;
	int y = 0;
	void set(int x, int y)
	{
		this->x = x;
		this->y = y;
	}
};

#define Sequence vector<Node>
bool myFunc_X(Node Vi, Node Vj);
bool myFunc_Y(Node Vi, Node Vj);
int EfficientClosestPair(Sequence P, Sequence Q);
int BruteForce(Sequence P);

int main()
{
	//The testing example.
	Sequence Initial(12);
	Initial[0].set(-1, 3);
	Initial[1].set(-2, -2);
	Initial[2].set(1,-4);
	Initial[3].set(2,1);
	Initial[4].set(1,5);
	Initial[5].set(3,3);
	Initial[6].set(3,0);
	Initial[7].set(5,1);
	Initial[8].set(7,3);
	Initial[9].set(7,6);
	Initial[10].set(5,6);
	Initial[11].set(3,7);

	//An array P sorted in nondecreasing order of x coordinates.
	sort(Initial.begin(), Initial.end(), myFunc_X);
	Sequence P(Initial);
	//An array Q sorted in nondecreasing order of y coordinates.
	sort(Initial.begin(), Initial.end(), myFunc_Y);
	Sequence Q(Initial);

	//If array.size no larger than 3,it can be solved by Brute-Force.
	//Obviously,here the size is 12.We select Divide-and-Conquer.

	int Distance = EfficientClosestPair(P, Q);
	cout << sqrt(Distance) << endl;

	return 0;
}

bool myFunc_X(Node Vi, Node Vj)
{
	return (Vi.x < Vj.x);
}

bool myFunc_Y(Node Vi, Node Vj)
{
	return (Vi.y < Vj.y);
}

int EfficientClosestPair(Sequence P, Sequence Q)
{
	if (P.size() > 3)
	{
		//Divide the points into two subsets.
		int mid = P.size() / 2;
		Sequence P_left(P.begin(), P.begin() + mid);
		Sequence P_right(P.begin() + mid, P.end());
		Sequence Q_left(P.begin(), P.begin() + mid);
		Sequence Q_right(P.begin() + mid, P.end());
		int d_min=min(EfficientClosestPair(P_left, Q_left),
			EfficientClosestPair(P_right, Q_right));
		int m = P[mid - 1].x;
		Sequence S;
		for (Sequence::iterator i = Q.begin(); i != Q.end(); ++i)
		{
			//Node whose x coordinate satisfies |x-m|<d.
			if ((i->x - m < d_min) || (m - i->x < d_min))
			{
				S.push_back(*i);
			}
		}
		for (int i = 0; i < S.size() - 1; ++i)
		{
			int k = i + 1;
			while (k < S.size() && (pow((S[k].y - S[i].y), 2) < d_min))
			{
				int d_cur = pow((S[k].x - S[i].x), 2) + pow((S[k].y - S[i].y), 2);
				d_min = min(d_min, d_cur);
				++k;
			}
		}
		return d_min;
	}
	else
	{
		return BruteForce(P);
	}
}

int BruteForce(Sequence P)
{
	int dis = INT_MAX;
	for (int i = 0; i < P.size() - 1; ++i)
	{
		int j = i + 1;
		int dis_cur = pow(P[i].x - P[j].x, 2) + pow(P[i].y - P[j].y, 2);
		dis = min(dis, dis_cur);
	}
	return dis;
}