algorithm - 无向图中访问顶点集的最短路径

Question

我在室内地图中有一个位置的无向图。当给定一组顶点时，我想找到覆盖所有这些顶点的最短路径。图包含 52 个顶点和 150 - 250 条边。

什么是我可以用来找到最短路径的最佳算法。请不要混淆这是一个旅行商问题。它不必覆盖所有节点。仅覆盖给定的节点集。

Answer 1

正如我所说，这是一个难题，所以不要指望多项式时间算法。

但是如果您正在寻找一种算法，您可以在可接受的时间内针对您提到的问题实例进行计算，那么这可能会奏效:

Let G(V,E) be the original graph, let N be the set of nodes that must be visited.

1. Compute the shortest-path matrix M for the entire graph (|V|x|V| matrix that contains
   the length of the shortest path between each two nodes).
2. Generate a new graph G`, containing N alone, with the distances between each 
   two nodes taken from the shortest-path matrix M.
3. Solve the Minimum Weight Hamiltonian Path Problem on G`.

请注意，这里“最难”的部分是第三部分，它需要指数时间。但是如果组 N 不是太大，你就可以解决它:

• Bruteforce 算法可让您在几秒钟内解决 N 包含大约 11 个节点的问题(O(|N|!) 复杂度)
• 动态编程可让您在几秒钟内解决 N 包含大约 20 个节点的问题(O(2^|N|*|N|^2) 复杂度。

你基本上可以将任何求解最小权重哈密顿路径问题的算法应用到第三部分，这些算法通常等同于TSP算法(这些问题之间的唯一区别是在TSP中你访问后返回源节点所有其他节点)。