假设旅行商打算访问一个城市列表中的所有城市，每个城市只访问一次，最后返回起点。我怎样才能得到最短路线？这就是旅行商问题，乍听之下很简单，但却是应用数学领域研究非常热门的问题，直到现在还没有人能解决。在本书中，威廉·J·库克将带领读者踏上一段数学之旅，追随旅行推销员的脚步，从19世纪初爱尔兰数学家W.R.汉密尔顿首次定义问题，一直到最前沿、最先进*最佳解决问题的尝试。它源于三个人解决经典数学问题的研究工作。这个由来已久的问题被称为“旅行商问题”，它从来没有被人类或最快的计算机解决过。1.摘自IBM公司1964年1月2日的新闻稿。“它”指的是解决小规模旅行推销员问题的新计算机程序，由MichaelHeld、RichardKarp和RichardShareshian编写。1962年春天，宝洁公司发起了一场广告活动，在应用数学家中引起了不小的轰动。比赛的重头戏是一场比赛，奖金高达10,000美元，在当时足够买房了。比赛规则如下：假设Toody和Muldoon打算开车环游美国，他们必须游览地图上用圆点标记的33个地方，并且必须走符合条件的最短路线。请为他们规划一条旅行路线，以伊利诺伊州芝加哥市为旅行的起点和终点，依次用线连接各个点，使总里程最短。图1-1 “54号车”竞赛题（图片由宝洁公司提供）Toody和Muldoon是当时流行的美剧中的人物。他们是驾驶54号车的两名警察。这项穿越33个城市的任务是旅行商问题(TSP)的具体示例。TSP的一般形式是：给定一组城市和它们之间的距离，找出经过每个城市并返回起点的最短路线。2.即1961年至1963年播出的美国电视喜剧《Car54,WhereAreYou》。——译者注求解TSP的一般形式是容易、困难还是不可能？对此的简单回答是没有人知道。这就是计算数学中这个众所周知的问题神秘而迷人的原因。这不仅仅是一个陷入困境的纠结的旅行推销员，因为TSP是关于计算复杂性的本质和人类认知的可能限制的深入辩论的中心。如果您准备好尝试，您只需要一支削尖的铅笔和一张干净的草稿纸即可为旅行推销员助一臂之力。也许我们对整个世界的认识也会因为你而飞跃。图1-11中的T恤图案是由参加2007年布达佩斯数学项目的JessieBrainerd创作的。1应用数学或者计算机专业，每个刚毕业的合格本科生一眼就能看出这张图的题目是TSP。根据许多大学的课程，学习旅行商问题是必经之路。最近连美国的中学课本都有对这个问题的简单介绍。图1-11 2007万圣节TSP（图片由JessieBrainerd提供）1穿T恤的男孩是BillKay。当他们在布达佩斯参加万圣节派对时，他是JessieBrainerd的同学。JessieBrainerd在博客上写了一篇日志，提到派对上有两名伪装成P和NP的学生，拿着玩具飞镖枪互相打斗。既然TSP入门如此火爆，我写这本书的目的是什么？很简单，希望本书的读者能更好地理解它，不要停留在最简单的理解上，而是要深入问题，接触最新的理论进展和最先进的解决方案。我的***目标是鼓励您，希望您也能踏上追踪旅行商的旅程。或许在某个不为人知的角落，你会迈出最后一步，迎来圆满成功。本书第2章将从数学和应用两个方面追溯旅行商问题的起源，并在回顾历史的过程中介绍旅行商问题的基本研究课题，留待后续章节进一步讨论。第三章继续介绍了TSP的丰富应用，包括旅游规划、基因组测序、行星搜索、音乐编曲等。第四章至第七章阐述了解决TSP的技术方法，这是核心内容。第8章随后讨论了计算机代码如何解决大规模TSP问题。第9章检查TSP的一般形式是否存在多项式时间解。这个理论问题价值数百万，如果你爱钱，这一章适合你。然而，即使你的金库空空如也，急需现金，我也不建议你跳过前面的章节。因为在计算领域大显身手的方法中，很可能孕育着成功解决理论问题的种子。并且如果你打算证明没有通用的解决方案，你还必须解释为什么以前的解决方案可以在实践中使用但并不令人满意。数学知识就介绍到这里。第10章转向心理学和神经科学的研究领域，讨论人类如何在没有计算机帮助的情况下解决TSP。第11章带领读者了解艺术作品中的TSP路线，例如JulianLethbridge精彩的抽象画和RobertBosch的简单曲线图案。***，第12章将再次号召本书的读者接受TSP的挑战，并以此结束本书。补充一点建议。爱尔兰作家J.P.唐利维笔下的拉舍尔·罗纳德，如果面前有无数困难和危险，他会发誓“坚持到底”。1Applegate等人在研究TSP计算时将这句话作为战斗口号。我建议深入研究这个问题的读者也保持这种态度。本书将介绍一些研究取得重大进展但仍未从根本上解决TSP问题的专家。也许我们所需要的只是一种新的思维方式来扭转局面并击败旅行商。1RashersRonald出现在J.P.Donleavy的《达西舞者的命运》中，绅士，大西洋月刊出版社，1994图1-12 左图：1987年，W.Cook（本书作者，左一）V.Chvátal（右一）将夜壶赠送给作家J.P.Donleavy，由AdrianBondy拍摄，照片版权所有；右图：1987年，J.P.Donleavy写给本书作者的明信片原文链接：http://www.ituring.com.cn/article/56991
