多项式时间的精确旅行推销员问题（TSP）解决方案？

Question

在多项式时间内是否有算法来准确解决（时间独立的）TSP问题（没有启发式算法，节点不是空间中的点，成本是任意的）？

谢谢！

Answer 1

不，它被认为是NP-Hard。

如果你找到一个，告诉我（当然在秘密的），我们会共同富裕:-)

我知道维基百科可以经常出错，但你会发现在TSP有趣的页面：

http://en.wikipedia.org/wiki/Travelling_salesman_problem

Answer 2

大概不会。它是NP-hard。

Answer 3

如果NP = P那么答案是肯定的，可以用多项式时间完成。如果NP ≠ P，那么答案是否定的，它不能在多项式时间内完成。 NP = P与NP ≠ P是一个悬而未决的问题，但我怀疑你会发现，那些对这个问题非常熟悉的代表性样本将会有更多的人相信NP = P的人。

Answer 4

不！！，以多项式时间。
是的，有一个确切的算法。