2.4 兰德公司

在20世纪30年代晚期和40年代初期，相关问题的研究记录中并没有出现“旅行商问题”或“TSP”的字眼。但是到了40年代末，这道难题却已声名远扬。此时，求解TSP的作战中心已经从普林斯顿大学转移到了兰德公司，Flood也同样搬到了加利福尼亚州。

2008年12月，普林斯顿大学的Harold Kuhn在一封电子邮件里如此写道：

在1949年的数学系范氏大楼¹里，旅行商问题的名号已经颇为响亮。举个例子，兰德公司当时现金悬赏求解一些问题，它就是其中之一。我记得他们那张列表贴在范氏大楼里的公告板上，那是1948至1949学年的事了。

_{1. 范氏大楼（Fine Hall）是普林斯顿大学数学系所在地，因此也代指该校数学系。该楼得名于首任系主任Henry Burchard Fine，他是经典著作《范氏大代数》（A College Algebra）的作者。——译者注}

兰德公司的奖金悬赏列表！有关TSP的文献资料里经常提到这些奖，但是现在已经很难找到当年那份文件的副本了。Hoffman和Wolfe称，兰德公司设立奖项是“为了TSP的理论研究”。尽管从未有人获得奖金，但是那张奖金列表再加上兰德公司研究小组的极高声望，确实对于宣传推广TSP作出了重要的贡献。

在兰德公司内部员工的口中，还出现了另一个奖项。著名女数学家Julia Robinson评价自己在博弈论方面的研究工作时提到了它：“兰德公司悬赏200美元求解那道题。在我的论文“迭代法求解一个游戏”（An iterative method of solving a game）里，我证明了我的方法确实是收敛的，但是他们也没给我奖金，因为我是兰德公司的内部员工。”²

_{2. Reid (1996).}

Robinson很可能是受到了列表上另一个问题的启发，于是在1949年开始研究TSP。那段时间，她在一份手写笔记里描述了一个通用的数学方法。她对旅行商问题的研究工作与这个通用方法是一致的。“有些问题的叙述相当简单，但是大家完全不知道用什么样的方法可以求出结果，我就更喜欢钻研这样的问题，而不太喜欢只需要推广现有解法的问题。”³当然，TSP正合她的心意，因为在Menger的研讨会之后接近20年的时间里，一直都没有人发表这方面的研究进展。而Robinson后来作出了不少贡献，兰德公司几年后正是在她的基础上取得了突破。我们将在第5章介绍具体内容。

_{3. Reid (1996).}

TSP从何得名

1949年，Robinson在一篇论文里很自然地使用了“旅行商问题”的说法，可见这个概念在当时已经广为人知。事实上，在现有的TSP文献中，她的这篇论文是使用这一说法的最早的一篇，只有兰德公司悬赏列表的副本才能动摇这一历史地位，但是得先有人从故纸堆中翻出那份列表来才行。Robinson将这道题表述为寻找“旅行商以华盛顿为起点和终点、周游各州首府的最短的路线”，与Flood的回忆相吻合，与Dantzig等人使用的数据集也是一致的。

Robinson叙述这个问题的方式把TSP和环游美国48州问题联系在了一起，但是我们依然不知道“旅行商”到底是何时出场的，“旅行商问题”的名字最早是何时开始使用的。Merrill Flood似乎应该知道答案，然而很不幸，他却对此一无所知。他对Albert Tucker解释说：“我不知道是谁把惠特尼的问题称为旅行商问题，是谁创造出这么生动有趣的名字。但是人们显然都很认可这个名字，后来也发现这个问题其实非常基本、非常重要。”无论旅行商问题的名字是如何产生的，到了20世纪50年代中期，这个名字已经得到了广泛使用，只不过“traveling salesman problem”的英文拼写有时存在细微不同，比如写成“travelling”或者“salesman's”之类的¹。同时，这个问题的“恶名”也逐渐远扬。万事俱备，只等Dantzig等人登场。

_{1. 同样，这道题的中文译名也并不唯一。除了本书使用的“旅行商问题”外，常见译名还包括“旅行推销员问题”和颇有趣味的“货郎担问题”。——译者注}