完整有向图的 TSP

Question

完全有向图上的旅行商问题是否存在多项式时间算法？

Answer 1

不太可能。如果有的话，您可以采用任何图形并添加所有具有非常高权重的缺失边。这将允许解决问题的标准版本，已知该问题是 NP 难的。