Блог

У меня есть массив с точечными объектами в качестве входных данных. Я хочу отсортировать эти точки, чтобы получить массив с кратчайшим маршрутом, охватывающим все точки. до сих пор это мой код, но я не понял, как удалять точки, как только они были использованы.

 public Point[] poiSort(Point[] poi){
        poi = new Point[lenght 1];
        poi[0] = points[0];
        distances = new Double[lenght];
        double Distance = verybignumber;
        double Distancecompare;
        for (int i = 1; i < leght 1; i  ){
            for (int j = 1; j < (lenght); j  ){
                Distancecompare = points[i-1].getDistance(points[j]);
                if (Distance > Distancecompare){
                    Distance = Distancecompare;
                    poi[i] = points[j];
                    distances[i-1] = Disstance;
                }
            }
        }
        return poi;
    }
    
 

Вы можете создать новый массив во время сортировки и вернуть его в качестве результата. Таким образом, вам не нужно удалять элементы. В качестве альтернативы вы можете использовать список массивов или набор деревьев для большей гибкости. Вот, может быть, не такой элегантный, но рабочий пример с массивами:

 import java.util.Arrays;
import java.util.Comparator;
import java.util.Optional;

public class Main {
    
    public static void main(String... args) {
        
        Point[] points = {new Point(1,1), new Point(3,3), new Point(2,2)};
        Point[] result = sort(points);
        for (Point p : result) {
            System.out.println("point("   p.x   ", "   p.y   ")");
        }
        
    }
    
    public static Point[] sort(Point[] in) {
        if (in == null || in.length == 0) {
            return in;
        }
        Point[] out = new Point[in.length];
        Point current = in[0];
        for (int i = 0; i < in.length; i  ) {
            if (i == in.length -1) {
                out[in.length -1] = Arrays.stream(in).filter(p -> !p.visited).findAny().orElseGet(null);
                break;
            }
            final Point finalCurrent = current;     // variable must be final or effectively final as used in stream
            out[i] = finalCurrent;
            finalCurrent.visit();
            Point next = Arrays.stream(in).filter(p -> !p.visited).min(Comparator.comparingDouble(p -> p.getDistance(finalCurrent))).get();
            current = next;
        }
        return out;
    }
}



class Point {
    final double x;
    final double y;
    boolean visited;
    
    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
    
    public double getDistance(Point point) {
        return Math.abs(this.x-point.x)   Math.abs(this.y - point.y);
    }
    
    public void visit() {
        visited = true;
    }

}
 

Проблема, которую вы, по-видимому, пытаетесь решить, не имеет смысла.

Или, по крайней мере … подзадача этого не делает.

Если у вас есть N точки, то количество попарных расстояний между ними равно (N-1)^2 . Для каждой заданной точки P существуют N - 1 расстояния до других точек. Вы не можете определить соответствующий / легко вычислимый порядок для точек на основе этого. Так что сортировка не имеет смысла.

Что вы могли бы сделать, так это взять одну точку и упорядочить (и отсортировать) остальные в зависимости от расстояния до этой точки. Но это означает, что в общей сложности для N очков у вас есть N отдельных заказов.

Обратите внимание, что то, что вы пытаетесь решить здесь, является формой «Проблемы Коммивояжера ¹» (TSP). Математически доказано, что TSP является NP-полным. Это должно сказать вам, что попытка решить ее с помощью сортировки (которая есть O(NlogN) ) не сработает.

Мой совет был бы:

1. Почитайте немного о TSP и почему это трудно
2. Постарайтесь избежать необходимости искать точное решение проблемы
3. Посмотрите на методы / алгоритмы поиска приближенных решений … вместо того, чтобы пытаться изобрести свой собственный алгоритм.
4. Поищите существующую библиотеку.

^{1 — Или «Проблема коммивояжера». Нет, я не шучу.}