旅行商问题新突破：华盛顿大学研究团队带来细微提升

aizixun8

旅行商问题，又称最短路径问题，是指给定一系列城市以及每对城市之间的距离，求解每个城市访问一次并返回起始城市的最短环路。自1976年Nicos提出简单逼近法以来，几十年来这个问题几乎没有取得任何进展。直到最近，华盛顿大学的一组研究人员才最终证明，十年前提出的一种方法产生了非常小的改进。虽然进步量很小，但在旅行商问题上已经迈出了一大步，也可能是未来进一步进步的突破口。本文讲述了这一突破性近似优化方法背后的故事。

两年前，当克莱因进入华盛顿大学研究生院时，他的导师提出了一个适度的培训计划：共同研究理论计算机科学中最著名的未解决问题之一。

这个想法是，即使他们没有解决这个问题，克莱恩也会一路学到很多东西。克莱恩同意了。 “当时我不知道恐惧，”他说。 “当时我还是一年级新生，无法理解现在的情况。”

现在，在今年 7 月发布的一篇 arXiv 论文中，华盛顿大学博士生 Klein 和他的导师 Anna 和 Oveis 终于实现了计算机科学家半个世纪以来一直追求的目标：找到更好的近似解旅行商问题。方法。

论文地址：

旅行商问题是一个优化问题，其目标是找到穿过一组城市的最短路径（或最低成本路径）。此问题的解决方案可用于许多应用，例如 DNA 测序和共享物流规划。几十年来，这个问题激发了计算机科学的许多基础性进步，有助于展示线性编程等技术的力量。然而，其潜在的可能性尚未得到充分探索，但研究人员为此付出了大量努力。

正如计算复杂性方面的一位领先专家所说：旅行商问题“不是问题，而是上瘾”。

大多数计算机科学家认为，不存在有效解决各种城市组合可能性的最优方案。但在 1976 年，Nicos 提出了一种算法，可以有效地找到近似解——比最优往返时间最多长 50% 的往返行程。当时，计算机科学家期望很快有人能够改进简单的算法并更接近真正的解决方案。但预期的进展并没有到来。

斯坦福大学教授阿明说：“很多人花了无数的时间试图改善这一结果。”

现在，Klein 和 Oveis 已经证明，十年前设计的算法优于算法的 50% 标准，尽管它仅将该百分比降低了一个非常小的数字（10^-36，0.2 a of a of a）。不过，进步就是进步，这一小步就能突破理论僵局和心理门槛。研究人员希望这将为进一步改进提供机会。

华盛顿大学研究生克莱因（左）和他的导师安娜和奥韦斯

“这是我一生工作中一直追求的目标，”自 20 世纪 80 年代以来一直在研究旅行商问题的康奈尔大学教授 David 说。

旅行商问题是理论计算机科学家试图解决的基本问题之一，旨在探索高效计算的极限（ ）。 “这一新结果是表明高效计算前沿实际上比我们想象的更好的第一步，”他说。

进展不大

虽然可能没有一种有效的方法来找到最短的旅程，但可以找到一种方法来找到足够好的路径：连接所有城市的最短树，即一个连接网络（“边”），其中有没有闭环。该算法使用这棵树作为主干进行往返，然后通过添加额外的边将其转换为往返。

任何往返路线必须有偶数条连接每个城市的边，因为每次到达都必须有出发。事实证明，反之亦然 - 如果网络中每个城市的连接数量为偶数，则网络中的边缘必须能够进行往返。

连接所有城市的最短树不具有这种偶数属性，因为路线末端的任何城市与另一个城市只有一个连接。因此，为了将最短的树转换为往返路径，（去年去世）发现最好的方法是将具有奇数边的城市对连接起来。他证明最终的往返行程绝不会比最佳往返行程长 50%。

在此过程中，他设计了也许是理论计算机科学中最著名的近似算法，该算法通常是教科书或课程中提到的第一个示例。

“每个人都知道这个简单的算法，”格勒诺布尔-阿尔卑斯大学和法国国家科学研究中心说。当你学习它时，“这是最好的方法”。这一声明是在七月做出的。仍然成立。

计算机科学家长期以来一直怀疑应该存在一种优于算法的近似算法。毕竟，虽然他的算法简单直观，但在设计旅行商的路线时并不总是有效，因为连接城市的最短树可能不是你可以选择的最佳主干线。例如，如果树有许多分支，则每个分支末端的城市需要与另一个城市匹配，这可能会创建大量成本高昂的新连接。

2010年，佐治亚理工学院的Oveis和Mohit Singh开始思考：也许他们可以通过从精心挑选的集合中随机选取一棵树来改进算法，而不是选择连接所有城市的最短树。他们受到旅行推销员问题的另一个版本的启发，其中旅行推销员可以沿着路径组合旅行，这样为了到达丹佛，他可以走从芝加哥到丹佛的 3/4 路径加上 1/4从洛杉矶到丹佛的路径。

与传统的旅行商问题不同，这个分数问题可以有效地解决。尽管这种细分路线没有实际意义，但计算机科学家长期以来认为，最佳细分路线可以为寻找良好的通用路径提供粗略指导。

