最短哈密顿路径 NP 难吗?

Question

Hamiltonian Path是连接所有节点而不重复的路径，它是一个NP完全问题。

1. 最短哈密顿路径 (SHP( NP 难吗？

2. 旅行推销员问题与SHP有什么区别？

Answer 1

我假设SHP问题是边加权图上的哈密顿问题。它是NP难的，因为它至少和哈密顿问题一样难。假设你有一个算法来解决SHP问题，然后你把这个算法应用到一个所有边权重都是1的加权图上，它将以相同的时间复杂度求解哈密顿问题。

TSP需要返回到原始顶点，您可以多次访问每个顶点一次。SHP 询问每个顶点恰好访问一次的路径。