我读了这篇文章，它建议（第 1025 页最后一段）有一个多项式时间算法可以使用二进制搜索找到 k-tsp 问题的最优值。使用二分搜索表明存在一种算法来检查是否存在解决方案，cost<X并且该算法用于二分搜索。我为此“用谷歌搜索”，我能找到的唯一算法是一个非确定性的算法（这很简单），但显然我正在寻找一个确定性的算法。
出于学习目的，我对此感兴趣，
任何帮助/链接将不胜感激。
编辑
我指的是找到最佳解决方案的价值，而不是找到解决方案本身。
问问题
1727 次
2 回答
1
因为 TSP 是 k-TSP 的一个特例，其中 k = 图中的节点数。如果您有一个与图形大小相关的多项式中“最便宜的 k-TSP 路线”的解决方案，那么您将对 TSP 的决策问题版本有一个多项式解决方案，这意味着 P = NP。
所以答案是否定的。用于 k-TSP 的决策问题和优化版本（它们本质上相同）的确定性多项式算法（尚不存在）。
于 2011-12-22T09:41:13.017 回答
0
您提到的论文提出了一种针对有向 k-TSP 问题的多项式时间逼近算法。
近似算法是那些保证产生与最优解值偏差有限的解的算法。有一些针对 NP-Hard 问题的多项式时间逼近算法的示例：Christofides 算法在 O(n³) 时间内产生度量 TSP 问题的解，其值最多为最优解的值的 3/2。
于 2016-09-16T15:45:45.343 回答