資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究最近點對問題
在這個問題中，給定二維平面上的n個點集。在這個問題中，我們必須找到距離最小的點對。
為了解決這個問題，我們必須將點分成兩半，之後以遞迴方式計算兩點之間的最小距離。使用來自中線的距離，將點分成一些條帶。我們將找到條帶陣列中最小的距離。首先建立兩個包含資料點的列表，一個列表將儲存按x值排序的點，另一個列表將儲存按y值排序的資料點。
該演算法的時間複雜度為O(n log n)。
輸入和輸出
Input: A set of different points are given. (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4) Output: Find the minimum distance from each pair of given points. Here the minimum distance is: 1.41421 unit
演算法
findMinDist(pointsList, n)
輸入： 給定的點列表和列表中的點數。
輸出 − 找到兩點之間的最小距離。
Begin min := ∞ for all items i in the pointsList, do for j := i+1 to n-1, do if distance between pointList[i] and pointList[j] < min, then min = distance of pointList[i] and pointList[j] done done return min End
stripClose(strips, size, dist)
輸入 − 條帶中的不同點，點數，到中線的距離。
輸出 − 條帶中兩點之間的最短距離。
Begin for all items i in the strip, do for j := i+1 to size-1 and (y difference of ithand jth points) <min, do if distance between strip[i] and strip [j] < min, then min = distance of strip [i] and strip [j] done done return min End
findClosest(xSorted, ySorted, n)
輸入 − 按x值排序的點，按y值排序的點，點數。
輸出 − 找到整個點集中的最小距離。
Begin if n <= 3, then call findMinDist(xSorted, n) return the result mid := n/2 midpoint := xSorted[mid] define two sub lists of points to separate points along vertical line. the sub lists are, ySortedLeft and ySortedRight leftDist := findClosest(xSorted, ySortedLeft, mid) //find left distance rightDist := findClosest(xSorted, ySortedRight, n - mid) //find right distance dist := minimum of leftDist and rightDist make strip of points j := 0 for i := 0 to n-1, do if difference of ySorted[i].x and midPoint.x<dist, then strip[j] := ySorted[i] j := j+1 done close := stripClose(strip, j, dist) return minimum of close and dist End
示例
#include <iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct point {
int x, y;
};
intcmpX(point p1, point p2) { //to sort according to x value
return (p1.x < p2.x);
}
intcmpY(point p1, point p2) { //to sort according to y value
return (p1.y < p2.y);
}
float dist(point p1, point p2) { //find distance between p1 and p2
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
float findMinDist(point pts[], int n) { //find minimum distance between two points in a set
float min = 9999;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (dist(pts[i], pts[j]) < min)
min = dist(pts[i], pts[j]);
return min;
}
float min(float a, float b) {
return (a < b)? a : b;
}
float stripClose(point strip[], int size, float d) { //find closest distance of two points in a strip
float min = d;
for (int i = 0; i < size; ++i)
for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)
if (dist(strip[i],strip[j]) < min)
min = dist(strip[i], strip[j]);
return min;
}
float findClosest(point xSorted[], point ySorted[], int n){
if (n <= 3)
return findMinDist(xSorted, n);
int mid = n/2;
point midPoint = xSorted[mid];
point ySortedLeft[mid+1]; // y sorted points in the left side
point ySortedRight[n-mid-1]; // y sorted points in the right side
intleftIndex = 0, rightIndex = 0;
for (int i = 0; i < n; i++) { //separate y sorted points to left and right
if (ySorted[i].x <= midPoint.x)
ySortedLeft[leftIndex++] = ySorted[i];
else
ySortedRight[rightIndex++] = ySorted[i];
}
float leftDist = findClosest(xSorted, ySortedLeft, mid);
float rightDist = findClosest(ySorted + mid, ySortedRight, n-mid);
float dist = min(leftDist, rightDist);
point strip[n]; //hold points closer to the vertical line
int j = 0;
for (int i = 0; i < n; i++)
if (abs(ySorted[i].x - midPoint.x) <dist) {
strip[j] = ySorted[i];
j++;
}
return min(dist, stripClose(strip, j, dist)); //find minimum using dist and closest pair in strip
}
float closestPair(point pts[], int n) { //find distance of closest pair in a set of points
point xSorted[n];
point ySorted[n];
for (int i = 0; i < n; i++) {
xSorted[i] = pts[i];
ySorted[i] = pts[i];
}
sort(xSorted, xSorted+n, cmpX);
sort(ySorted, ySorted+n, cmpY);
return findClosest(xSorted, ySorted, n);
}
int main() {
point P[] ={{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
int n = 6;
cout<< "The minimum distance is " <<closestPair(P, n);
}輸出
The minimum distance is 1.41421
更新於: 2020年6月16日
11K+ 次瀏覽
廣告