我正在解决这个问题：
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 完全问题，我最终可能会这样做，但仍然......这让我很烦恼。