在 wiki 中阅读了有关 TSP 的信息后，我发现它说 DP 是 TSP 问题的精确算法，但我很困惑，如果他们有一个问题的精确算法，该问题是否仍应归类为 NPC？任何答案表示赞赏。维基 TSP 页面
问问题
1622 次
1 回答
2
Nitin Gurram 的评论绝对不正确。
NP-Complete 问题可以（并且确实）有精确算法，但是所有这些目前已知的精确算法都在指数时间内执行，最坏的情况。旅行商问题的一个简单但仍然精确的算法是枚举每条可能的旅行商路线，计算每条路线的长度，然后选择最小的。但由于此类路径的数量随着城市数量的增加呈指数增长，因此该算法的执行时间呈指数增长。您指向的维基百科页面说了这么多。
动态规划方法没有天真的方法那么糟糕，它是另一种精确算法，但它仍然在指数时间最坏的情况下运行。
NP-Completeness并不是说没有精确的算法。这意味着没有已知的精确多项式时间算法，以及其他一些技术复杂性理论要求。
（作为旁注，NP-Complete 与 NP 的复杂性类别不同。所有 NP 的意思是，在给定解决方案的情况下，存在多项式时间验证算法。NP-Complete 是该集合的子集，正如我提到的，其他一些技术要求。）
于 2012-12-01T18:46:04.230 回答