小量变引起大质变，多项式几何助力旅行商问题研究取得突破性进展

选自quantamagazine

旅行商问题也称最短路径问题，是指给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。自 1976 年 Nicos Christofides 提出了一种简单的近似方法之后，这一问题在几十年的时间里鲜有进展。直到最近，华盛顿大学的一个研究团队才最终证明十年前提出的一种方法能带来非常细微的提升。进展的量虽小，但却是在旅行商问题上迈出的一大步，也许更是未来进一步进展的突破口。本文将介绍这种突破性近似优化方法背后的故事。

两年前，当 Nathan Klein 刚进入华盛顿大学研究生院时，他的导师提出了一个谦逊的培养计划：一起研究理论计算机科学领域一个最有名的待解决问题。

他们当时的想法是，就算最终没能解决它，Klein 也能在过程中学到很多。Klein 同意了这一想法。「我当时还不知道害怕，」他说，「我那时还是个一年级新生，根本搞不清状况。」

而现在，在今年 7 月发布的一篇 arXiv 论文中，华盛顿大学在读博士 Nathan Klein 及其导师 Anna Karlin 和 Shayan Oveis Gharan 终于实现了一个令计算机科学家追逐了半个世纪的目标：寻找旅行商问题近似解的更优方法。

论文地址：

https://arxiv.org/abs/2007.01409

旅行商问题是一个优化问题，其目标是寻找走完一组城市的最短路径（或成本最低的路径）。这个问题的解决方案可用于 DNA 测序和共享物流规划等许多应用。几十年来，这一问题激发了计算机科学领域多项根本性的进步，帮助展现了线性规划等技术的力量。不过，其潜在的可能性还未得到完全探索，不过研究者为此付出的努力并不少。

正如计算复杂性领域著名专家 Christos Papadimitriou 说的那样： 旅行商问题「不是一个问题，而是一个会让人上瘾的东西」 。

大多数计算机科学家认为：并不存在一种有效解决各种城市组合可能性的最优解。但在 1976 年，Nicos Christofides 提出了一种能有效找到近似解的算法——往返旅程最多比最佳往返旅程长 50%。那时，计算机科学家预计很快就有人能在 Christofides 的简单算法上实现提升，进一步接近真实解。但预期的进展并未到来。

斯坦福大学教授 Amin Saberi 表示：「很多人花了无数时间试图提升这一结果。」

现在，Karlin、Klein 和 Oveis Gharan 已经证明：十年前设计的一种算法优于 Christofides 算法的 50% 标准，虽然它也只是将这个百分数减少了非常小的数字（10^-36，0.2 billionth of a trillionth of a trillionth of a percent）。尽管如此，进步终究是进步， 这一微小进步能够突破理论上的僵局以及心理上的门槛 。研究者希望这能带来契机，实现进一步的改进。

华盛顿大学研究生 Nathan Klein（左）及其导师 Anna Karlin 和 Shayan Oveis Gharan

康奈尔大学教授 David Williamson 表示：「这是我一生事业所追求的目标。」他自 1980 年代以来一直在研究旅行商问题。

旅行商问题是理论计算机科学家试图解决的基础性问题之一，旨在探索高效计算（efficient computation）的极限。Williamson 说：「这个新结果是向人们展示高效计算的发展前沿事实上比我们预想的更好的第一步。」

微末的进展

尽管可能并不存在找到最短旅程的有效方法，但却有可能找到足够好路径的方法：连接所有城市的最短树（tree），也就是一个由连接（「边」）构成的网络，其中没有封闭回路。Christofides 的算法使用了这个树作为骨干部分来进行往返旅行，然后通过添加额外的边来将其转换成往返旅程。

任何往返旅程路线连接每个城市的边的数量都必然为偶数，因为每一次到达之后都必然有一次离开。事实证明反过来也是如此——如果网络中每座城市的连接数为偶数，则网络中的边必然能实现往返旅程。

而连接所有城市的最短树则不具备这种偶数性质，因为任何在路线末端的城市与另一个城市仅有一个连接。因此为了将最短树转换到往返旅程中，Christofides（已于去年逝世）发现最佳方法是连接有奇数条边的城市对。他证明，所得到的往返旅程永远不会比最佳往返旅程长 50%。

在此过程中，他设计出了也许是理论计算机科学领域最有名的近似算法——这个算法通常是教科书或课程中提到的第一个例子。

法国格勒诺布尔 - 阿尔卑斯大学与法国国家科学研究中心的 Alantha Newman 称：「这个简单算法人人皆知。」而且当你学习它的时候，「它就是当前最佳方法。」这个说法直到 7 月份时还依然成立。

长时间以来，计算机科学家猜想应该存在优于 Christofides 算法的近似算法。毕竟他的算法虽然简单直观，但并不总能有效设计出旅行商行进路线，因为连接城市的最短树可能并非你可选择的最佳骨干。举例来说，如果这个树有很多分支，那么每个分支末端的城市都需要与另一个城市匹配，这就有可能形成大量成本高昂的新连接。

2010 年，佐治亚理工学院的 Oveis Gharan、Saberi 和 Mohit Singh 开始思考：也许可以不选择连接所有城市的最短树，而从一个精心选取的集合中取一个随机树来改进 Christofides 算法。他们的灵感来自旅行商问题的一个替代版本，该问题中旅行商可沿路径组合行进，比如为了到达丹佛，可以选取从芝加哥到丹佛的 3/4 路径加上洛杉矶到丹佛的 1/4 路径。

不同于常规的旅行商问题，这个分数化的问题可以得到有效解决。尽管这种分数化路径（fractional route）并不具有实际意义，但计算机科学家长时间以来认为，最佳的分数化路径能为寻找优良的常规路径提供粗略的指引。

