algorithm - 访问完整有向图中所有节点的最短路径

Question

注意:这与以下问题几乎相同:Shortest path to visit all nodes

但是我有一个完整的图表。

问题:考虑一个具有非负边长的完全无向图。问题:计算访问每个节点至少一次的最短路径。

注意: 这不是 TSP 问题。该路径没有结束节点，并且路径可以多次通过节点。

其他说明:

节点数量少(小于20)。

Answer 1

问题仍然是 NP-Complete(对于决策变量)，从 Hamiltonian Path Problem 减少.

给定哈密顿路径问题实例 G=(V,E)，将其简化为您的问题:G'=(V, E', w) 和路径长度|V| - 1。

地点:

E' = VxV
w(u,v) = 1  if (u,v) is in E
w(u,v) = 2  otherwise

• 如果 G 中存在哈密顿路径，则 G' 中存在一条成本为 |V| - 1 的路径。
• 如果 G' 中有一条路径花费 |V| - 1，然后沿着 G 中的这些边，我们得到一个 Hamiltonian Paht。

因此，以上是从哈密顿路径问题到这个 TSP 变体的多项式化简，并且由于哈密顿路径问题是 NP-Hard，所以这个问题也是。