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

Shortest path to visit all nodes in a complete directed graph

注意：这几乎是同一个问题：Shortest path to visit all nodes

但是我有一个完整的图

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

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

其他说明：

节点数量少（小于20）。

问题仍然是 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 中的这些边，我们得到哈密顿 Paht。

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

声明

允许重新访问节点不会使问题变得更简单。

说明

假设我们希望在图 G 中找到一个 Hamiltonian path。我们可以通过将 G 中的边的边权重设置为 1，将边的边权重设置为 10 来将其转化为您的问题的一个实例不在 G.

我们现在有一个非负边的完备图H。

当且仅当我们发现 H 中的最短路径长度为 n-1 时，图 G 才具有哈密顿路径。

推荐

因此您修改的问题是 NP-hard，因此您似乎不太可能比简单地采用标准 TSP 技术（例如 Held-Karp algorithm ）来解决它更好。