刚读研就被安排了最难的问题，还解出来了是种什么体验

本文来自微信公众号：大数据文摘（ID：BigDataDigest），来源：quanta，编译：徐玲、coolboy，头图来自：pixabay

试想，当你刚进入研究生院的时候，你的导师向你提出：我们一起来研究理论计算机科学领域最有名的待解决问题吧，你会是什么心情？

但这就是Nathan Klein两年前遇到的事，他的导师邀请他一起解决的问题是旅行商问题，是理论计算机科学家试图解决的基础性问题之一，旨在探索高效计算（efficient computation）的极限。

即使无法解决该问题，他们认为Klein也会在这个过程中学到很多东西。Klein也接受了这个主意，他说：“我当时还不知道害怕，”“我只是一年级的研究生，根本搞不清状况。”

好在，最后Klein也顺利毕业了，也就是说，他们实现了计算机科学家追求了近半个世纪的目标：一种找到旅行商问题近似解的更好方法，在7月份发表的arXiv论文中进行了详细的阐述。

这个优化问题，其目标是寻找走完一组城市的最短路径（或成本最低的路径）。这个问题的解决方案可用于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 年代以来一直在研究旅行商问题。

Williamson说：“这个新结果是向人们证明高效计算的前沿实际上比我们预期的要好的第一步。”

进展

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

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

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

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

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

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

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

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

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

图片来源：Samuel Velasco/Quanta Magazine

这个方法看起来很有希望，不止这三位研究者这么看，其他计算机科学家也这么想。瑞士洛桑联邦理工学院副教授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说解决一般旅行商问题还是“难如登天”。

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

他们发现，这个多项式具有一个他们需要的特性，即“实数稳定性”（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/

本文来自微信公众号：大数据文摘（ID：BigDataDigest），编译：徐玲、coolboy