迷茫的旅行商——1.4　本书路线一览

图1-11 的T 恤衫图案出自Jessie Brainerd 之手，她曾参加2007 年的布达佩斯数学项目。①在应用数学专业或者计算机科学专业，每一名毕业不久的合格本科生都能一眼看出这幅图的主题就是TSP。按照许多大学的课程设置，学习旅行商问题都是必经之路。最近，甚至连美国的中学课本里都有该问题的简单介绍。 图1-11　2007 年万圣节的TSP（照片由Jessie Brainerd提供） ① 照片上身着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 会发誓“不屈不挠，前进到底”。①Applegate 等人在研究TSP 计算时便将这句话作为战斗口号。我建议深入该问题的读者也能坚 持这种态度。本书会介绍许多专家，他们的研究取得了重大进展，但仍然没有从根本上解决TSP。要想扭转局势，搞定旅行商，也许我们需要的恰恰只是一个新的思考角度。 ① Rashers Ronald 出现在J. P. Donleavy 的作品The Destinies of Darcy Dancer, Gentleman中，该书由Atlantic Monthly Press 于1994 年出版。 图1-12　左图：1987 年，W. Cook（本书作者，左一）和V. Chvátal（右一）向作家J. P. Donleavy 赠送夜壶，由Adrian Bondy 拍摄，照片所有权利保留；右 图：1987 年，J. P. Donleavy 写给本书作者的明信片