江苏龙网

  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?的关键突破】
44年，10?3?的关键突破
本文插图
这是一个简单的TSP例子 ， 在这个例子中 ， 最优解并不复杂 。 而克里斯托菲德斯算法会先找到连接所有城市的最短树 ， 然后再将它转换成完整的往返旅程 。 | 图片设计：雯雯子；素材参考：[1]
在任何往返旅程中 ， 连接每座城市的边都必须是偶数条 ， 这不难理解 ， 因为每次到达后都会离开 。 事实证明反之亦然 ， 也就是说 ， 如果网络中的每座城市都有偶数条连接 ， 那么网络中的连接一定能构成一个往返旅程 。
连接所有城市的最短树则缺乏这种“偶数性” ， 因为位于分支末端的城市只存在一条连接 。 克里斯托菲德斯算法找到了最佳的方式 ，将拥有奇数条连接的城市相连 ， 就让最短树变成了一个往返旅程 。 随后他证明 ， 由此产生的往返旅程最多比最优解长50% 。
克里斯托菲德斯算法是理论计算机科学中最著名的近似算法之一 ， 它也成了不少教科书和课程中经常出现的最佳案例 。 但计算机科学家一直相信 ， 应当存在比克里斯托菲德斯算法更优的近似算法 。 毕竟 ， 克里斯托菲德斯算法虽然简单直观 ， 但并非总是那么高效 ， 因为连接城市的最短树或许并非可选择的最佳主干 。 比如 ， 如果这个树有许多分支 ， 那么分支末端的每座城市都需要与另一座城市相匹配 ， 这可能会带来大量昂贵的新连接 。


推荐阅读


上一篇：海水淡化|海水取之不尽用之不竭，为什么人类还面临水资源短缺的4个原因

下一篇：周震南父母被曝是老赖欠款上亿|R1SE男团再起风波！周震南父母被曝是老赖欠款上亿