第1章 难题大挑战

它产生于三个人求解一道经典数学问题的研究工作。这个历史悠久的问题叫做“旅行商问题”，无论靠人工计算还是借助最快的计算机都一直无法解决。

——IBM新闻稿，1964年¹

_{1. 摘自IBM公司发布于1964年1月2日的新闻稿。“它”表示一个新的计算机程序，能够解决小规模的旅行商问题，由Michael Held、Richard Karp和Richard Shareshian三人编写完成。}

1962年春天，宝洁公司发起了一场广告宣传活动，在应用数学家中引起了不小的反响。活动的重头戏是一项竞赛，奖金高达1万美元，在当时足以买下一座房子。参赛规则如下：

假设Toody和Muldoon打算开车环游美国，地图上用点标出的33个地点都要游览，并且要走满足条件的路线中最短的一条。请你为他们规划一条旅行路线，以伊利诺伊州的芝加哥市为旅途的起点和终点，依次用线连接各地点，并使得总里程最短。

图1-1　“54号车”竞赛题（宝洁公司供图）

Toody和Muldoon是当时一部美国热门电视剧²中的人物。他们是驾驶54号车的两名警官。这项游遍33座城市的任务是旅行商问题（traveling salesman problem，简称TSP）的一个具体例子。TSP的一般形式为：给定一组城市及它们两两之间的距离，求经过每座城市并返回出发地的最短路线。

_{2. 即1961～1963年播出的美国电视喜剧Car 54, Where Are You。——译者注}

求解一般形式的TSP，是容易，还是困难，抑或无法求解？对此，最简单的回答就是谁也不知道。这道计算数学领域的知名难题之所以神秘莫测而又引人入胜，正是因为这一点。为此陷入困境的也不只是一名纠结的旅行商而已，因为在计算复杂度的本质与人类认识的可能限度这一高深论题中，TSP正是讨论的焦点。

若你已跃跃欲试，那么只需要一支削尖的铅笔和一张干净的草稿纸，就可以向旅行商伸出援手。或许我们对于整个世界的认识也会因为你而发生飞跃。