寻找访问一组断开线路的最小距离
假设我有一组断开连接的道路，就像在这个例子一样。每个路由都有Start和Finish点，可能是相同的(如果路由是循环的)。路由可以是“打开”(不同的开始/完成)或“关闭”(相同的开始/完成)。对于封闭路线，可以将确切的入口/出口点定义为起始点/终点。
还定义了“全局”START和FINISH点。
如何找到访问所有线路所需的最低“成本”(距离或持续时间)，从“全局”开始，从“全局”开始，从开始到完成(或从结束到开始)，以及在“全局”结束时完成旅程？
我熟悉Dijkstra算法，但我不确定它是否可以在这种情况下使用。
每个两点之间的距离和/或持续时间是已知的(可以计算)。我认为每条路线的距离/持续时间并不重要，因为我们需要找出所有“互连”路线的最低“成本”，这些路线需要从一条路线的终点到下一条路线的起点。
每条路线的方向都不重要。每条路线都可以从起点到终点，也可以从终点到终点。
回答 1
Stack Overflow用户
发布于 2014-08-06 13:38:56
如果我正确地解决了这个问题，您将尝试连接一组(开始，完成)对，从全局开始节点开始，到全局结束节点结束，这样，这些对之间的互连距离最小。本地起点和终点(感兴趣的路线)之间的联系已经根据您的描述给出了，因此是不相关的。
正如注释中已经指出的，这个问题是NP难的，因此用多项式时间算法(除非P=NP)是无法解决的。
正如上面的注释所示，如果本地(start、finish)对数量相当小，您可以简单地尝试这些对的所有排列，并按照各自排列的顺序连接，每次都使用dijkstra (或更高级的P2P算法)。不幸的是，正如前面所述，这对你的例子中的13对来说太过分了。
您可以尝试的是，通过考虑(贪婪地)从最后一个终点(可以用dijkstra的一次运行来确定)的下一个X个最近的起点来启发式地减少排列的数量。对于X=2和13对，这将使你降低到2^12 = 4098排列。对于X=3，这将是3^11*2= 354294。当考虑更多的排列时，X越高，解就越好，计算时间越长。
https://stackoverflow.com/questions/24792486
复制相似问题
腾讯云开发者
