算法：所有点之间的最短路径
假设我有 10 分。我知道每个点之间的距离。
我需要找到穿过所有点的最短路线。
我尝试了几种算法（Dijkstra、Floyd Warshall...），它们都给出了起点和终点之间的最短路径，但它们并没有制定一条包含所有点的路线。
排列工作得很好，但它们太耗费资源了。
您可以建议我研究什么算法来解决这个问题？或者是否有记录的方法可以使用上述算法来做到这一点？
Suppose I have 10 points. I know the distance between each point.
I need to find the shortest possible route passing through all points.
I have tried a couple of algorithms (Dijkstra, Floyd Warshall,...) and they all give me the shortest path between start and end, but they don't make a route with all points on it.
Permutations work fine, but they are too resource-expensive.
What algorithms can you advise me to look into for this problem? Or is there a documented way to do this with the above-mentioned algorithms?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
查看旅行推销员问题。
您可能需要研究一些启发式解决方案。他们可能无法为您提供 100% 准确的结果，但通常他们可以在合理的时间内提出足够好的解决方案（距离最佳解决方案有 2% 到 3% 的差距）。
Have a look at travelling salesman problem.
You may want to look into some of the heuristic solutions. They may not be able to give you 100% exact results, but often they can come up with good enough solutions (2 to 3 % away from optimal solutions) in a reasonable amount of time.
这显然是旅行推销员问题。特别是对于
N=10，您可以尝试O(N!)naive 算法，或者使用 动态编程，您可以通过交换空间将其减少到O(n^2 2^n)。除此之外，由于这是一个 NP 难题，考虑到通常的注意事项，您只能希望得到近似值或启发式方法。
This is obviously Travelling Salesman problem. Specifically for
N=10, you can either try theO(N!)naive algorithm, or using Dynamic Programming, you can reduce this toO(n^2 2^n), by trading space.Beyond that, since this is an NP-hard problem, you can only hope for an approximation or heuristic, given the usual caveats.
正如其他人提到的，这是 TSP 的一个实例。我认为佐治亚理工学院开发的 Concord 是当前最先进的求解器。它可以在几秒钟内处理多达 10,000 个点。它还具有易于使用的 API。
As others have mentioned, this is an instance of the TSP. I think Concord, developed at Georgia Tech is the current state-of-the-art solver. It can handle upwards of 10,000 points within a few seconds. It also has an API that's easy to work with.
我认为这实际上是您正在寻找的：
Floyd Warshall
在“路径重建”小节中，它解释了您需要存储“路径”的数据结构（实际上您只需存储要前往的下一个节点，然后简单地重建所需的路径为需要）。
I think this is what you're looking for, actually:
Floyd Warshall
In the "Path reconstruction" subsection it explains the data structure you'll need to store the "paths" (actually you just store the next node to go to and then trivially reconstruct whichever path is required as needed).