江苏龙网

  1. 首页 > 人文 > >

|44年，10?3?的关键突破


|44年，10?3?的关键突破
本文插图

你是一位辛苦而忙碌的推销员 ， 需要穿梭在许多城市之间 。 假设现在你有一系列目的地城市需要逐一拜访 ， 并最终返回你生活的那座起点城市 。 你已经做了充足的准备 ， 知道任意两座城市之间的距离 ， 那么 ， 应当如何规划旅行路径 ， 才能使得整个旅程最短呢？
虽然描述和理解起来并不复杂 ， 但这绝不能算是一个简单的问题 ， 尤其是当“城市”的数量远不止三五座 ， 而是一个庞大的数字时 ， 问题的复杂程度也可能变得超乎想象 。
这个问题有个专属的名字 ， 它通常被称为旅行推销员问题（travelling salesman problem, TSP） ， 是理论计算机科学中一个最著名的存在已久的基本问题之一 。 理论计算机科学家为了检验有效计算的极限 ， 对这一问题进行了反复研究 。 几十年来 ， 它也激发了计算机科学中许多基础的进步 ， 帮助阐释了 线性规划等技术的能力 。 一些科学家甚至把探索TSP称为一种“瘾” 。
TSP也并非单纯的“纸上谈兵” ， 而是具有广泛的实际意义 ， 在物流、制造业 ， 甚至DNA测序中都有应用 。 在这些情况下 ， “城市”就代表着客户、DNA片段等 ， 而“城市间的距离”则可以指时间、距离、相似度等 。
两年前 ， 当Nathan Klein开始研究生学习时 ， 他的导师Anna Karlin与Shayan Oveis Gharan提出了这样一个规划——共同研究理论计算机科学中这个著名问题 。 Klein的导师都认为 ， 即使他们无法解决这个问题 ， Klein也能在这个过程中学到很多东西 。 当时仍是研究生新生的Klein同意了这个计划 ， 他还不知道自己在接下来两年将会面临什么 。
如今 ， 在上传至预印本网站的一篇论文中 ， 导师与Klein终于实现了他们的目标 ， 事实上 ， 这也是计算机科学家近半个世纪以来一直所追求的——他们 证明了找出TSP近似解的更优算法 。
大多数计算机科学家相信 ， 没有一种算法可以有效地为TSP所有可能的城市组合找到最优解 。 虽然如此 ， 找到接近最优解的方法还是有可能的 。
1976年 ， 尼科斯·克里斯托菲德斯（Nicos Christofides）提出了一种算法 ， 可以有效地找到TSP的近似解 ， 并保证这种近似解中的往返旅程最多比最优解长出50%（近似比不超过3/2） 。这种算法利用了连接所有城市的最短“树” ， 也就是没有闭合回路的连接（或者叫“边”）网络 ， 然后将这种树作为主干 ， 随后添加额外的连接 ， 将它转换成完整的往返路径 。
|44年，10?3?的关键突破
本文插图

这是一个简单的TSP例子 ， 在这个例子中 ， 最优解并不复杂 。 而克里斯托菲德斯算法会先找到连接所有城市的最短树 ， 然后再将它转换成完整的往返旅程 。 | 图片设计：雯雯子；素材参考：[1]
在任何往返旅程中 ， 连接每座城市的边都必须是偶数条 ， 这不难理解 ， 因为每次到达后都会离开 。 事实证明反之亦然 ， 也就是说 ， 如果网络中的每座城市都有偶数条连接 ， 那么网络中的连接一定能构成一个往返旅程 。
连接所有城市的最短树则缺乏这种“偶数性” ， 因为位于分支末端的城市只存在一条连接 。 克里斯托菲德斯算法找到了最佳的方式 ，将拥有奇数条连接的城市相连 ， 就让最短树变成了一个往返旅程 。 随后他证明 ， 由此产生的往返旅程最多比最优解长50% 。
克里斯托菲德斯算法是理论计算机科学中最著名的近似算法之一 ， 它也成了不少教科书和课程中经常出现的最佳案例 。 但计算机科学家一直相信 ， 应当存在比克里斯托菲德斯算法更优的近似算法 。 毕竟 ， 克里斯托菲德斯算法虽然简单直观 ， 但并非总是那么高效 ， 因为连接城市的最短树或许并非可选择的最佳主干 。 比如 ， 如果这个树有许多分支 ， 那么分支末端的每座城市都需要与另一座城市相匹配 ， 这可能会带来大量昂贵的新连接 。
当时许多人认为 ， 不久就会有人对克里斯托菲德斯的简单算法提出改进 。 但事情并没有这么简单 。
直到10年前 ， Gharan和他的博士导师以及合作者开始研究提高克里斯托菲德斯算法的可能 。 他们受到了另一种版本的TSP的启发 。 在这个版本中 ， 你可以选择一种组合路径 。 例如 ， 如果你想去A地 ， 可以选择3/4的B到A的路径 ， 加上1/4的C到A的路径 。 这种“分段版本”的问题虽然没有实际的物理意义 ， 却能够有效地求解 。 对计算机科学家来说 ， 它也可以作为对求解一般性TSP的一种思路引导 。
因此 ， Gharan等人没有选择连接所有城市的最短树 ， 而是从一个精心筛选的集合中随机选择一个树 。 他们创建了新的算法 ， 利用一种随机过程创建出树 ， 在这样的树中 ， 拥有奇数条连接的城市倾向于有邻近的“搭档” 。 接着再用类似克里斯托菲德斯算法的方式 ， 将这些城市与其“搭档”相连 ， 就能创造出一个完整的往返旅程 。
|44年，10?3?的关键突破
本文插图

