求访问不相连路线集的最小距离
本文关键字：距离 访问 连路 | 更新日期: 2023-09-27 18:13:25
假设我有一组不相连的道路路线，如本例所示。每条路线都有Start和Finish点，它们可能是相同的(如果路线是圆形的)。路由可以是"开放"(不同的开始/结束)或"封闭"(相同的开始/结束)。对于封闭路线，可以将确切的入口/出口点定义为起点/终点。
还定义了"全局"START和FINISH点。
如何找到访问所有路线所需的最小"成本"(距离或持续时间)，从"全局"起点开始，从起点到终点(或从终点到起点)通过每条路线，并在"全局"终点完成旅程?
我熟悉Dijkstra算法，但我不确定它是否可以在这种情况下使用。
每两个点之间的距离和/或持续时间是已知的(可以计算)。我猜集合中每条路线的距离/持续时间并不重要，因为我们需要找出所有"互连"路线的最小"成本"，从一条路线的终点到下一条路线的起点所需的最小"成本"。
每条路线的方向不重要，即。可以从起点到终点，也可以从终点到起点。
如果我的问题是正确的，您正在尝试连接一组(开始，结束)对，从全局start节点开始并在全局finish节点结束，以便这些对之间的互连具有最小距离。根据你的描述，本地起点和终点(感兴趣的路线)之间的联系已经给出了，因此是不相关的。
正如在评论中已经提到的，这个问题是NP困难的，因此不能用多项式时间算法解决(除非p =NP)。
正如上面的评论所建议的，如果本地(开始，结束)对的数量相当少，您可以简单地尝试这些对的所有排列，并按照各自排列给出的顺序连接这些排列，每次使用dijkstra(或更高级的p2p算法)。不幸的是，如前所述，这对于您示例中的13对来说是多余的。
你可以尝试的是启发式地减少排列的数量，通过(贪婪地)只考虑离最后一个终点最近的下一个X个起点(这可以通过一次dijkstra运行来确定)。对于X=2和13对，这将使你减少到2^12 = 4098种排列。对于X=3，就是3^11*2= 354294。当考虑更多排列时，X越高解决方案越好，缺点是计算时间更长。