两点之间的最短路径是从点集合开始遍历所有其他点

本文关键字：开始 集合 遍历 点集 其他 两点 之间 最短路径 | 更新日期: 2023-09-27 18:02:41

给定一个由x和y坐标定义的点集合

在这个集合中，我得到了起点，终点和所有其他n-2个点。

我必须通过所有其他点找到起点和终点之间的最短路径。最短的路径由它的值和交叉点的顺序(如果可能的话)定义。

乍一看，这似乎是一个图形问题，但我现在不太确定，无论如何，我都试图通过使用几何关系找到这条最短的路，因为目前我拥有的所有信息只有点的x和y坐标，以及哪个点是起点，哪个是终点。

我的问题是，这个方法可以只用几何关系找到吗?

我正在尝试在c#中实现这个，所以如果有一些有用的包可用，请告诉我。

两点之间的最短路径是从点集合开始遍历所有其他点

最简单且性能合理的启发式是2-opt。将点放在一个数组中，起始点在前，结束点在后，重复尝试改进解，如下所示。选择起始索引i和结束索引j，并将子数组从i反向到j。如果总成本较低，则保留此更改，否则撤销更改。请注意，当且仅当d(p[i - 1]， p[i]) + d(p[j]， p[j + 1])> d(p[i - 1]， p[j]) + d(p[i]， p[j + 1])时，总成本会更低，因此您可以避免执行交换，除非它是一个改进。

这个方法可能有很多改进。3-opt和k-opt考虑了更多可能的走法，从而得到更好的解质量。几何搜索的数据结构，例如kd树，减少了寻找改进移动的时间。据我所知，TSP的局部搜索算法中最先进的是Keld helsgaon的LKH。

另一类算法是分支定界算法。这些返回最优解。协和式飞机(据我所知)在这里是最先进的。

这是Niklas描述的O(n^2 2^n) DP的Java实现。有许多可能的改进，例如，缓存点之间的距离，切换到浮点数(可能)，重新组织迭代，以便子集以大小递增的顺序枚举(允许仅保留最近的minTable层，从而节省大量空间)。

class Point {
    private final double x, y;
    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
    double distanceTo(Point that) {
        return Math.hypot(x - that.x, y - that.y);
    }
    public String toString() {
        return x + " " + y;
    }
}
public class TSP {
    public static int[] minLengthPath(Point[] points) {
        if (points.length < 2) {
            throw new IllegalArgumentException();
        }
        int n = points.length - 2;
        if ((1 << n) <= 0) {
            throw new IllegalArgumentException();
        }
        byte[][] argMinTable = new byte[1 << n][n];
        double[][] minTable = new double[1 << n][n];
        for (int s = 0; s < (1 << n); s++) {
            for (int i = 0; i < n; i++) {
                int sMinusI = s & ~(1 << i);
                if (sMinusI == s) {
                    continue;
                }
                int argMin = -1;
                double min = points[0].distanceTo(points[1 + i]);
                for (int j = 0; j < n; j++) {
                    if ((sMinusI & (1 << j)) == 0) {
                        continue;
                    }
                    double cost =
                        minTable[sMinusI][j] +
                        points[1 + j].distanceTo(points[1 + i]);
                    if (argMin < 0 || cost < min) {
                        argMin = j;
                        min = cost;
                    }
                }
                argMinTable[s][i] = (byte)argMin;
                minTable[s][i] = min;
            }
        }
        int s = (1 << n) - 1;
        int argMin = -1;
        double min = points[0].distanceTo(points[1 + n]);
        for (int i = 0; i < n; i++) {
            double cost =
                minTable[s][i] +
                points[1 + i].distanceTo(points[1 + n]);
            if (argMin < 0 || cost < min) {
                argMin = i;
                min = cost;
            }
        }
        int[] path = new int[1 + n + 1];
        path[1 + n] = 1 + n;
        int k = n;
        while (argMin >= 0) {
            path[k] = 1 + argMin;
            k--;
            int temp = s;
            s &= ~(1 << argMin);
            argMin = argMinTable[temp][argMin];
        }
        path[0] = 0;
        return path;
    }
    public static void main(String[] args) {
        Point[] points = new Point[20];
        for (int i = 0; i < points.length; i++) {
            points[i] = new Point(Math.random(), Math.random());
        }
        int[] path = minLengthPath(points);
        for (int i = 0; i < points.length; i++) {
            System.out.println(points[path[i]]);
            System.err.println(points[i]);
        }
    }
}

欧几里得旅行商问题可以简化为这样，它是np困难的。所以除非你的点集很小或者你有一个非常特殊的结构，你应该寻找一个近似。请注意，维基百科文章提到了针对该问题的PTAS的存在，这在实践中可能会非常有效。

UPDATE:由于您的实例似乎只有几个节点，因此您可以使用简单的指数时间动态规划方法。设f(S, p)是连接集合S中所有点的最小代价，以点p结束。我们有f({start}， start) = 0，我们要寻找f(p, end)，其中p是所有点的集合。为了计算f(S, p)，我们可以检查遍历中p的所有可能的前导，因此我们有

f(S, p) = MIN(q in S ' {p}, f(S ' {p}, q) + distance(p, q))

您可以将S表示为位向量以节省空间(为了最大程度地简化，只需使用单个单词的整数)。还要使用记忆法来避免重新计算子问题的结果。

运行时间将是O(2^n * n^2)，该算法可以用一个相当低的常数因子来实现，所以我预测它能够在秒内解决n = 25的实例一个合理的时间。

这可以用进化算法来解决。看看这个:http://johnnewcombe.net/blog/post/23

你可能想看看TPL(任务并行库)来加速应用程序。

编辑

我发现了这个链接，它有一个旅行推销员算法:http://msdn.microsoft.com/en-us/magazine/gg983491.aspx

源代码据说在:http://archive.msdn.microsoft.com/mag201104BeeColony

相关文章：