寻找旅行推销员解决方案的最佳成本
我正在研究这个问题：
TSP:
Input: A matrix of distances; a budget b
Output: A tour which passes through all the cities and has length <= b,
if such a tour exists.
TSP-OPT
Input: A matrix of distances
Output: The shortest tour which passes through all the cities.
表明如果 TSP 可以在多项式时间内解决，那么 TSP-OPT 也可以。
现在，我首先想到的是，如果我知道最佳解决方案的成本，我可以将 b 设置为该值，然后瞧。而且，你难道不知道吗，在我的其他地方书中包含了针对这个问题的提示：
我们如何找到最佳成本？简单：通过二分查找。
我想我可能在这里误解了一些非常严重的事情。二分查找的目的是查找给定项目在排序列表中的位置。这究竟如何帮助我找到最佳成本？我真的很困惑。不幸的是，作者没有进一步详细说明。
我可能想到解决这个问题的唯一另一件事是证明它们都简化为另一个 NP 完全问题，我可能最终会这样做，但仍然......这让我烦恼。
I'm working on this problem:
TSP:
Input: A matrix of distances; a budget b
Output: A tour which passes through all the cities and has length <= b,
if such a tour exists.
TSP-OPT
Input: A matrix of distances
Output: The shortest tour which passes through all the cities.
Show that if TSP can be solved in polynomial time, then so can TSP-OPT.
Now, the first thing that jumps to mind is that if I knew the cost of the optimal solution, I could just set b to that and voila. And, wouldn't you know it, elsewhere in my book it contains a hint for this very problem:
How do we find the optimum cost? Easy: by binary search.
I think I might be misunderstanding something very badly here. Binary search is meant to find the position of a given item in a sorted list. How exactly could that help me find the optimal cost? I'm genuinely confused. The authors don't elaborate any further, unfortunately.
The only other thing I might think of to solve this problem is to prove that they both reduce to another problem that is NP-complete, which I may end up doing, but still... this bugs me.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
假设您有一些下限 l（例如 0）和上限 u（例如所有边权重的总和）。首先，尝试找到总成本 <= (l+u)/2 的解决方案。如果成功，请再次尝试较低的值：(3l+u)/4；如果不是，请尝试更高的值：(l+3u)/4。
我将其称为二分法 (Wikipedia) 而不是二分搜索，但想法是相同的。我们想要在某个范围内搜索最佳值，因此我们从中间开始，如果太低则向上移动，如果太高则向下移动。
Assume that you have some lower bound l (e.g. 0) and upper bound u (e.g. the sum of all the edge weights). First, attempt to find a solution of total cost <= (l+u)/2. If you succeed, try again for a lower value: (3l+u)/4; if not, try for a higher value: (l+3u)/4.
I would call this a bisection method (Wikipedia) rather than binary search, but the idea is the same. We want to search some range for the optimal value, so we start in the middle and move up if we're too low and down if we're too high.