寻找旅行推销员问题最优解的成本

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设置为该成本，就可以轻松解决问题。而且，在书中的其他地方，它还提供了解决这个问题的提示：“我们如何找到最优成本？很容易：通过二分查找。”我可能非常错误地理解了某些内容。二分查找是用来找到已排序列表中给定项目的位置的。但是，它怎么能帮助我找到最优成本呢？我真的很困惑。不幸的是，作者没有进一步阐述。我唯一想到的另一种解决方法是证明它们都归约为另一个NP完全问题，我可能最终会这样做，但是...这让我感到困扰。

- 2-bits

---

如果您告诉我们教科书的名称，可能会有所帮助。 - Paul Johnson

有趣的是，http://cseweb.ucsd.edu/classes/wi08/cse101/hw/hw7soln.pdf提供了相当清晰的解释，（还涵盖了为什么二分查找不能产生伪多项式时间算法的原因）。 - lijie

@j_random_hacker：我认为“最小边的分辨率”这个术语实际上是“边权重表示的分辨率”（否则，用logK位表示K的观点就没有意义）。如果权重是实数，则二进制搜索可能不起作用，除非TSP实际上搜索长度<(严格)b的旅行团。 - lijie

即使是浮点数也有最小（非零）分辨率（对应于最小的非规格化数），并且在某些最小分辨率下，该论点仍然成立（步骤数量只增加一个常数因子 - 基本上是取对数到不同的基数），因此它仍然是一种可接受的方法。请注意，该论点并不假设特定的最大边缘权重（它只假设有一个 有限 的最大边缘权重）。 - lijie

啊！这很有道理。因此，使用浮点表示导致长度为n的最大可表示数字的形式为k^(k^n)，而不是k^n。好的，同意。我之前发表的第三条评论是错误的。如果我们还必须使用相同的表示来表示总和，那么手动挥舞地感觉，将表示空间均匀分割的二分搜索变体仍然可以工作。 - lijie

Answer 1

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

我会称这为二分法(维基百科)而不是二分搜索，但想法是相同的。我们想要在某个范围内搜索最佳值，所以我们从中间开始，并向上移动如果太低并向下移动如果太高。

- bnaul

---

+1 但我还没有被二分法的停止准则所说服。正如我在对李杰的评论中所说，他链接的PDF中提出的论点并没有表明当差异小于图中最小边长时停止是足够的。 （实际上，这可能是正确性的充分条件，但该论点并未证明它。） - j_random_hacker