计算机科学家打破旅行推销员记录
康奈尔大学(Cornell University)的大卫·威廉姆森(David Williamson)自20世纪80年代以来一直在研究旅行推销员问题，他说：“这是我整个职业生涯都想要的结果。”
旅行推销员问题是理论计算机科学家一次又一次地用来测试有效计算极限的少数几个基本问题之一。威廉姆森说，新的结果“是向显示高效计算的前沿实际上比我们想象的更好迈出的第一步”。
虽然可能没有有效的方法总是找到最短的行程，但有可能找到几乎同样好的东西：连接所有城市的最短的树，意思是没有闭合环路的连接(或“边”)网络。Christofides的算法使用这棵树作为往返旅行的主干，添加额外的边将其转换为往返旅行。
任何往返路线都必须有偶数条通往每个城市的边，因为每一次到达之后都会有一次出发。事实证明，反过来也是正确的-如果网络中的每个城市都有偶数个连接，那么网络的边缘必须跟踪往返。
连接所有城市的最短的树缺乏这种均匀性，因为在树枝末端的任何城市都只有一个连接到另一个城市。因此，为了将最短的树变成往返行程，克里斯托菲德斯(去年去世)找到了连接边数为奇数的城市对的最佳方法。然后他证明了由此产生的往返行程永远不会比最好的往返行程长50%。
在这样做的过程中，他设计了可能是理论计算机科学中最著名的近似算法-这通常是教科书和课程中的第一个例子。
“每个人都知道这个简单的算法，”法国格勒诺布尔阿尔卑斯大学和国家科学研究中心的阿兰塔·纽曼(Alantha Newman)说。当你知道的时候，她说，“你知道最先进的技术”--至少在今年7月之前是这样。
长期以来，计算机科学家一直怀疑应该有一种近似算法比克里斯托菲兹的算法性能更好。毕竟，他的简单直观的算法并不总是设计旅行推销员路线的有效方式，因为连接城市的最短树可能不是你可以选择的最佳骨干。例如，如果这棵树有许多分支，分支末端的每个城市都需要与另一个城市相匹配，这可能会形成许多昂贵的新连接。
2010年，佐治亚理工学院的奥维斯·加兰(Oveis Gharan)、萨贝里(Saberi)和莫希特·辛格(Mohit Singh)开始考虑是否有可能改进克里斯托菲兹的算法，不是选择连接所有城市的最短树，而是从精心挑选的集合中随机选择一棵树。他们从旅行推销员问题的另一个版本中获得灵感，在这个问题中，你可以沿着多种路径旅行-也许你通过从芝加哥到丹佛的路线的四分之三加上从洛杉矶到丹佛的四分之一的路线到达丹佛。
与常规的旅行商问题不同，该分数阶问题可以有效地求解。虽然分数路线在物理上没有意义，但计算机科学家长期以来一直认为，最好的分数路线应该是好的普通路线轮廓的粗略指南。
因此，为了创建他们的算法，Oveis Gharan，Saberi和Singh定义了一个随机过程，选择一棵连接所有城市的树，这样给定的边在树中的概率等于该边在最佳分数路线中的分数。有许多这样的随机过程，所以研究人员选择了一种倾向于产生具有许多均匀连接的城市的树木的过程。在这个随机过程产生一棵特定的树后，他们的算法将其插入到Christofides的方案中，以匹配具有奇数条边的城市，将其转换为往返行程。
这种方法似乎很有前途，不仅对这三位研究人员，对其他计算机科学家也是如此。“直觉很简单，”瑞士洛桑联邦理工学院的奥拉·斯文森(Ola Svensson)说。但是“为了证明它是一头不同的野兽。”
然而，第二年，奥韦斯·加兰(Oveis Gharan)、萨贝里(Saberi)和辛格(Singh)成功地证明了他们的算法击败了克里斯托菲兹(Christofides)的算法，解决了“图形化”的旅行推销员问题-在这个问题中，城市之间的距离由一个网络(不一定包括所有连接)表示，其中每条边都有相同的长度。但研究人员无法想出如何将他们的结果推广到一般的旅行推销员问题上，在这个问题中，一些边可能比其他边长得多。
卡林说：“如果我们必须在比赛中增加一个超级昂贵的优势，那么基本上我们就完蛋了。”
然而，Oveis Gharan带着一个不可动摇的信念从那次合作中走出来，他相信他们的算法应该会击败Christofides的算法来解决一般的旅行推销员问题。“我从来没有怀疑过，”他说。
在接下来的几年里，奥韦斯·加兰(Oveis Gharan)一直在思考这个问题。他怀疑，在理论计算机科学界鲜为人知的一门名为多项式几何的数学学科，可能拥有他所需要的工具。因此，当卡林两年前找到他，建议他们共同建议一位名叫内森·克莱恩(Nathan Klein)的聪明的应届研究生，他曾主修数学和大提琴，他说，“好的，让我们试一试--我有一个有趣的问题。”
卡林认为，如果没有其他事情，这将是一个学习更多多项式几何知识的有趣机会。“我真的没有想到我们能够解决这个问题，”她说。
她和Oveis Gharan毫不犹豫地将Klein投入了计算机科学研究的深渊。奥韦斯·加兰(Oveis Gharan)早在2010年还是一名研究生时，就在旅行推销员问题上露出了自己的牙齿。两位顾问一致认为，给研究生布置难题的好处是，特别是在他们头几年没有取得成果的压力的时候。
这三个人投入了一场激烈的合作。克莱因说：“这是我两年来一直在想的事情。”
他们花了第一年的时间解决了这个问题的简化版本，以了解他们面临的挑战。但克莱因说，即使他们做到了这一点，总体情况仍然感觉像是“登月”。
尽管如此，他们还是对他们的工具有了感觉-特别是多项式的几何。多项式是由数字和变量的幂组成的项的组合，例如3x2y+8xz7。为了研究旅行推销员问题，研究人员将城市地图提炼成一个多项式，其中城市之间的每条边都有一个变量，每棵树可以连接所有城市。然后，数字因子对这些项进行加权，以反映旅行推销员问题的分数解中每条边的值。
他们发现，这种多项式有一种令人垂涎的特性，叫做“真实稳定性”，这意味着使多项式计算为零的复数永远不会位于复平面的上半部分。真正稳定的好处是，即使你对你的多项式做了很多改变，它仍然有效。因此，例如，如果研究人员想要关注特定的城市，他们可以用一个变量来表示通向城市的所有不同的边，他们可以将他们不关心的边的变量设置为1。当他们处理这些简化的多项式时，他们的处理结果仍然具有真正的稳定性，为各种各样的技术打开了大门。
这种方法使研究人员能够处理一些问题，比如算法多久会被迫连接两个相距较远的城市。在近80页的分析中，他们成功地证明了该算法在解决一般的旅行推销员问题上优于克里斯托菲兹的算法(这篇论文还没有经过同行评审，但专家们相信它是正确的)。论文完成后，奥韦斯·加兰(Oveis Gharan)匆忙给他以前的博士导师萨贝里(Saberi)发了一封电子邮件。“我想我终于可以毕业了，”他开玩笑说。
