Teilen und Conquer am nächsten Paar Algorithmus

Question

Ich versuche, einen Algorithmus zu erstellen, der das am nächsten gelegene Paar aus zufällig generierten Punkten zurückgibt. Ich habe den Algorithmus beendet, aber die Divide and Conquer-Methode des Algorithmus ist nicht viel schneller als die Brute-Force-Methode. Was kann ich tun, um den Code so zu optimieren, dass er zur (n log n) Zeit zurückkehrt?

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

Verwenden Sie die folgende Methode mit der Änderung für minDisSimple. Sie können mehr Leistung erzielen.

Leistung weise für kleine Anzahl von Punkten einfache Methode ist gut, aber größere Anzahl von Punkten Teilen und beherrschen ist gut. Versuchen Anzahl der Punkte mit 10, 100, 1000, 10000, 100000, 1000000

Answer 2

Ein kritischer Aspekt bei der minDisDivideConquer() ist, dass die Schleife, die die Hilfsgruppen T iteriert durch alle Punkte N Konstrukten. Da es insgesamt O(N) rekursive Aufrufe gibt, führt dies dazu, dass alle N Punkte jedes Mal durchlaufen werden, zu einer Komplexität von O(N^2), die der des einfachen Algorithmus entspricht. Die Zeile sollte eigentlich nur die Punkte mit Indizes zwischen low und high berücksichtigen. Darüber hinaus könnte es in zwei separate Schleifen aufgeteilt werden, die von mid (vorwärts und rückwärts) beginnen, und brechen, wenn die geprüfte Entfernung bereits zu groß ist.

---

Eine weitere mögliche Verbesserung für die minDisDivideConquer() Verfahren, in dem „4 oder mehr Punkte“ Situation ist ein Blick in Paaren zu verhindern, die bereits in den rekursiven Aufrufen berücksichtigt wurden. Wenn das Verständnis stimmt, enthält das Array T die Punkte, die nahe genug auf der X-Achse zum Mittelpunkt sind, so dass die Wahrscheinlichkeit besteht, dass ein Punktepaar in T einen kleineren Abstand als die des Individuums erzeugt halbe Sätze.

Es ist jedoch nicht notwendig, Punkte zu untersuchen, die beide vor mid oder beide nach mid liegen (da diese Paare bereits in den rekursiven Aufrufen berücksichtigt wurden).

Somit ist eine mögliche Optimierung ist und zwei Listen T_leftT_right (statt T) und überprüfen Entfernungen zwischen Paaren von Punkten zu konstruieren, so dass eine auf der linken Seite von mid ist, und das andere nach rechts. Auf diese Weise, anstatt |T| * (|T| - 1)/2 Entfernungen zu berechnen, würden wir nur in |T_left| * |T_right| Paare suchen, mit |T_left| + |T_right| = |T|. Dieser Wert ist höchstens 2 mal weniger Abstände als zuvor (dies ist im schlimmsten Fall, aber die tatsächliche Anzahl der Paare kann auch viel kleiner sein, einschließlich Null).