迷茫的旅行商一个无处不在的计算机算法问题 第1章：难题大挑战.pdf

第 1 章 难题大挑战 它产生于三个人求解一道经典数学问题的研究工作。这个 历史悠久的问题叫做“旅行商问题”，无论靠人工计算还是借 助最快的计算机都一直无法解决。 ——IBM 新闻稿，1964 年① 1962 年春天，宝洁公司发起了一场广告宣传活动，在应用数学家中 引起了不小的反响。活动的重头戏是一项竞赛，奖金高达1 万美元，在 当时足以买下一座房子。参赛规则如下： 假设Toody 和Muldoon 打算开车环游美国，地图上用点标 出的33 个地点都要游览，并且要走满足条件的路线中最短的 一条。请你为他们规划一条旅行路线，以伊利诺伊州的芝加哥 市为旅途的起点和终点，依次用线连接各地点，并使得总里程 最短。 ② Toody 和Muldoon 是当时一部美国热门电视剧 中的人物。他们 是驾驶54 号车的两名警官。这项游遍33 座城市的任务是旅行商问题 （traveling salesman problem ，TSP ）的一个具体例子。TSP 的一般形式为： 给定一组城市及它们两两之间的距离，求经过每座城市并返回出发地的 最短路线。 求解一般形式的TSP ，是容易，还是困难，抑或无法求解？对此， 最简单的回答就是谁也不知道。这道计算数学领域的知名难题之所以神 ① 摘自IBM 公司发布于 1964 年 1 月2 日的新闻稿。“它”表示一个新的计算机程 序，能够解决小规模的旅行商问题，由Michael Held 、Richard Karp 和Richard Shareshian 三人编写完成。 ② 即1961 ～1963 年播出的美国电视喜剧Car 54, Where Are You。——译者注 2 迷茫的旅行商：一个无处不在的计算机算法问题 救命啊！我们迷路了！ 支援 54 号车，赢现金大奖 54 名　各奖 1000 美元 1 名　大奖 10 000 美元 图1-1　“54 号车”竞赛题 （宝洁公司供图） 秘莫测而又引人入胜，正是因为这一点。为此陷入困境的也不只是一名 纠结的旅行商而已，因为在计算复杂度的本质与人类认识的可能限度这 一高深论题中，TSP 正是讨论的焦点。若你已跃跃欲试，那么只需要一 支削尖的铅笔和一张干净的草稿纸，就可以向旅行商伸出援手。或许我 们对于整个世界的认识也会因为你而发生飞跃。 1.1　环游美国之旅 TSP 虽然公认棘手，但从某一方面来看却相当容易：经过给定一组 城市的全部可能路线总数是有限的，因此1962 年的某位数学家只需检 验每条可能的路线，将最短的一条记录下来寄给宝洁公司，便可坐等 一万美元支票寄到家中。这个解题策略堪称简单而完美，但有一点潜在 的困难。由于路线总数极其庞大，根本不可能逐一检验。 第 1 章　难题大挑战 3 1930 年，奥地利数学家、经济学家Karl Menger 已注意到TSP 存在 这种困难。最初正是因为他的工作，数学界才开始关注TSP 这道难题。 他写道：“该问题当然可以在有限多次试验内解决，但是尚未发现能够 ① 给出比给定点的全排列数更低的试验次数的解法。” 一条路线可以通过 到达各城市的顺序来唯一确定。我们依次用字母A ～Z 及数字 1 ～7 表示Toody 和Muldoon 的33 个