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

Question

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

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

我尝试了几种算法（Dijkstra，Floyd Warshall，...），它们都为我提供了起点和终点之间的最短路径，但它们并没有制定一条包含所有点的路线。

排列工作正常，但它们太耗费资源。

你能建议我研究什么算法来解决这个问题？或者是否有记录的方法可以使用上述算法来做到这一点？

Answer 1

看看旅行商问题。

您可能想研究一些启发式解决方案。他们可能无法为您提供 100% 准确的结果，但通常他们可以在合理的时间内提出足够好的解决方案（距离最佳解决方案 2% 到 3%）。

Answer 2

这显然是旅行商问题。具体来说N=10，您可以尝试O(N!)朴素算法，或者使用动态规划，您可以通过交易空间将其减少到O(n^2 2^n)。

除此之外，由于这是一个 NP 难题，鉴于通常的警告，您只能希望得到近似值或启发式方法。

Answer 3

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

Answer 4

我认为这就是你正在寻找的，实际上：

弗洛伊德·沃歇尔

在计算机科学中，Floyd-Warshall 算法（有时称为 WFI 算法[需要澄清]、Roy-Floyd 算法或只是 Floyd 算法）是一种图分析算法，用于在加权图中（具有正边权重或负边权重）寻找最短路径）。算法的单次执行将找到所有顶点对之间最短路径的长度（总权重），尽管它不返回路径本身的详细信息

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