logo标签列表

通过遍历所有点集中的其他点，找到两点之间的最短路径

c#algorithmgeometrydistance
3
给定由x和y坐标定义的点集合。
在这个集合中，我获取起点、终点以及其他n-2个点。
我必须通过穿过所有其他点来找到起点和终点之间的最短路径。最短路径由其值和(如果可能)交叉点顺序定义。
乍一看，这似乎是一个图形问题，但我现在并不确定，无论如何，我正在尝试仅使用几何关系来找到这条最短路径，因为目前我所拥有的所有信息都只是点的x和y坐标，以及哪个点是起点，哪个点是终点。
我的问题是，是否可以仅使用几何关系找到这条路径？
我正在尝试在C#中实现这一点，如果有可用的有用软件包，请告诉我。
1
“交叉点次序”是什么意思？这只是旅行商问题吗？ - Kevin
“交叉点顺序”是指将点添加到最小路径的顺序。例如，这些点可以保存在一个集合中，前两个点定义了第一对点之间的最短路径，然后从集合中选择第三个点来定义第二对点之间的最短路径，以此类推。 - Clock
是的，允许多次访问一个点。 - Clock
有多少个点？使用近似解可以吗？您愿意使用其他人的软件吗？ - David Eisenstat
不知道是我没有完全理解问题还是标题与问题几乎毫无关系。你是想要一条单线，尽可能地（根据某种定义）经过所有点，还是一条折线形式的游览路线？ - Niklas B.
显示剩余8条评论
4个回答
4

欧几里得旅行商问题可以简化为这个问题，而且它是NP难的。因此，除非你的点集很小或者有一个非常特殊的结构，否则你应该寻找一种逼近方法。请注意，维基百科文章提到了该问题存在 PTAS，在实践中可能非常有效。

更新: 由于您的实例似乎只有几个节点，您可以使用简单的指数时间动态规划方法。让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的实例。
所以最终，这必须是一个图形问题，我应该停止试图用更简单的几何方法解决它吗？ - Clock
@MirceaLucian 嗯，这不是一个图问题。从某种意义上说，欧几里得TSP比一般图中的TSP问题要“容易”，这可以通过存在利用几何属性和图相关概念的PTAS来证明。简单的2倍近似使用最小生成树和三角不等式。两者都需要一些调整，因为您不需要旅游回到起点。 - Niklas B.
我假设你指的是Arora的PTAS。与某些PTAS不同的是，它没有隐藏的星际常数，但局部搜索方法（2-opt、3-opt、k-opt、Keld Helsgaun的优秀LKH）在实践中更简单且效果非常好，而分支定界方法（通常基于Held-Karp LP）可以在惊人的大欧几里得平面实例上给出精确答案。进化算法可能不值得考虑。 - David Eisenstat
@DavidEisenstat，你显然对可用的近似方案有更好的概述，所以请随意撰写答案或通过编辑来改进我的答案。我无法对在这里实际运作的哪种方法效果良好做出任何判断。 - Niklas B.
抱歉，当必然会提出遗传算法建议时，我会有点暴躁。 - David Eisenstat
4
最简单的启发式算法是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 Helsgaun的LKH。
另一类算法是分支定界算法，它们返回最优解。Concorde（据我所知）是目前的最新技术。

这里是尼克拉斯所描述的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]);
        }
    }
}
谢谢你提供的算法建议，我很快就会开始实现它并看看它的表现！之前，我只是计算每个点到所有其他点的最短距离，然后将该距离添加到最终结果中。但是，这样做最终并不能给出连接所有点的最短路径。 - Clock
抱歉，我心中的算法也是O(2^n * n^2)，所以即使没有进行重度微优化，也不一定能在几秒钟内完成。 - Niklas B.
0
谢谢您的建议，我只是想寻找一种更简单的实现方式。使用这样的算法似乎需要更长的开发时间，而采用启发式解决方案之类的方法则显得更简单。在某种程度上，我可以在性能方面做出牺牲，以保持实现的简单性。 - Clock
0
1
首先，我需要正确的算法，然后这些加速的事情就会出现了 :)。 - Clock
我在数学方面不是很强，但如果你只有一个随机的点集而不是从方程生成的话，那么我认为你需要一个好的参考来帮助你找到最佳解决方案。在大学里我们学过这个，我用的书是《算法与数据结构：尼克劳斯·维尔特》。如果我没记错的话，这本书中的算法是用Pascal编写的，很容易转换成C#。 - Barry West
这些点是随机生成的，一开始我只是试图找到一个“几何”解决方案，以保持事情简单。对我来说，完全由我编写的代码更容易维护和理解。不知何故，我认为这会加快开发时间，但是...如果将现有算法转换将是最后的解决方案，我将不得不这样做。感谢您提供的算法建议！ - Clock
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接