Bài toán cặp điểm gần nhất (Closest Pair of Points)

Trong bài toán này, một tập hợp n điểm được cho trên mặt phẳng 2D. Ta phải tìm cặp điểm có khoảng cách nhỏ nhất.

Để giải quyết, ta chia các điểm thành hai nửa, sau đó tính khoảng cách nhỏ nhất giữa hai điểm theo cách đệ quy. Sử dụng khoảng cách từ đường giữa, các điểm được tách thành các dải (strips). Ta tìm khoảng cách nhỏ nhất từ mảng dải. Ban đầu tạo hai danh sách chứa các điểm dữ liệu: một danh sách giữ các điểm được sắp xếp theo giá trị x, danh sách kia giữ các điểm được sắp xếp theo giá trị y.

Độ phức tạp thời gian của thuật toán này là O(n log n).

Đầu vào và Đầu ra

Đầu vào: Một tập hợp các điểm khác nhau. (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)
Đầu ra: Tìm khoảng cách nhỏ nhất từ mỗi cặp điểm cho trước. Ở đây khoảng cách nhỏ nhất là: 1.41421 đơn vị

Thuật toán

findMinDist(pointsList, n)

Đầu vào: Danh sách điểm cho trước và số lượng điểm trong danh sách.

Đầu ra: Tìm khoảng cách nhỏ nhất từ hai điểm.

Bắt đầu
  min := vô cực
  với mọi phần tử i trong pointsList, thực hiện
    với j := i+1 đến n-1, thực hiện
      nếu khoảng cách giữa pointList[i] và pointList[j] < min thì
        min = khoảng cách của pointList[i] và pointList[j]
    kết thúc
  kết thúc
  trả về min
Kết thúc

stripClose(strips, size, dist)

Đầu vào: Các điểm khác nhau trong dải, số lượng điểm, khoảng cách từ đường giữa.

Đầu ra: Khoảng cách gần nhất từ hai điểm trong một dải.

Bắt đầu
  với mọi phần tử i trong dải, thực hiện
    với j := i+1 đến size-1 và (chênh lệch y của điểm i và j) < min, thực hiện
      nếu khoảng cách giữa strip[i] và strip[j] < min thì
        min = khoảng cách của strip[i] và strip[j]
    kết thúc
  kết thúc
  trả về min
Kết thúc

findClosest(xSorted, ySorted, n)

Đầu vào: Các điểm sắp xếp theo giá trị x, các điểm sắp xếp theo giá trị y, số lượng điểm.

Đầu ra: Tìm khoảng cách nhỏ nhất từ tổng tập hợp điểm.

Bắt đầu
  nếu n <= 3 thì
    gọi findMinDist(xSorted, n)
    trả về kết quả
  mid := n/2
  midpoint := xSorted[mid]
  định nghĩa hai danh sách con để tách điểm theo đường thẳng dọc.
  các danh sách con là ySortedLeft và ySortedRight
  leftDist := findClosest(xSorted, ySortedLeft, mid) // tìm khoảng cách bên trái
  rightDist := findClosest(xSorted, ySortedRight, n - mid) // tìm khoảng cách bên phải
  dist := minimum của leftDist và rightDist
  tạo dải các điểm
  j := 0
  với i := 0 đến n-1, thực hiện
    nếu chênh lệch của ySorted[i].x và midPoint.x < dist thì
      strip[j] := ySorted[i]
      j := j+1
    kết thúc
  kết thúc
  close := stripClose(strip, j, dist)
  trả về minimum của close và dist
Kết thúc

Ví dụ (C++)

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

struct point {
  int x, y;
};

int cmpX(point p1, point p2) {
  // để sắp xếp theo giá trị x
  return (p1.x < p2.x);
}

int cmpY(point p1, point p2) {
  // để sắp xếp theo giá trị y
  return (p1.y < p2.y);
}

float dist(point p1, point p2) {
  // tìm khoảng cách giữa p1 và 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) {
  // tìm khoảng cách nhỏ nhất giữa hai điểm trong một tập hợp
  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) {
  // tìm khoảng cách gần nhất của hai điểm trong một dải
  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];  // các điểm y sắp xếp ở bên trái
  point ySortedRight[n-mid-1]; // các điểm y sắp xếp ở bên phải
  int leftIndex = 0, rightIndex = 0;
  
  for (int i = 0; i < n; i++) {
    // tách các điểm y sắp xếp sang trái và phải
    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]; // giữ các điểm gần đường thẳng dọc
  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)); // tìm min dùng dist và cặp gần nhất trong dải
}

float closestPair(point pts[], int n) {
  // tìm khoảng cách của cặp gần nhất trong tập điểm
  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);
}

Đầu ra

The minimum distance is 1.41421