算法：所有点之间的最短路径

Question

15

假设我有10个点，我知道每个点之间的距离。

我需要找到通过所有点的最短路径。

我尝试了几种算法（Dijkstra，Floyd Warshall等），它们都可以给我起点和终点之间的最短路径，但它们没有将所有点都包含在内的路径。

排列组合方法可以正常工作，但计算资源开销太大。

你能向我推荐哪些算法来解决这个问题吗？或者是否有文档记录了如何使用上述算法来解决此问题？

- Jeroen

1

如果只有10个点，那么只有3,628,800种排列方式。这并不是非常昂贵的。你预计会做很多这样的事情吗？ - Jeffrey L Whitledge

10分是一个例子。我们需要编写一个脚本，可以接受任意数量的分数。 - Jeroen

4个回答

6

这显然是旅行商问题。特别对于N=10，你可以尝试使用O(N!)的朴素算法，或者使用动态规划，通过交换空间将其降至O(n^2 2^n)。

此外，由于这是一个NP难题，你只能希望得到近似解或启发式解决方案，需要注意通常的警告。

- Larry

2

正如其他人所提到的，这是TSP的一个实例。我认为目前最先进的解决方案是由乔治亚理工学院开发的Concord。它可以在几秒钟内处理高达10,000个点。它还有一个易于使用的API。

- Eric

1

我认为这可能是你正在寻找的内容：

在计算机科学中，弗洛伊德-沃舍尔算法（有时称为WFI算法[需要澄清]、罗伊-弗洛伊德算法或仅仅是弗洛伊德算法）是一种用于在加权图中查找最短路径（具有正或负边缘权重）的图形分析算法。该算法的单次执行将找到所有顶点对之间最短路径的长度（总和权重），但它不返回路径本身的详细信息。

在“路径重建”子部分中，它解释了您需要存储“路径”的数据结构（实际上，您只需存储要前往的下一个节点，然后根据需要轻松重建任何所需的路径）。

- dsmelser

实际上，OP提到了FW，但很明显这不是他想要询问的内容。 - ziggystar

1

OP可能提到了它，但这并不意味着他知道路径重建，这就是上面的评论所补充的内容。 - Pat Niemeyer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Graviton · Accepted Answer

您可能需要研究一些启发式算法。它们可能无法给出100％精确的结果，但通常可以在合理的时间内得出足够好的解决方案（距离最优解2-3％）。