ปัญหาคะแนนคู่ที่ใกล้เคียงที่สุด

ในปัญหานี้ ชุดของ n จุดจะได้รับบนระนาบ 2D ในปัญหานี้เราต้องหาคู่ของคะแนนที่มีระยะห่างน้อยที่สุด

เพื่อแก้ปัญหานี้ เราต้องแบ่งจุดออกเป็นสองส่วน หลังจากนั้นระยะทางที่เล็กที่สุดระหว่างจุดสองจุดที่คำนวณแบบเรียกซ้ำ โดยใช้ระยะห่างจากเส้นกลาง จุดต่างๆ จะแยกออกเป็นแถบบางๆ เราจะหาระยะทางที่เล็กที่สุดจากอาร์เรย์แถบ ในตอนแรกสองรายการจะถูกสร้างขึ้นด้วยจุดข้อมูล รายการหนึ่งจะเก็บคะแนนซึ่งจัดเรียงตามค่า 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

แถบปิด(แถบ ขนาด ระยะ)

ป้อนข้อมูล - จุดต่างๆ ในแถบ จำนวนจุด ระยะห่างจากเส้นกึ่งกลาง

ผลลัพธ์ − ระยะทางที่ใกล้ที่สุดจากจุดสองจุดในแถบหนึ่ง

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