查找离开路线集的最小距离

Question

假设我有一组断开的公路路线，如this example。每条路线有Start和Finish个点，这可能是相同的（如果路线是圆形的）。路线可以是“打开”（不同的开始/结束）或“关闭”（相同的开始/结束）。对于封闭路线，可以将确切的进入/退出点定义为开始/结束点。

还定义了“全局”START和FINISH点。

如何从“全局”START开始，通过从开始到完成（或从完成到开始）的每条路线，以及在“全局性”中完成旅程，查找访问所有路线所需的最低“成本”（距离或持续时间） “完成？

我对Dijkstra算法很熟悉，但我不确定它是否可以在这种情况下使用。

每两点之间的距离和/或持续时间是已知的（可以计算）。我猜测集合中每条路线的距离/持续时间并不重要，因为我们需要找出所有“互连”路线的最低“成本”，从一条路线的末端到下一条路线的开始需要走路。

每条路线的方向并不重要，可以从“开始”到“结束”，也可以从“完成”开始到“开始”。

Answer 1

如果我遇到问题，您尝试互连一组（起始，结束）对，从全局开始节点开始到结束于全局结束节点，以使这些对之间的互连具有最小距离。本地起点和终点（感兴趣的路线）之间的联系已根据您的描述给出，因此不相关。

正如在评论中已经指出的那样，这个问题是NP-hard，因此不能通过多项式时间算法解决（除非P = NP）。

正如上面的评论所表明的，如果本地（开始，结束）对的数量相当小，您可以简单地尝试所有这些对的排列，并按照各个排列给定的顺序连接它们，每次使用dijkstra（或更高级的p2p算法）。不幸的是，正如之前所说的，这对你的例子中的13对来说是过度杀伤性的。

你可以尝试的方法是通过考虑（贪婪地）仅考虑从最后一个终点（它可以通过dijkstra的一次运行来确定）的下一个X最近的起始点来启发式地减少排列的数量。对于X = 2和13对，这会使您下降到2^12 = 4098个排列。对于X = 3，这将是3^11 * 2 = 354294.考虑到更多的排列，较高的X越好，解决方案越长，计算时间越长。