Разделить и покорить самый близкий пара-алгоритм

Question

Я пытаюсь создать алгоритм, который возвращает ближайшую пару из случайно созданных точек. Я закончил алгоритм, однако метод разделения и захвата алгоритма не намного быстрее, чем метод грубой силы. Что я могу сделать для оптимизации кода, чтобы он возвращался в (n log n) времени?

import java.util.*; 
import java.lang.*; 
import static java.lang.Math.min; 
import static java.lang.StrictMath.abs; 

public class closestPair { 

    private static Random randomGenerator; // for random numbers 

    public static class Point implements Comparable<Point> { 

     public long x, y; 

     // Constructor 
     public Point(long x, long y) { 
      this.x = x; 
      this.y = y; 
     } 

     public int compareTo(Point p) { 
      // compare this and p and there are three results: >0, ==0, or <0 
      if (this.x == p.x) { 
        if (this.y == p.y) 
         return 0; 
        else 
         return (this.y > p.y)? 1 : -1; 
       } 
      else 
        return (this.x > p.x)? 1 : -1; 
     } 

     public String toString() { 
      return " ("+Long.toString(this.x)+","+Long.toString(this.y)+")"; 
     } 

     public double distance(Point p) { 
      long dx = (this.x - p.x); 
      long dy = (this.y - p.y); 
      return Math.sqrt(dx*dx + dy*dy); 
     } 
    } 

    public static Point[] plane;   

     public static Point[] T; 

     public static Point[] Y; 

    public static int N; // number of points in the plane 

    public static void main(String[] args) { 

     // Read in the Size of a maze 
     Scanner scan = new Scanner(System.in);   
     try {   
      System.out.println("How many points in your plane? "); 
      N = scan.nextInt(); 
     } 
     catch(Exception ex){ 
      ex.printStackTrace(); 
     } 
     scan.close(); 

     // Create plane of N points. 
     plane = new Point[N]; 
       Y = new Point[N]; 
       T = new Point[N]; 
     randomGenerator = new Random(); 

     for (int i = 0; i < N; ++i) { 
      long x = randomGenerator.nextInt(N<<6); 
      long y = randomGenerator.nextInt(N<<6); 
      plane[i] = new Point(x, y); 
     } 
     Arrays.sort(plane); // sort points according to compareTo. 
     for (int i = 1; i < N; ++i) // make all x's distinct. 
      if (plane[i-1].x >= plane[i].x) plane[i].x = plane[i-1].x + 1; 

        //for (int i = 1; i < N; i++) 
         //  if (plane[i-1].y >= plane[i].y) plane[i].y = plane[i-1].y + 1; 
          // 
          //  
     System.out.println(N + " points are randomly created.");   
     System.out.println("The first two points are"+plane[0]+" and"+plane[1]); 
     System.out.println("The distance of the first two points is "+plane[0].distance(plane[1])); 


       long start = System.currentTimeMillis(); 
     // Compute the minimal distance of any pair of points by exhaustive search. 
     double min1 = minDisSimple(); 
       long end = System.currentTimeMillis(); 
     System.out.println("The distance of the two closest points by minDisSimple is "+min1); 
       System.out.println("The running time for minDisSimple is "+(end-start)+" mms"); 
     // Compute the minimal distance of any pair of points by divide-and-conquer 
     long start1 = System.currentTimeMillis(); 
       double min2 = minDisDivideConquer(0, N-1); 
       long end1 = System.currentTimeMillis(); 

     System.out.println("The distance of the two closest points by misDisDivideConquer is "+min2); 
       System.out.println("The running time for misDisDivideConquer is "+(end1-start1)+" mms"); 

     }  

    static double minDisSimple() { 
     // A straightforward method for computing the distance 
     // of the two closest points in plane[0..N-1]. 

     // to be completed 
      double midDis = Double.POSITIVE_INFINITY; 
     for (int i = 0; i < N - 1; i++) { 
       for (int j = i + 1; j < N; j++) { 
        if (plane[i].distance(plane[j]) < midDis){ 
         midDis = plane[i].distance(plane[j]); 
        }    
       } 
      } 
     return midDis; 

     } 


     static void exchange(int i, int j) { 
     Point x = plane[i]; 
     plane[i] = plane[j]; 
     plane[j] = x; 
     } 

