第12章 超越极限

该问题当然还没有定论。我希望人们能在两方面完成更多的研究工作，一方面要寻找更好的计算方法，另一方面要加深数学上对它的理解。

——Delbert Ray Fulkerson，1956年¹

_{1. 摘自D. R. Fulkerson写于1956年6月25日的信，收信人是法国讷伊（Neuilly）的B. Zimmern。}

从今往后，TSP之美仍将继续吸引数学家和计算机科学家，这一点毫无疑问。

Christos Papadimitriou告诉我，旅行商问题不是一道题，而是一种瘾品。

——Jon Bentley，1991年²

_{2. New York Times, 1991-03-12, G. Kolata.}

它让你上瘾。不管取得了多大的进展，你总会觉得有些尚未落实的预感有可能带来重大突破，这种不安的感觉永远挥之不去。

——Vašek Chvátal，1998年³

_{3 Science Blog, 1998-06-08. http://www.scienceblog.com.}

我们不教你如何戒除TSP瘾。相反，假如有机会设计糖纸，我也会毫不犹豫地在背面印上小规模的TSP难题。当然，糖不属于本书的讨论范围。

本书涉及的许多研究题目依然悬而未决，比如《蒙娜丽莎》难题和世界旅行商问题，4/3猜想，突破Held-Karp运行时间下界，还有改进Christofide近似算法界限。和别人讨论这些题目是件乐事，但你也许需要花很长时间才能取得突破，我无意隐瞒这一事实。只有非常渴望深入探究TSP计算之谜的人，才有可能对它大彻大悟。