最短哈密顿路径是 NP 难的吗？
Is Shortest Hamiltonian path NP-hard?
Hamiltonian Path是一条连接所有节点而不重复的路径，是一个NP完全问题。
最短哈密顿路径 (SHP) 是 NP 难的吗？
旅行商问题和SHP有什么区别？
我假设SHP问题是边加权图上的哈密顿问题。它是 NP 难的，因为它至少和哈密顿问题一样难。假设你有一个算法来解决 SHP 问题，然后你将这个算法应用到一个所有边权重都为 1 的加权图上，它将以相同的时间复杂度解决 Hamiltonian 问题。
TSP需要return到原顶点，每个顶点可以多访问一次。 SHP 要求访问每个顶点恰好一次的路径。
Hamiltonian Path是一条连接所有节点而不重复的路径，是一个NP完全问题。
最短哈密顿路径 (SHP) 是 NP 难的吗？
旅行商问题和SHP有什么区别？
我假设SHP问题是边加权图上的哈密顿问题。它是 NP 难的，因为它至少和哈密顿问题一样难。假设你有一个算法来解决 SHP 问题，然后你将这个算法应用到一个所有边权重都为 1 的加权图上，它将以相同的时间复杂度解决 Hamiltonian 问题。
TSP需要return到原顶点，每个顶点可以多访问一次。 SHP 要求访问每个顶点恰好一次的路径。