complexity-theory - 最短哈密顿路径是 NP 难的吗？

Question

哈密​​顿路径是一条连接所有节点而不重复的路径，它是一个 NP 完全问题。

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

2. 旅行商问题与 SHP 有什么区别？

标签： complexity-theorynpnp-completenp-hard

Answer 1

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

TSP需要返回到原来的顶点，每个顶点可以多访问一次。SHP 要求只访问每个顶点一次的路径。