Gharan等人提出的新算法的近似解 ， 先利用随机过程创建树 ， 然后再将它转换成完整的往返旅程 。 | 图片设计：雯雯子；素材参考：[1]
这种方法似乎很有前景 ， 他们相信这是一种更好的算法 ， 但严谨地证明出这种优越性并非易事 。
2011年 ， Gharan等人成功证明 ， 他们的新算法在“图形化”TSP上比克里斯托菲德斯算法更优 。 “图形化”TSP可以理解成TSP的一类特例 ， 也就是城市之间的距离由一个网络（不一定包括所有连接）表示 ， 每边长度相同 。 但他们一直没能将结果推广到一般性TSP中 。
几年来 ， Gharan仍然在一直思考这个问题 。 他认为 ， 数学中的多项式几何（geometry of polynomials）领域可能是解决问题的关键工具 ， 但理论计算机界对这一数学领域知之甚少 。 Gharan在与Karlin共同指导研究生Klein时 ， 他们决定共同推进对这个问题的研究 。
在第一年里 ， 他们先从一种简化版本入手 。 尽管困难重重 ， 但他们开始对所用的工具有了感觉 ， 尤其是多项式几何 。
多项式是由常数和变量的幂运算等组合而成的表达式 ， 比如x2y+2yz? 。 在TSP中 ， 研究人员将一张城市地图提炼成一个多项式 ， 其中每座城市之间的连接是一个变量 ， 可以连接所有城市的每个树是一项 。 数值因数随后为这些项加权 ， 反映出旅行售货员问题的分段解中每条边的值 。
他们发现 ， 这个多项式有一种迷人的性质 ， 也就是“实稳定性”（real stability） ， 也就是说 ， 让多项式为零的复数永远不在复平面的上半部分 。 实稳定性带来的优势是 ， 即使对多项式做出许多改变 ， 它仍然有效 。 例如 ， 当研究人员操控一些更简化的多项式时 ， 他们操控的结果仍然具有实稳定性 ， 这就为各种各样的技巧打开了大门 。
这使得研究人员能够更好地处理一些问题 。 终于 ， 在一份80多页的论文中 ， Karlin、Klein和Gharan证明出 ， 10年前设计出的算法确实比克里斯托菲德斯算法要更好 。 新算法在克里斯托菲德斯算法（3/2近似比）的基础上 ， 将近似比提高到了 3/2 - 10?3? 。
虽然这一微小的数字看似不足为道 ， 但许多理论计算机学家相信 ， 它突破了理论和心理上的僵局 。 研究人员希望 ， 这能为进一步的提高开辟道路 。
参考来源：
https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/
https://arxiv.org/pdf/2007.01409.pdf
封面来源：pikrepo.com
来源：原理
编辑 ：前进四
【|44年，10?3?的关键突破】声明：转载此文是出于传递更多信息之目的 。 若有来源标注错误或侵犯了您的合法权益 ， 请作者持权属证明与本网联系 ， 我们将及时更正、删除 ， 谢谢 。


    推荐阅读


    上一篇：爱生链社群电商服务|爱生链——公司是船，我在船上

    下一篇：15匹马力的法国货 堪比GPR125 售价却高达2.7万