第645章 44年，关于一个PNP问题的10的关键突破
你是一位辛苦而忙碌的推销员，需要穿梭在许多城市之间。假设现在你有一系列目的地城市需要逐一拜访，并最终返回你生活的那座起点城市。你已经做了充足的准备，知道任意两座城市之间的距离，那么，应当如何规划旅行路径，才能使得整个旅程最短呢？
虽然描述和理解起来并不复杂，但这绝不能算是一个简单的问题，尤其是当“城市”的数量远不止三五座，而是一个庞大的数字时，问题的复杂程度也可能变得超乎想象。
这个问题有个专属的名字，它通常被称为旅行推销员问题（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）。这种算法利用了连接所有城市的最短“树”，也就是没有闭合回路的连接（或者叫“边”）网络，然后将这种树作为主干，随后添加额外的连接，将它转换成完整的往返路径。
这是一个简单的TSP例子，在这个例子中，最优解并不复杂。而克里斯托菲德斯算法会先找到连接所有城市的最短树，然后再将它转换成完整的往返旅程。
在任何往返旅程中，连接每座城市的边都必须是偶数条，这不难理解，因为每次到达后都会离开。事实证明反之亦然，也就是说，如果网络中的每座城市都有偶数条连接，那么网络中的连接一定能构成一个往返旅程。
连接所有城市的最短树则缺乏这种“偶数性”，因为位于分支末端的城市只存在一条连接。克里斯托菲德斯算法找到了最佳的方式，将拥有奇数条连接的城市相连，就让最短树变成了一个往返旅程。随后他证明，由此产生的往返旅程最多比最优解长50%。
克里斯托菲德斯算法是理论计算机科学中最著名的近似算法之一，它也成了不少教科书和课程中经常出现的最佳案例。但计算机科学家一直相信，应当存在比克里斯托菲德斯算法更优的近似算法。毕竟，克里斯托菲德斯算法虽然简单直观，但并非总是那么高效，因为连接城市的最短树或许并非可选择的最佳主干。比如，如果这个树有许多分支，那么分支末端的每座城市都需要与另一座城市相匹配，这可能会带来大量昂贵的新连接。
当时许多人认为，不久就会有人对克里斯托菲德斯的简单算法提出改进。但事情并没有这么简单。
直到10年前，Gharan和他的博士导师以及合作者开始研究提高克里斯托菲德斯算法的可能。他们受到了另一种版本的TSP的启发。在这个版本中，你可以选择一种组合路径。例如，如果你想去A地，可以选择3/4的B到A的路径，加上1/4的C到A的路径。这种“分段版本”的问题虽然没有实际的物理意义，却能够有效地求解。对计算机科学家来说，它也可以作为对求解一般性TSP的一种思路引导。
因此，Gharan等人没有选择连接所有城市的最短树，而是从一个精心筛选的集合中随机选择一个树。他们创建了新的算法，利用一种随机过程创建出树，在这样的树中，拥有奇数条连接的城市倾向于有邻近的“搭档”。接着再用类似克里斯托菲德斯算法的方式，将这些城市与其“搭档”相连，就能创造出一个完整的往返旅程。
小主，这个章节后面还有哦^.^，请点击下一页继续阅读，后面更精彩！