“迷茫的旅行商”一场精彩的数学之旅

只布布倩 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年出版。

“迷茫的旅行商”一场精彩的数学之旅

相关推荐

seasongirl / 0评论 2020-06-05