寻找旅行推销员解决方案的最佳成本

Question

我正在解决这个问题：

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设置为voila。而且，您会不会知道，在我书的其他地方也包含有关此问题的提示：

我们如何找到最佳成本？容易：通过二进制搜索。

我想我可能在这里误会了很严重的事情。二进制搜索旨在找到给定项目在排序列表中的位置。那到底如何帮助我找到最佳成本？我真的很困惑。不幸的是，作者没有进一步阐述。

解决这个问题，我唯一想到的另一件事就是证明它们都可以归结为NP-complete的另一个问题，我可能最终会解决，但这仍然使我感到困惑。

Answer 1

假设您有一些下限 l（例如 0）和上限 u（例如所有边权重的总和）。首先，尝试找到总成本 <= (l+u)/2 的解决方案。如果成功，请再次尝试较低的值：(3l+u)/4；如果不是，请尝试更高的值：(l+3u)/4。

我将其称为二分法（维基百科）而不是二分搜索，但想法是相同的。我们想要在某个范围内搜索最佳值，因此我们从中间开始，如果太低则向上移动，如果太高则向下移动。