2

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

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

4

1 回答 1

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不是太大，您将能够解决它：

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

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

于 2013-11-09T15:06:36.273 回答