अंक एल्गोरिदम की निकटतम जोड़ी

Question

मैं इस एल्गोरिदम के एक सरल संस्करण को लागू करने की कोशिश कर रहा हूं लेकिन जो वर्गिक एल्गोरिदम से बेहतर काम करता है। मेरा विचार मूल रूप से केवल एक्स समन्वय द्वारा अंक को क्रमबद्ध करना है और इसे वहां से हल करने का प्रयास करना है। एक बार जब मैं एक्स समन्वय द्वारा अंक की अपनी सरणी को सॉर्ट करता हूं, तो मैं सरणी पर फिर से शुरू करना चाहता हूं और मूल रूप से उन बिंदुओं पर छोड़ना चाहता हूं जिनकी दूरी पहले दो बिंदुओं से अधिक है।

उदाहरण के लिए, मेरा currentminDist = x;

यदि दो बिंदुओं की जोड़ी मैं देख रहा हूं, तो दूरी> x (केवल इसके x समन्वय से) है, मैं बिंदु को अनदेखा करता हूं और इसे सरणी में पीछे ले जाता हूं।

मेरे पास विचार है, लेकिन मैं इस तरह से वास्तव में इसे लागू करने के तरीके पर अटक गया हूं (विशेष रूप से हालत भाग)। मेरे पास एक ऐसा कार्य है जो मुझे अपने एक्स समन्वय के आधार पर दो बिंदुओं के बीच की दूरी देता है।

मैं अपने लूप के लिए वास्तव में अपनी स्थितियों को लिखने के तरीके से उलझन में हूं क्योंकि मैं एक बिंदु को अनदेखा करना चाहता हूं अगर दूरी बहुत दूर होती है और फिर भी मेरी सरणी भरती है जिसमें प्रत्येक I के लिए निकटतम बिंदुओं के उत्तर होंगे (मैं वर्तमान बिंदु हूं मैं देख रहा हूँ)।

कोई सुझाव या निर्देशों की बहुत सराहना की जाएगी। मैं कोडिंग एल्गोरिदम में बहुत जानकार नहीं हूं इसलिए यह काफी निराशाजनक है।

for (i = 0; i < numofmypoints; i++) 
     { 
      for (int j = i + 1; (j < numpofmypoints) && ((inputpoints[j].x - inputpoints[i].x) < currbest); j++) 
      { 
       currdist = Auxilary.distbyX(inputpoints[i],inputpoints[j]); 

       if (currdist < bestdist) 
       { 
       closest[i] = j; 
       bestdist = currdist; 

       } 
      } 
     } 

distbyX मेरी समारोह है कि सिर्फ दो अंक के बीच की दूरी देता है:

यहाँ मेरी कोड का हिस्सा है।

धन्यवाद!

Answer 1

फास्ट एल्गोरिथ्म एक केडी-ट्री
इस एल्गोरिथ्म का उपयोग कर एक केडी पेड़ बनाता है और फिर प्रत्येक बिंदु के लिए निकटतम जोड़ी पाता है। केडी-पेड़ बनाना ओ (एन लॉग एन) है, और एक बिंदु के निकटतम पड़ोसी को ढूंढना ओ (लॉगन) है। क्रेडिट Wikipedia पर जाना चाहिए, जो एक लेख में बताता है कि केडी-पेड़ कैसे बनाएं और निकटतम पड़ोसी को ढूंढने के लिए उनका उपयोग कैसे करें। सवाल
में कोड को

import java.util.*; 

public class Program 
{ 
    public static void main(String[] args) 
    { 
     List<Point> points = generatePoints(); 
     Point[] closest = new Point[points.size()]; 

     KDTree tree = new KDTree(points, 0); // WILL MODIFY 'points' 

     for (int i = 0; i < points.size(); i++) 
     { 
      closest[i] = tree.findClosest(points.get(i)); 
     } 

     for (int i = 0; i < points.size(); i++) 
     { 
      System.out.println(points.get(i) + " is closest to " + closest[i]); 
     } 
    } 

    private static List<Point> generatePoints() 
    { 
     ArrayList<Point> points = new ArrayList<Point>(); 
     Random r = new Random(); 

     for (int i = 0; i < 1000; i++) 
     { 
      points.add(new Point(r.nextInt() % 1000, r.nextInt() % 1000)); 
     } 

     return points; 
    } 
} 

