algorithm - 找到最小成本路径的有效算法

Question

假设有一组给定的城市...... A、B、C、D、E、F、G。问题是找到覆盖城市 A、B、C、F 的最小成本路径。路径必须覆盖城市 A、B、C、F。该路径可以(但不必)穿过任何其他给定城市(D、E、G)。允许重复路径。路径应从 A 开始和结束。 我应该如何着手解决类似的问题？

Answer 1

这是 Travelling Salesman Problem 的变体(TSP) 变相。

您可以看到，如果您将每个城市都标记为“需要覆盖”(以后我将称之为“有趣”)。 TSP 的变体允许您多次访问一个节点，它仍然是 NP 完全的。

因此，知道您问题的每个精确解决方案的复杂性都会随着有趣城市的数量呈指数增长，您可以按如下方式进行:

首先，预先计算有趣城市之间的最短路径。这可以通过 Dijkstra's algorithm 来完成从每一个有趣的城市或Floyd-Warshall algorithm跑.然后要么尝试访问有趣城市的顺序的每一种排列；要么或者使用一些现有的 TSP 求解器或启发式算法。

所以最简单的实现是这样的:

1. 将 Floyd-Warshall 应用于城市图。它比 Dijkstra 的实现起来简单得多。我找到了一个不错的 PDF与他们的比较。它为您提供了包含 AB、AC、AF、BC、BF 和 CF 的所有最短路径的矩阵。如果您需要按城市顺序获取实际路径，请查看 Path reconstruction section在维基百科中。
2. 尝试访问有趣城市的顺序的所有排列，但 A 除外(即仅 B、C 和 F)。如果你使用 C++、Python 或 Ruby，它们在标准库中都有排列函数。对于其他语言，您可能需要使用第三方库或在 Stack Overflow 中搜索算法。
3. 找到路径总成本最低的排列。例如，对于排列 C-F-B，总成本为 AC+CF+FB+BA。您已经拥有来自 Floyd-Warshall 的所有这些值，因此您可以简单地对它们求和。

如果你总共有 V 个城市和 N 个有趣的城市，这个实现的运行时间大约是 O(V³ + N!·N)