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

Question

注意：这个问题与此问题几乎相同：访问所有节点的最短路径 但我有一个完整的图。

问题：考虑一个具有非负边长的完全无向图。问题：计算访问每个节点至少一次的最短路径。 NB：这不是TSP问题。该路径没有结束节点，路径可以多次经过节点。

其他注意事项：

节点数很少（小于20）。

- Ryan J. Shrott

---

你尝试过修改Held-Karp算法来解决这个问题吗？ - Peter de Rivaz

@PeterdeRivaz 算法要求恰好访问每个节点一次。我的问题更加宽松，应该更容易吧？ - Ryan J. Shrott

为什么这个被标记为“D”？ - greenify

Answer 1

问题仍为NP完全问题（对于决策变体），通过从哈密顿路径问题中进行约减。

给定哈密顿路径问题实例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 中沿着这些边行走，我们可以得到一个哈密顿路径。

因此，上述内容是从哈密顿路径问题到该TSP变体的多项式归约，由于哈密顿路径问题是NP难问题，所以该问题也是NP难问题。

- amit

Answer 2

主张

允许节点被重新访问并不会使问题变得更容易。

解释

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

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

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

建议

因此，您修改后的问题是NP难问题，因此似乎您不能比简单地适应标准TSP技术（例如Held-Karp算法）来解决它更好。

- Peter de Rivaz