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

Question

注意:这几乎与此问题相同:访问所有节点的最短路径

但我有一个完整的图表.

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

注意:这不是TSP问题.路径没有结束节点,路径可以多次通过节点.

其他说明:

节点数很少(小于20).

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-Hard,所以这个问题也是如此.