完全有向图的TSP

Question

4

在完全有向图上，是否存在一个多项式时间算法来解决旅行商问题？

- Unknown

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wrwrwr · Accepted Answer

不太可能。如果有这个算法，就可以将所有缺失的边设置为非常高的权重，并解决这个问题的标准版本，该问题已知是NP难问题。