按兴趣点之间的距离排序

Question

我有一个以点对象作为输入的数组。我想对这些点进行排序，得到一个包含所有点的最短路线的数组。到目前为止，这是我的代码，但我还没有弄清楚，一旦使用了点，如何删除它们。

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;
    }
    

Answer 1

您显然试图解决的问题没有意义。

或者至少......子问题没有。

如果有

N

个点，那么它们之间的成对距离的 number 就是

(N-1)^2

。对于每个给定点 P，到其他点有

N - 1

距离。您无法基于此为点定义相关/易于计算的排序。所以排序没有意义。

你可以做的就是取一个点并根据到该点的距离对其他点进行排序（和排序）。但这意味着总共 N 个点，您有 N 个单独的排序。

请注意，您在这里尝试解决的是 “旅行商¹ 问题”(TSP) 的一种形式。 TSP 已被数学证明是一个“NP 完全”问题。这应该告诉您尝试通过排序来解决它（即O(NlogN)）是行不通的。

我的建议是：

阅读一些关于 TSP 的文章以及为什么它很难

1. 尽量避免寻找问题的精确解决方案
2. 查看寻找近似解决方案的技术/算法......而不是尝试发明自己的算法。
3. 寻找现有的图书馆。

---

1 - 或“旅行推销员问题”。不，我不是在开玩笑。

Answer 2

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;
    }

}

Answer 3

(
    local arr = #($Point001)
    local objs = selection as array
        
    print objs; print "----------"
    
    for x = objs.count to 1 by -1 do (
        local tmparr = for i = 1 to objs.count collect (distance arr[arr.count] objs[i])
        local idx = finditem tmparr (amin tmparr)
        append arr objs[idx]
        deleteItem objs idx
    )
    print arr
)