江苏龙网

  1. 首页 > 资讯 > 科技 > >

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


当时许多人认为 ， 不久就会有人对克里斯托菲德斯的简单算法提出改进 。 但事情并没有这么简单 。
直到10年前 ， Gharan和他的博士导师以及合作者开始研究提高克里斯托菲德斯算法的可能 。 他们受到了另一种版本的TSP的启发 。 在这个版本中 ， 你可以选择一种组合路径 。 例如 ， 如果你想去A地 ， 可以选择3/4的B到A的路径 ， 加上1/4的C到A的路径 。 这种“分段版本”的问题虽然没有实际的物理意义 ， 却能够有效地求解 。 对计算机科学家来说 ， 它也可以作为对求解一般性TSP的一种思路引导 。
因此 ， Gharan等人没有选择连接所有城市的最短树 ， 而是从一个精心筛选的集合中随机选择一个树 。 他们创建了新的算法 ， 利用一种随机过程创建出树 ， 在这样的树中 ， 拥有奇数条连接的城市倾向于有邻近的“搭档” 。 接着再用类似克里斯托菲德斯算法的方式 ， 将这些城市与其“搭档”相连 ， 就能创造出一个完整的往返旅程 。
【|44年，10?3?的关键突破】
|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
来源：原理
编辑 ：前进四
声明：转载此文是出于传递更多信息之目的 。 若有来源标注错误或侵犯了您的合法权益 ， 请作者持权属证明与本网联系 ， 我们将及时更正、删除 ， 谢谢 。


推荐阅读


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

下一篇：什么值得买|用老旧mate9在天猫超市抢茅台分享