class Point 
{ 
    public static final Point INFINITY 
     = new Point(Double.POSITIVE_INFINITY, 
        Double.POSITIVE_INFINITY); 

    public double[] coord; // coord[0] = x, coord[1] = y 

    public Point(double x, double y) 
    { 
     coord = new double[] { x, y }; 
    } 

    public double getX() { return coord[0]; } 
    public double getY() { return coord[1]; } 

    public double distance(Point p) 
    { 
     double dX = getX() - p.getX(); 
     double dY = getY() - p.getY(); 
     return Math.sqrt(dX * dX + dY * dY); 
    } 

    public boolean equals(Point p) 
    { 
     return (getX() == p.getX()) && (getY() == p.getY()); 
    } 

    public String toString() 
    { 
     return "(" + getX() + ", " + getY() + ")"; 
    } 

    public static class PointComp implements Comparator<Point> 
    { 
     int d; // the dimension to compare in (0 => x, 1 => y) 

     public PointComp(int dimension) 
     { 
      d = dimension; 
     } 

     public int compare(Point a, Point b) 
     { 
      return (int) (a.coord[d] - b.coord[d]); 
     } 
    } 
} 

class KDTree 
{ 
    // 2D k-d tree 
    private KDTree childA, childB; 
    private Point point; // defines the boundary 
    private int d; // dimension: 0 => left/right split, 1 => up/down split 

    public KDTree(List<Point> points, int depth) 
    { 
     childA = null; 
     childB = null; 
     d = depth % 2; 

     // find median by sorting in dimension 'd' (either x or y) 
     Comparator<Point> comp = new Point.PointComp(d); 
     Collections.sort(points, comp); 

     int median = (points.size() - 1)/2; 
     point = points.get(median); 

     // Create childA and childB recursively. 
     // WARNING: subList() does not create a true copy, 
     // so the original will get modified. 
     if (median > 0) 
     { 
      childA = new KDTree(
       points.subList(0, median), 
       depth + 1); 
     } 
     if (median + 1 < points.size()) 
     { 
      childB = new KDTree(
       points.subList(median + 1, points.size()), 
       depth + 1); 
     } 
    } 

    public Point findClosest(Point target) 
    { 
     Point closest = point.equals(target) ? Point.INFINITY : point; 
     double bestDist = closest.distance(target); 
     double spacing = target.coord[d] - point.coord[d]; 
     KDTree rightSide = (spacing < 0) ? childA : childB; 
     KDTree otherSide = (spacing < 0) ? childB : childA; 

     /* 
     * The 'rightSide' is the side on which 'target' lies 
     * and the 'otherSide' is the other one. It is possible 
     * that 'otherSide' will not have to be searched. 
     */ 

     if (rightSide != null) 
     { 
      Point candidate = rightSide.findClosest(target); 
      if (candidate.distance(target) < bestDist) 
      { 
       closest = candidate; 
       bestDist = closest.distance(target); 
      } 
     } 

     if (otherSide != null && (Math.abs(spacing) < bestDist)) 
     { 
      Point candidate = otherSide.findClosest(target); 
      if (candidate.distance(target) < bestDist) 
      { 
       closest = candidate; 
       bestDist = closest.distance(target); 
      } 
     } 

     return closest; 
    } 
} 

फिक्स तुम सच में जटिलता के बारे में चिंता नहीं है, तो अपने कोड के साथ ही समस्या यह है कि आप आगे लेकिन पीछे की ओर नहीं लग रहे है। बस भीतरी पाश नकल और (i - 1)0 करने से j जाने बनाना:

Point[] points = sort(input()); 
int[] closest = new int[points.length]; 

for (int i = 0; i < points.length; i++) 
{ 
    double bestdist = Double.POSITIVE_INFINITY; 

    for (int j = i + 1; (j < points.length) && ((points[j].x - points[i].x) < bestdist); j++) 
    { 
     double currdist = dist(points[i], points[j]); 

     if (currdist < bestdist) 
     { 
      closest[i] = j; 
      bestdist = currdist; 
     } 
    } 
    for (int j = i - 1; (j >= 0) && ((points[i].x - points[j].x) < bestdist); j--) 
    { 
     double currdist = dist(points[i], points[j]); 

     if (currdist < bestdist) 
     { 
      closest[i] = j; 
      bestdist = currdist; 
     } 
    } 
}