Closed. This question needs to be more focused。它当前不接受答案。
想改善这个问题吗？更新问题，使其仅关注editing this post的一个问题。
6年前关闭。
Improve this question
这个问题已经以类似的方式被问过几次，但是我发现的现有答案都没有对我有实际帮助。
问题:
我有一个固定的起点，一个固定的终点以及之间的许多终点。
从所需的起点开始，我想计算出沿着所有目的地并在给定目的地处结束的最短路线。
对于我必须解决的特定问题，我需要一个非常快速的解决方案。我当时认为Floyd-Warshall算法适合，据我所知，我的问题与全对最短路径问题有关。
但是，我不知道这些数据将如何随我的数据缩放(在智能手机上可以计算出每条路线数百个中间目的地)。
我也在考虑是否可以将其转化为经典的TSP问题(然后再返回)，因此我可以使用Concorde TSP库，据说它具有出色的性能。
因此:您能为我推荐一个解决问题的最佳方案，以及一些C++代码以帮助我入门吗？
想改善这个问题吗？更新问题，使其仅关注editing this post的一个问题。
6年前关闭。
Improve this question
这个问题已经以类似的方式被问过几次，但是我发现的现有答案都没有对我有实际帮助。
问题:
我有一个固定的起点，一个固定的终点以及之间的许多终点。
从所需的起点开始，我想计算出沿着所有目的地并在给定目的地处结束的最短路线。
对于我必须解决的特定问题，我需要一个非常快速的解决方案。我当时认为Floyd-Warshall算法适合，据我所知，我的问题与全对最短路径问题有关。
但是，我不知道这些数据将如何随我的数据缩放(在智能手机上可以计算出每条路线数百个中间目的地)。
我也在考虑是否可以将其转化为经典的TSP问题(然后再返回)，因此我可以使用Concorde TSP库，据说它具有出色的性能。
因此:您能为我推荐一个解决问题的最佳方案，以及一些C++代码以帮助我入门吗？
最佳答案
您拥有固定的，不同的端点这一事实并没有使问题变得更容易。如果我们可以找到一个多项式时间算法来解决这个问题，我们可以简单地将每个节点设置为端点，解决所有这些问题，找到最佳解决方案(将成本加回到每个节点的起点)，然后针对(经典)TSP问题提供多项式时间算法。
允许您多次访问节点似乎并没有使问题容易得多。为了获得正式证明，需要将TSP降低到这一水平(而不是相反)，在将任意两个节点之间的边缘成本设置为等于这两个节点之间的最短路径时，请考虑一下。完成此操作后，您最终将不得不基本解决TSP问题-该TSP问题的最佳解决方案应该是原始问题的最佳解决方案。
尽管仅使用最短路径有时可能会导致不必要的节点重复，但对于最佳解决方案而言，情况并非如此，因为在通过最短路径隐式访问重复节点之前，始终会降低访问第一重复节点的成本。路径。
要使用TSP求解器解决此问题，请考虑将每两个节点之间的边的权重设置为等于两个节点之间的最短路径，并添加一条从端点到起点的路径，成本为0。
如果使用您使用的求解器无法做到这一点，Wikipedia列出了您可以遵循的几种方法。
性能说明:
是的，我建议运行全对最短路径算法以获取上述最短路径。
请注意，即使是对TSP的(近似)近似算法也要比解决所有对最短路径问题花费更多的时间，因此首先这样做的相对开销应该最小。
如果您认为可以使用全对最短路径解决此问题(但我认为不可能)，那么可以这样做-它将更快。
10-08 14:28