旅行商问题详解

给一位推销员一份城市清单,要求他找出把每座城市访问一次并回到家中的最短旅程。任何人都能检验一条给出的路线,任何人也都能凭肉眼改进一条糟糕的路线,但没有人知道一种总能找到最优路线的快速方法。旅行商问题已成为难题的标准范例,而为攻克它而发明的方法如今被用于规划配送、为电路板钻孔和拼接基因组。

一张由闭合路线连接城市的地图,标出了起点城市,下方隐约可见一条更短的路线
一张由闭合路线连接城市的地图,标出了起点城市,下方隐约可见一条更短的路线

问题

一条路线恰好访问每个城市一次,并在出发点结束;它的长度是沿途各段距离之和。任务是找到最短的路线。在这里的版本中,距离是地图上的直线距离,因此从 A 到 C 绝不会比途经 B 更远:这就是度量旅行商问题。数学家卡尔·门格尔(Karl Menger)在 1930 年前后讨论过这个难题,而这个名称在随后几十年间流行开来,当时兰德公司(RAND Corporation)的数学家开始研究它。

卡尔·门格尔,1970年。他约在1930年讨论了旅行推销员问题。
卡尔·门格尔,1970年。他约在1930年讨论了旅行推销员问题。

路线数量的爆炸

固定出发城市。下一个城市有 n − 1 种选择,再下一个有 n − 2 种,依此类推,而每条路线都可以沿两个方向走,所以共有 (n − 1)! / 2 条路线。10 个城市时为 181,440 条,对计算机来说轻而易举。20 个城市时约为 6 × 10¹⁶ 条,70 个城市时则超过可观测宇宙中的原子数。更快的计算机也帮不了多少:每增加一个城市,工作量就大约乘以 n。

NP 困难

1972 年,理查德·卡普(Richard Karp)证明,判断一个图是否有一条经过每个顶点的环游路线(即哈密顿回路)的问题,属于一族同样困难的 NP 完全问题。旅行商问题包含了这个问题,因此是 NP 困难的。若有求解它的快速方法,就能为调度、物流和密码学中成千上万的其他问题带来快速方法。这样的方法是否存在,正是 P 对 NP 问题,它是千禧年大奖难题之一。

一种精确方法:Held–Karp

1962 年,迈克尔·赫尔德(Michael Held)和理查德·卡普,以及独立研究的理查德·贝尔曼(Richard Bellman),使用了动态规划。对每个城市集合 S 以及 S 中的每个城市 j,计算从家乡城市出发、恰好访问 S 中的城市并在 j 结束的最短路径。每个值都可由去掉 j 后的 S 的值求出,因此表格从小集合到大集合依次填写,最后得出最短路线。它需要约 n² · 2ⁿ 步而不是 n! 步,对 30 个城市来说,这就是几分钟与宇宙年龄之间的差别,但它仍呈指数增长。

1962年的理查德·贝尔曼,阿尔弗雷德·艾森施塔特摄。20世纪50年代初他在兰德公司工作时为动态规划命名。
1962年的理查德·贝尔曼,阿尔弗雷德·艾森施塔特摄。20世纪50年代初他在兰德公司工作时为动态规划命名。

快速构造规则

最近邻法总是前往尚未访问的最近城市。它简单快速,但往往会落下几个城市,最后只能绕远路去收集,因此它的路线通常比最优路线长约 25%。插入法则始终保持一个闭合回路,把剩下的城市逐个加到代价最小的位置。1976 年,尼科斯·克里斯托菲德斯(Nicos Christofides)找到一种构造方法,保证在任何度量地图上至多是最优值的 1.5 倍,这个界限四十多年来几乎无人打破。

改进路线:2-opt

局部搜索从任意路线出发,不断做使其变短的小改动。经典的 2-opt 移动去掉两条边,再把两段以另一种方式重新连接,这会使它们之间那段路线反向。只要两条边相交,这个移动就能解开交叉并缩短长度,所以 2-opt 无法再改进的路线绝不会自相交。在随机地图上,2-opt 路线通常比最优值长约 5%。交换三条边的更强移动,或 Lin 和 Kernighan 于 1973 年提出的可变深度方法,还能更接近最优。

模拟退火

局部搜索可能会卡在这样一条路线上:每一个单独的移动都会让它变差,尽管存在好得多的路线。模拟退火由斯科特·柯克帕特里克(Scott Kirkpatrick)、丹尼尔·盖拉特(Daniel Gelatt)和马里奥·韦基(Mario Vecchi)于 1983 年应用于这个问题,它借鉴了冶金学:以取决于温度的概率接受更差的移动,温度起初很高,然后慢慢降低。早期路线可以自由游走;到最后只接受改进。只要冷却足够慢,它就能可靠地找到非常好的路线。

动手探索

打开旅行商演示,随机地、在圆周上、成簇地、在网格上或在你点击的任何地方放置最多 200 个城市。观看最近邻法如何落下最后几个城市,看 2-opt 解开每一处交叉,跟随模拟退火的温度逐渐冷却,并让 Held–Karp 为最多 12 个城市证明最短路线。“全部比较”会在同一张地图上运行每种方法,并显示每条路线比找到的最短路线长多少。

常见问题

旅行商问题用在哪里?

凡是需要按高效顺序访问许多地点的地方都会用到:送货和收货路线、钻头或激光在电路板上移动的路径、望远镜观测恒星的顺序、仓库中的拣货顺序,以及(采用不同的距离)组装 DNA 序列时片段的排列顺序。

精确求解过的最大问题有多大?

1954 年,乔治·丹齐格(George Dantzig)、雷·富尔克森(Ray Fulkerson)和塞尔默·约翰逊(Selmer Johnson)证明了经过美国 49 个城市的最短路线。2006 年,大卫·阿普尔盖特(David Applegate)、罗伯特·比克斯比(Robert Bixby)、瓦谢克·赫瓦塔尔(Vašek Chvátal)和威廉·库克(William Cook)的 Concorde 求解器在耗费多年计算机时间后,证明了来自一个芯片设计的 85,900 个点的最优路线。

最短路线总是没有交叉吗?

是的,在采用直线距离的平面地图上是这样。如果两条边相交,把它们换成它们构成的四边形的两条边就会缩短路线,所以有交叉的路线不可能是最短的。

启发式方法每次都给出同样的路线吗?

这里使用的最近邻、最小代价插入和 2-opt 都是确定性的:对同一组城市,它们给出同样的路线。模拟退火从一条随机路线出发并做随机移动,因此两次运行可能得到不同的路线,不过长度通常几乎相同。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

打开旅行商演示