是否有一种算法可以在多项式时间内准确地解决(时间无关的)TSP 问题(没有启发式算法，节点不是空间中的点，成本是任意的)？
谢谢!
最佳答案
没有。它被认为是 NP-Hard。
如果你真的找到了，告诉我(当然是 secret 的)，我们会一起致富:-)
我知道维基百科经常出错，但您可能会发现他们在 TSP 上的页面很有趣:
关于algorithm - 多项式时间内精确的旅行商问题(TSP)解决方案？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5433694/