因此，为了创建自己的算法，Oveis 和 Mohit Singh 定义了一个随机过程，用于选择一棵连接所有城市的树，并使该树中给定边的概率等于该边在最佳分割路径中的概率分数。这样的随机过程有很多，研究人员倾向于选择能够生成连接城市的多棵偶数树的随机过程。在这个随机过程选择一棵特定的树之后，他们将算法插入到一个方案中，该方案匹配具有奇数边的城市，并将结果转换为往返。

这种方法看起来很有前途，不仅这三位研究人员这么认为，其他计算机科学家也这么认为。瑞士洛桑联邦理工学院副教授奥拉表示：“直观理解很简单，但证明它是一个大问题。”

然而，在接下来的一年里，Oveis 和 Singh 成功证明了他们的算法在“模式”旅行商问题上的表现优于算法。 “模式”旅行商问题将城市之间的距离表示为网络（不一定是所有连接），其中所有边的长度都相同。但他们未能找到一种方法将这一结果扩展到一般的旅行商问题，其中一些边可能比其他边长得多。

说道：“如果在匹配中加入一个成本非常高的边，这个方案基本上就完蛋了。”

进步的过程

尽管如此，在这次合作中，奥维斯带着一个不可动摇的信念离开了：他们的算法在一般旅行商问题上也将优于算法。 “我从来没有怀疑过。”

此后的许多年里，这个问题一直盘旋在奥维斯的脑海中。他怀疑一门叫做“多项式几何”的数学学科可能有他需要的工具，但这是理论计算机科学界很少关注的一个领域。因此，当两年前有人建议他可以指导一位有天赋的研究生克莱因时，他回答说：“当然，我们会尝试一下——我碰巧遇到了一个有趣的问题。”克莱因本科时主修数学和大提琴。主要的。

我当时的想法是，即使没有结果，这也是学习多项式几何的好机会。 “我真的认为我们无法解决这个问题，”她说。

她和奥维斯不失时机地将克莱因带入了计算机科学研究的这一深层次领域。奥维斯本人在 2010 年还是一名研究生时就研究了旅行商问题。两位导师都认为给研究生提出难题是有帮助的，尤其是在前几年，当他们没有压力去产出结果的时候。

三位研究人员开始密切合作。 “这就是我过去两年一直在想的事情，”克莱因说。

在第一年，他们解决了问题的简化版本，以了解他们面临的困难。但即使在解决了简化问题之后，克莱因表示，解决一般旅行商问题仍然是“天价”。

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

他们发现这个多项式有一个他们需要的属性，即“实稳定性（real）”，这意味着使多项式为零的复数永远不会出现在复平面的上半部分。真实稳定性的优点是，即使多项式发生很多变化，它仍然有效。例如，如果研究人员想要关注特定城市，他们可以使用单个变量来表示连接城市的所有不同边，然后将他们不关心的边的变量设置为 1。在对这些边进行操作时多项式的简化版本，其运算结果仍然是实数稳定的，这为各种技术的应用打开了大门。

该方法允许研究人员解决诸如算法被迫连接两个相距较远的城市的频率等问题。在近 80 页的分析中，他们成功地证明了该算法在一般旅行商问题上的表现优于算法。 （该论文尚未经过同行评审，但一些专家对此表示赞赏。）

论文一完成，奥维斯就给他的博士生导师发了一封电子邮件。 “我想我终于毕业了，”他开玩笑说。

斯坦福大学教授阿明（左）和佐治亚理工学院的莫希特·辛格

尽管这项研究取得的进步很小，但计算机科学家希望这一突破能够激发进一步的进步。

回想一下 2011 年，当时 Oveis 和 Singh 解决了模式旅行商问题。不到一年后，其他研究人员提出了非常不同的算法，并大大提高了图形情况下的近似性能。现在在图的情况下，这些算法已将近似率 ( ) 从算法的 50% 降低到 40%。

“当他们公布关于图式旅行商问题的结果时，我们认为这是可能的。我们开始研究它，”后来在该案例上取得进展的研究人员说。他花了数年时间试图在一般的旅行商问题上超越算法。 “现在我知道这是可能的，我会再试一次，”他说。

在过去的几十年里，旅行商问题催生了许多新的方法。奥维斯希望人们现在能够看到多项式几何的价值，事实上他已经成为这种方法的热情传播者。在过去十年或自从他开始学习该方法以来，多项式几何帮助他证明了许多定理。他说，这个工具“塑造了我的整个职业生涯”。

关于旅行商问题的新结果证明了这种方法的威力。说道：“你若仔细研究，一定会受到启发。”

克莱恩现在必须找到新的问题来调查。 “失去这个问题有点悲伤，因为它在我的脑海中构建了很多结构，但现在它们几乎都消失了。”但他对计算机科学研究的贡献却非常令人满意。 “我觉得我们正在将未知的事物推得更远一些。”

原文链接：

爬取UP的主要弹幕和评论进行广告分析。

10月14日，AWS解决方案架构师何六路将带来现场会议，演示如何使用AWS云服务构建从爬取、处理到分析视频内容的简单数据管道。