“迷茫的旅行商”一场精彩的数学之旅
只布布倩 2013-09-26
假设一名旅行商打算拜访一张城市列表中的所有城市，每座城市只去一次，最后回到出发地。要怎么走才能让路线最短呢？这就是旅行商问题，乍一听很简 单，在应用数学界却是一道研究极其热烈的难题，时至今日仍无人能解。本书中，William J. Cook将带领读者踏上一场数学之旅，跟随旅行商的脚步，从19世纪初爱尔兰数学家W. R. Hamilton最初定义该问题开始，一路奔向当今最前沿、最顶尖的解题尝试。
它产生于三个人求解一道经典数学问题的研究工作。这个历史悠久的问题叫做“旅行商问题”，无论靠人工计算还是借助最快的计算机都一直无法解决。
1. 摘自IBM公司发布于1964年1月2日的新闻稿。“它”表示一个新的计算机程序，能够解决小规模的旅行商问题，由Michael Held、Richard Karp和Richard Shareshian三人编写完成。
1962年春天，宝洁公司发起了一场广告宣传活动，在应用数学家中引起了不小的反响。活动的重头戏是一项竞赛，奖金高达1万美元，在当时足以买下一座房子。参赛规则如下：
假设Toody和Muldoon打算开车环游美国，地图上用点标出的33个地点都要游览，并且要走满足条件的路线中最短的一条。请你为他们规划一条旅行路线，以伊利诺伊州的芝加哥市为旅途的起点和终点，依次用线连接各地点，并使得总里程最短。
图1-1 “54号车”竞赛题（宝洁公司供图）
Toody和Muldoon是当时一部美国热门电视剧2中的人物。他们是驾驶54号车的两名警官。这项游遍33座城市的任务是旅行商问题（traveling salesman problem，简称TSP）的一个具体例子。TSP的一般形式为：给定一组城市及它们两两之间的距离，求经过每座城市并返回出发地的最短路线。
2. 即1961～1963年播出的美国电视喜剧Car 54, Where Are You。——译者注
求解一般形式的TSP，是容易，还是困难，抑或无法求解？对此，最简单的回答就是谁也不知道。这道计算数学领域的知名难题之所以神秘莫测而又引人入 胜，正是因为这一点。为此陷入困境的也不只是一名纠结的旅行商而已，因为在计算复杂度的本质与人类认识的可能限度这一高深论题中，TSP正是讨论的焦点。
若你已跃跃欲试，那么只需要一支削尖的铅笔和一张干净的草稿纸，就可以向旅行商伸出援手。或许我们对于整个世界的认识也会因为你而发生飞跃。
本书路线一览
图1-11的T恤衫图案出自Jessie Brainerd之手，她曾参加2007年的布达佩斯数学项目。1在应用数学专业或者计算机科学专业，每一名毕业不久的合格本科生都能一眼看出这幅图的主题就是TSP。按照许多大学的课程设置，学习旅行商问题都是必经之路。最近，甚至连美国的中学课本里都有该问题的简单介绍。
图1-11 2007年万圣节的TSP（照片由Jessie Brainerd提供）
1 照片上身着T恤衫的男生是Bill Kay。他是Jessie Brainerd的同学，当时他们在布达佩斯参加万圣节晚会。Jessie Brainerd在博客上写了一篇日志，提到晚会上还有两名学生化装成P和NP，手持飞镖枪玩具互相打斗。
对TSP的介绍既然已经如此普及，我写作本书的目的何在？很简单，我希望能让本书读者对它更加了解，不止步于最简单的认识，而是远远深入问题，接触 最近的理论进展与最先进的解法。我的终极目标是鼓励你们，希望你们也能踏上对旅行商的追踪之路。也许就在某个未知的拐角处，你们将迈出最终一步，迎来彻底 的成功。
本书第2章将从数学和应用两方面追溯旅行商问题的由来，在回顾历史的过程中介绍TSP的基本研究题目，进一步讨论将留到后面各章进行。第3章继续介绍TSP的丰富应用，包括旅行规划、基因组测序、行星搜寻、乐曲编排等方面的内容。
第4章到第7章阐述求解TSP的技术方法，为核心内容。接下来在第8章讨论计算机代码如何解决大规模的TSP题目。
第9章将探讨一般形式的TSP是否存在多项式时间解法。这一理论问题价值百万美金，你若爱钱，这章内容正合你意。然而，即使你钱库空空，亟待现金入 账，我也不建议你跳过前面的章节。因为在计算领域大显身手的方法里，很可能孕育着成功解决理论问题的种子。而你若打算证明不存在通用解法，也必须解释清楚 为何前人的解法能实际应用却不合要求。
数学知识就介绍到这里。第10章将转向心理学和神经学的研究范畴，论述人类如何在不借助计算机的情况下求解TSP。第11章将带领读者欣赏艺术作品 中的TSP路线，比如Julian Lethbridge笔下美妙的抽象画和Robert Bosch设计的简单曲线图案。最后，第12章将再次号召本书读者接受TSP的挑战，并以此结束全书。
补充一点小建议。
如果面前有无数艰难险阻横空而降，爱尔兰作家J. P. Donleavy笔下的人物Rashers Ronald会发誓“不屈不挠，前进到底”。1Applegate等人在研究TSP计算时便将这句话作为战斗口号。我建议深入该问题的读者也能坚持这种态度。本书会介绍许多专家，他们的研究取得了重大进展，但仍然没有从根本上解决TSP。要想扭转局势，搞定旅行商，也许我们需要的恰恰只是一个新的思考角度。
1 Rashers Ronald出现在J. P. Donleavy的作品The Destinies of Darcy Dancer, Gentleman中，该书由Atlantic Monthly Press于1994年出版。