因此，为了创建自己的算法，Oveis Gharan、Saberi 和 Mohit Singh 定义了一种用于选取连接所有城市的树的随机过程，并令给定边在该树中的概率等于该边在最佳分数化路径中的分数。这样的随机过程有很多，研究者倾向于选择能生成多个偶数连接城市的树的随机过程。在这个随机过程选出一个特定的树之后，再将他们的算法接入到 Christofides 的方案，匹配有奇数条边的城市，并将结果转化为一个往返旅程。

这个方法看起来很有希望，而且不止这三位研究者这么看，其他计算机科学家也这么想。瑞士洛桑联邦理工学院副教授 Ola Svensson 表示：「其中的直观理解很简单，但证明它却又是一大难题。」

不过，在第二年里，Oveis Gharan、Saberi 和 Singh 成功证明他们的算法在「图式」旅行商问题中优于 Christofides 算法。「图式」旅行商问题将城市之间的距离表示为网络（不必包含所有连接），其中所有边的长度全都一样。但他们没能找到将这一结果扩展到一般旅行商问题的方法，一般旅行商问题中一些边可能比另一些边长很多。

Karlin 表示：「如果在匹配中加入一条成本很高的边，这个方案基本就完蛋了。」

进展的历程

尽管如此，在这场合作中，Oveis Gharan 有了一个不可动摇的信念：他们的算法在一般旅行商问题上同样胜过 Christofides 算法。「我从未怀疑过。」

接下来的很多年里，这个问题一直在 Oveis Gharan 的脑中盘旋。他猜想，一个名为「多项式几何」的数学学科中可能有他需要的工具，但这是理论计算机科学社区不太关注的领域。因此，当 Karlin 两年前建议他一起指导天才研究生新生 Nathan Klein 时，他回答说：「没问题，我们就试试看——我正好有个有趣的问题。」Nathan Klein 在本科阶段主修了数学和大提琴两个专业。

Karlin 当时想的是，就算没有成果，这也是一个学习多项式几何的好机会。她说：「我当时确实认为我们没法解决这个问题。」

她和 Oveis Gharan 毫不犹豫地将 Klein 带入到了计算机科学研究的这一深层领域。Oveis Gharan 本人在 2010 年研究生阶段时就研究旅行商问题。这两位导师都认为给研究生布置难题大有裨益，尤其是前几年他们还没有出成果的压力时。

这三位研究者开始了密切合作。Klein 说：「我这两年里思考的都是它。」

在第一年里，他们解决了该问题的一个简化版本，以便感受他们所面临的难度。但即便在解决了简化问题之后，Klein 说解决一般旅行商问题还是「难如登天」。

尽管如此，他们已经很好地理解了所用的工具，尤其是多项式几何。多项式是带有幂的变量的组合表达式，比如 3x²y+8xz⁷。为了研究旅行商问题，他们将城市构成的地图提炼成了多项式，其中每个变量表示城市之间的一条边，而每一项表示可以连接所有城市的每个树。然后使用数值因子对这些项进行加权，以反映各条边在旅行商问题的分数解中的值。

他们发现，这个多项式具有一个他们需要的特性，即「实数稳定性（real stability）」，也就是说能让该多项式为零的复数永远不会出现在复平面的上半部分。实数稳定性的优势在于即便对多项式进行许多更改，它仍旧有效。举个例子，如果研究者想要关注特定的一些城市，他们可以使用单个变量表示连接一个城市的所有不同边，然后将不关心的边的变量设为 1。在操作这些简化版多项式时，他们的操作结果仍具有实数稳定性，这为各种技术的应用开启了大门。

该方法让研究者可以处理很多问题，比如算法被迫连接两个相距较远的城市的频率是多少。在近 80 页的分析中，他们成功证明该算法在一般旅行商问题上优于 Christofides 算法（该论文还未经过同行评议，但一些专家给予了肯定。）

论文刚完成，Oveis Gharan 就给他的博士导师 Saberi 发了封电子邮件。他开玩笑道：「我想我终于毕业了。」

斯坦福大学教授 Amin Saberi（左）和佐治亚理工学院的 Mohit Singh

尽管该研究实现的提升微乎其微，但计算机科学家希望这一突破能启发进一步的进展。

回想 2011 年，那时候 Oveis Gharan、Saberi 和 Singh 解决了图式旅行商问题。之后不到一年时间，其他研究者就提出了非常不同的算法，并极大提升了在图式案例上的近似性能。现在在图式案例上，这些算法已经将近似率（approximation factor）从 Christofides 算法的 50% 下降到了 40%。

「当他们宣布有关图式旅行商问题的结果时，我们觉得这是有可能的。我们也开始研究它。」后来在这一案例上取得进展的研究者 Svensson 说。他之前多年一直尝试在一般旅行商问题上超过 Christofides 算法。他说：「现在我知道这是可能的，我会再次尝试。」

过去几十年来，旅行商问题已经催生了很多新方法。Oveis Gharan 希望现在人们能看到多项式几何的价值，而且事实上他已经成为这一方法的热情布道者。在最近十年中或自他开始学习这一方法以来，多项式几何已经帮助他证明了很多定理。他表示：这一工具「塑造了我的整个职业生涯」。

这一旅行商问题的新结果证明了该方法的强大。Newman 称：「仔细研究的话肯定能大受启发。」

Klein 现在则必须找一个新问题来研究了。「失去这个问题是有点悲伤，因为它在我的头脑中构建了许多结构，但现在它们差不多都消失了。」但他对计算机科学研究的贡献已经很令人满意了。「我感觉我们把未知之物又推进了一点。」

https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/