序

“听着，老兄，这片土地上的每一条道路都有我的足迹。”

——Geoff Mack，《我的足迹遍布四方》

在Geoff Mack的歌曲《我的足迹遍布四方》（I've Been Everywhere）中，主人公曾经去过以下城市：里诺、芝加哥、法戈、布法罗、多伦多、温斯洛、萨拉索塔、威奇托、塔尔萨、渥太华、俄克拉荷马、坦帕、巴拿马、马特瓦、拉帕洛马、班戈、巴尔的摩、萨尔瓦多、阿马里洛、托卡皮罗、巴兰基亚、帕迪亚。

1988年2月的一天晚上，我和朋友Vašek Chvátal下定决心追随数学大师的脚步，试着寻找周游多个目的地的最短路线。次日，我们约在曼哈顿下城的一家计算机销售商店碰头，那家店名为Tri-State Camera。店里的技术人员一听说我们是数学家，还想买一台速度快的计算机，便盯着我们的眼睛，告诫道：“你们俩不是想解决那道旅行商问题吧？是不是啊？”他颇有先见之明。在之后的20年里，我们把大部分时光都用在了求解这道题上。期间，有很多台计算机在我们手下逐渐停止运转，就像最初的这一台一样。

这道“臭名昭著”的题是这样的：给定一系列城市，试求出经过所有城市并回到出发地的最短路线。以Geoff Mack歌里唱到的那位旅行者为例，经过那22座城市的路线总共有51 090 942 171 709 440 000条。可以想到，逐一检验所有路线就是一种解题思路。在这样的计算量面前，速度最快的超级计算机也要“挽起袖子”准备辛苦干上一整天。若有足够的耐心，便有希望找到最短路线。然而，假如城市数目变成100座，那么就算征用地球上所有的计算机，也不可能通过逐一检验所有路线找出最短的一条。

最后这句评论针对的是枚举路线的做法，但如果要说旅行商问题确实难解，这理由绝对不足以让人信服。有一些类似的问题其实很容易解决，而它们可供枚举的情形比旅行商的路线还要多。旅行商问题的与众不同之处在于，尽管世界各地的一流应用数学家已经研究了几十年，但人们如今依然不知道，对于一般性的旅行商问题，如何才能得出远远优于简单暴力枚举检验的通用解法。很有可能根本就没有一种高效解法能保证解决该问题的所有具体题目。高效解法是否存在？这是一道严肃的数学问题，涉及可行计算的界限，因此触及复杂性理论的核心。对于想努力求出通用解法的勇士，克雷数学研究所准备了一份大奖——任何人只要能够提出高效解法或者证明不存在高效解法，便会得到100万美元的奖金。

在旅行商问题研究领域，克雷大奖关注的复杂性问题就像圣杯一样。我们也许连解法的影子都看不到，但这并不意味着数学家至今的研究都一无所获。事实上，这道问题带来了许多美妙而深刻的结论和猜想。在精确计算领域，一道包含85 900座城市的难题于2006年宣告破解。该题的最优路线经过计算脱颖而出，若是对数目异常庞大的所有路线逐一检验，需要用顶尖计算机工作站连续运转136年。在实际应用领域，人们使用该问题的解法，每天可以对大量应用题目计算出最优路线或近优路线。

旅行商问题之所以具有永恒的力量，原因之一在于，它是应用数学领域以及运筹学与数学规划方向的驱动力，对新发现起到了有目共睹的带动作用。而且，更多的发现可能就在前方不远处。本书的一大目标就是鼓励有意求解这道难题的读者，希望你们能追随自己的见解和思路。

在写作本书的过程中，我有幸得到了许多人的帮助和支持。首先，我要感谢同事David Applegate、Robert Bixby和Vašek Chvátal。感谢我们在二十多年的岁月里，分享欢乐，共同工作，为揭开旅行商问题的部分奥秘而努力。

我还要感谢Michel Balinsky、Mark Baruch、Robert Bland、Sylvia Boyd、William Cunningham、Michel Goemans、Timothy Gowers、Nick Harvey、Keld Helsgaun、Alan Hoffman、David Johnson、Richard Karp、Mitchel Keller、Anton Kleywegt、Bernhard Korte、Harold Kuhn、Jan Karel Lenstra、George Nemhauser、Gary Parker、William Pulleyblank、Andre Rohe、Lex Schrijver、Bruce Shepherd、Stan Wagon、David Shmoys、Gerhard Woeginger和Phil Wolfe。感谢他们对旅行商问题及其历史的讨论。

书中使用的图片和史料来自Hernan Abeledo、Leonard Adleman、David Applegate、Masashi Aono、Jessie Brainerd、Robert Bixby、Adrian Bondy、Robert Bosch、John Bartholdi、Nicos Christofides、Sharlee Climer、James Dalgety、Todd Eckdahl、Daniel Espinoza、Greg Fasshauer、Lisa Fleischer、Philip Galanter、Brett Gibson、Marcos Goycoolea、Martin Grötschel、Merle Fulkerson Guthrie、Nick Harvey、Keld Helsgaun、Olaf Holland、Thomas Isrealsen、David Johnson、Michael Jünger、Brian Kernighan、Bärbel Klaaßen、Bernhard Korte、Drew Krause、Harold Kuhn、Pamela Walker Laird、Ailsa Land、Julian Lethbridge、Adam Letchford、Panagiotis Miliotis、J. Eric Morales、Randall Munroe、Yuichi Nagata、Denis Naddef、Jaroslav Nešetřil、Manfred Padberg、Elias Pampalk、Rochelle Pluth、Ina Prinz、William Pulleyblank、Gerhard Reinelt、Giovanni Rinaldi、Ron Schreck、Éva Tardos、Mukund Thapa、Michael Trick、Marc Uetz、Yushi Uno、Günter Wallner、Jan Wiener和Uwe Zimmermann。感谢他们所有人的热情帮助。

两所院校为我提供了极好的写作环境，分别是佐治亚理工大学的米尔顿·斯图尔特工业与系统工程学院和普林斯顿大学的运筹学与金融工程系。我对旅行商问题的研究工作得到了美国国家科学基金会（CMMI-0726370）和美国海军研究办公室（N0014-09-1-0048）的资助，也收到了A. Russel Chandler III的慷慨捐赠。感谢他们一直以来的支持。

最后，我要感谢我的家人Monika、Benny和Linda。感谢他们多年来耐心听我讲述旅行商的故事。