    static double minDisDivideConquer(int low, int high) { 
      // Initialize necessary values 
      double minIntermediate; 
      double minmin; 
      double minDis; 

     if (high == low+1) { // two points 
       if (plane[low].y > plane[high].y) exchange(low, high); 
       return plane[low].distance(plane[high]); 
     } 
      else if (high == low+2) { // three points 
      // sort these points by y-coordinate 
      if (plane[low].y > plane[high].y) exchange(low, high); 
      if (plane[low].y > plane[low+1].y) exchange(low, low+1); 
      else if (plane[low+1].y > plane[high].y) exchange(low+1, high); 
      // compute pairwise distances 
      double d1 = plane[low].distance(plane[high]); 
      double d2 = plane[low].distance(plane[low+1]); 
      double d3 = plane[low+1].distance(plane[high]); 
      return ((d1 < d2)? ((d1 < d3)? d1 : d3) : (d2 < d3)? d2 : d3); // return min(d1, d2, d3) 
     } else { // 4 or more points: Divide and conquer 
       int mid = (high + low)/2; 
       double lowerPartMin = minDisDivideConquer(low,mid); 
       double upperPartMin = minDisDivideConquer(mid+1,high); 
       minIntermediate = min(lowerPartMin, upperPartMin); 
       int k = 0; 
       double x0 = plane[mid].x; 
       for(int i = 1; i < N; i++){ 
        if(abs(plane[i].x-x0) <= minIntermediate){ 
         k++; 
         T[k] = plane[i]; 
        } 
       } 
       minmin = 2 * minIntermediate; 
       for (int i = 1; i < k-1; i++){ 
        for(int j = i + 1; j < min(i+7,k);j++){ 
         double distance0 = abs(T[i].distance(T[j])); 
         if(distance0 < minmin){ 
          minmin = distance0; 
         } 
        } 
       } 
       minDis = min(minmin, minIntermediate); 
      } 
      return minDis; 
     } 
    } 

Answer 1

Используйте следующий метод с заменой для minDisSimple. Вы можете повысить производительность.

static double minDisSimple() { 
    // A straightforward method for computing the distance 
    // of the two closest points in plane[0..N-1]. 

    // to be completed 
    double midDis = Double.POSITIVE_INFINITY; 
    double temp; 
    for (int i = 0; i < N - 1; i++) { 
     for (int j = i + 1; j < N; j++) { 
      temp = plane[i].distance(plane[j]); 
      if (temp < midDis) { 
       midDis = temp; 
      } 
     } 
    } 
    return midDis; 

} 

Производительность мудрого для небольшого количества пунктов простой метод хороший, но большее количество пунктов Разделить и завоевать хорошо. Попытка количество точек с 10, 100, 1000, 10000, 100000, 1000000.

Answer 2

Одним из наиболее важных аспектов в minDisDivideConquer() является то, что цикл, который строит вспомогательный массив T итерацию по всем пунктам N. Так как есть итоговые рекурсивные вызовы O(N), что делает этот проход через все N точек каждый раз приводит к сложности O(N^2), что эквивалентно простому алгоритму.

Петля должна фактически рассматривать точки с индексами между low и high. Кроме того, его можно разделить на две отдельные петли, начинающиеся с mid (вперед и назад) и разрываются, когда пройденное расстояние уже слишком велико.

---

Другим возможным улучшение для метода minDisDivideConquer(), в «4 или более точек» ситуации, чтобы предотвратить глядя на пары, которые уже были рассмотрены в рекурсивных вызовов.

Если мое понимание верное, массив T содержит те точки, которые достаточно близки по оси х до средней точки, так что существует вероятность того, что пара точек в T будет создавать расстояние, меньшее, чем у человека половина комплектов.

Однако нет необходимости искать точки, которые находятся перед mid, или оба после mid (так как эти пары уже учитывались при рекурсивных вызовах).

Таким образом, возможно оптимизация построить два списка T_left и T_right (вместо T) и проверить расстояния между парами точек, одна находится на левой mid, а другой справа. Таким образом, вместо вычисления расстояний |T| * (|T| - 1)/2 мы рассмотрим только |T_left| * |T_right| пар, с |T_left| + |T_right| = |T|. Это значение не более (|T|/2) * (|T|/2) = |T|^2/4, т. Е. примерно в 2 раза меньше расстояний, чем раньше (это в худшем случае, но фактическое число пар также может быть намного меньше, включая ноль).