algorithm - 多项式时间内的精确旅行商问题 (TSP) 解决方案？

Question

是否有一种算法可以在多项式时间内准确地解决（时间无关的）TSP 问题（没有启发式方法，节点不是空间中的点并且成本是任意的）？

谢谢！

score 11 · Accepted Answer

不，它被认为是 NP-Hard。

如果你真的找到了，请告诉我（当然是秘密），我们会一起致富:-)

我知道 Wikipedia 经常出错，但您可能会发现他们在 TSP 上的页面很有趣：

score 4 · Accepted Answer

4

可能不是。它是NP 难的。

于 2011-03-25T14:22:30.023 回答

score 3 · Accepted Answer

如果 NP=P 那么答案是肯定的，它可以在多项式时间内完成。如果NP≠P，那么答案是否定的，它不能在多项式时间内完成。NP=P 与 NP≠P 是一个悬而未决的问题，不过我怀疑你会发现，在足够熟悉该问题的人中，有代表性的样本相信 NP≠P 的人比相信 NP=P 的人要多。

score 2 · Accepted Answer

2

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

于 2012-10-28T12:12:31.317 回答

4 回答 4