我读了这篇文章，它建议（第1025页最后一段）存在一个多项式时间算法使用二分搜索找到 k-tsp 问题的最优解。
使用二分搜索表明存在一种算法来检查是否存在具有 cost 的解决方案，并且该算法用于二分搜索。
我为此“谷歌搜索”，我能找到的唯一算法是非确定性算法（这非常简单），但显然我正在寻找一种确定性算法。
我出于学习目的对此感兴趣，
任何帮助/链接将不胜感激。
编辑
我指的是寻找最佳解决方案的价值，而不是寻找解决方案本身。
I read this article, it suggests (page 1025 last paragraph) that there is a polynomial time algorithm to find the optimum of a k-tsp problem using binary search.
Using binary search would suggest there exists an algorithm for checking if a solution exists with cost<X and this algorithm is used for the binary search.
I 'googled' around for this and the only algorithm i could find was a non deterministic one (which is pretty trivial), but obviously i'm looking for a deterministic one.
I am interested in this for learning purposes,
Any help/links would be appreciated.
EDIT
I am referring to finding the value of the optimal solution and not about finding the solution itself.
发布评论
评论（3）
由于 TSP 是 k-TSP 的特殊情况，其中 k = 图中的节点数。如果您有一个关于图大小的多项式“什么是最便宜的 k-TSP 路线”的解决方案，那么您就会有一个 TSP 决策问题版本的多项式解决方案，这意味着 P = NP。
所以答案是否定的。 k-TSP 的决策问题和优化版本（本质上是相同的）的确定性多项式算法还不存在。
Since TSP is a special case of k-TSP where k = number of nodes in the graph. If you had a solution for "what's the cheapest k-TSP route" in polynomial in relation to graph size, then you'd have a polynomial solution to decision problem version of TSP which would imply that P = NP.
So the answer is no. Deterministic polynomial algorithm for both decision problem and optimization version (they're essentially the same) of k-TSP doesn't exist (yet).
您提到的论文提出了一种针对有向 k-TSP 问题的多项式时间近似算法。
近似算法是那些保证产生与最佳解值偏差有限的解的算法。有一些针对 NP-Hard 问题的多项式时间逼近算法的示例：Christofides 算法 得出，时间 O(n3)，度量 TSP 问题的解，其值最多为最优解值的 3/2。
The paper you mentioned proposes a polynomial-time approximation algorithm for the directed k-TSP problem.
Approximation algorithms are those which are guaranteed to yield solutions with a limited deviation from the optimal solution value. There are examples of polynomial-time approximation algorithms for NP-Hard problems: the Christofides Algorithm yields, in time O(n³), solutions to the metric TSP problem whose values are at most 3/2 the value of the optimal solution.
David Karger 在一次讲座 (链接) 中
提到了一种随机算法高效的 k-TSP 问题，其运行时间为 n 的多项式时间（但 k 为指数）。它基于颜色编码的思想：用 [1..k] 中的随机颜色为每个节点着色，并找到最短的彩色路径（其中每种颜色恰好出现一次）。通过简单的动态规划算法，这种方法的运行时间为 O(n^2 2^k)，并且以概率 e^{-k} 成功（以最小成本找到路径）。通过重复 e^k 次，可以实现一种以高概率找到最小 k-TSP 的算法。
David Karger, in a lecture (link)
mentions a randomized algorithm for efficient k-TSP problem which runs in polynomial time in n (but exponential in k). It is based on the idea of color coding: color each of the node with a random color in [1..k], and find a shortest chromatic path (where each color appears exactly once). With a simple dynamic programming algorithm, this approach gives a runtime of O(n^2 2^k) and it succeeds (in finding the path with minimal cost) with probability e^{-k}. By repeating e^k times, one achieves an algorithm that finds the minimum k-TSP with high probability.