🦎 💚 👩🏾‍⚖️ IT专家在未铺砌的道路上行走 👨🏿‍🎓 👩🏿‍🤝‍👩🏾 👲

经过数十年的停滞，已经发现了旅行商问题的新捷径。

不久前，来自斯坦福大学和麦吉尔大学的一组研究人员以难以想象的小数目打破了35年的计算机科学记录-减少了万亿分之一万亿兆的百分之四十分之一。突破-在计算机科学经典问题中遇到的推销员问题-太小了，没有任何实用价值，但他为寻求改进的近似解决方案注入了新的生命。

任务的构成如下：对于一组通过道路连接的城市，有必要找到返回起点的最短途径来访问每个城市。该问题的解决方案具有实际应用，从在印刷电路板上打孔到在计算机上管理任务计划并组织基因组特性。

推销员问题很容易提出，并且从理论上讲，通过检查所有可能的闭合路径以找出最短的问题，很容易解决。暴力破解方法的问题在于，随着城市数量的增长，相应的路径数量很快就会超过最快的计算机的能力。对于十个城市，有超过30万条路线。对于15个城市，其数量增加到870亿。

Christofides算法

在早期计算机时代，数学家希望有人能找到解决该问题的简便方法-一种算法，可以在合理的时间内解决该问题。但是，尽管程序员在特定情况下取得了进展-确定了1950年代49个城市，1980年代2,392个城市和2006年85,900个城市的最短路径，但没有人提出一种能有效解决一般情况下问题的算法。根据1972年的杰出工作，有可能根本不存在这种算法。加州大学伯克利分校的计算机科学家理查德·卡普（Richard Karp）表明，推销员问题是NP完全的，这意味着没有有效的算法（除非有人证明P = NP-但大多数科学家认为并非如此）。。

遍及全美500个以上人口的13,509个城市中最短的路线（根据1998年数据），

在Karp出版后，许多计算机科学家开始开发一种有效的算法来找到问题的近似解决方案-闭合路径的长度仅比最短路径略长。在这里，他们更加幸运-1976年，伦敦帝国学院的教授Nikos Christofides开发了一种算法，该算法所产生的路径保证不会超过最短路径超过50％。

创建该算法后，许多科学家认为，该算法非常简单，可以让学生在一个小时内学习，它将成为中间环节，在此之后，将找到一个更复杂，更近似的真实解。但是几十年后，这种算法从未出现。

普林斯顿大学的科学家Sanjeev Arora说：“几乎所有计算机科学专业的学生都花了数周或数月的时间来尝试改进Christofides的算法。”

最终，在2011年，斯坦福大学和麦吉尔小组超越了某些类型的推销员任务的50％保证，并表明他们的解决方案将超过最短路径不超过49.99999999999999999999999999999999999999999999999696％。

从那时起，由于对问题的重新审视，出现了许多改进的近似算法。麻省理工学院IT专家Michel Goemans表示，尽管这些近似值仅适用于某些类型的旅行推销员任务，但它们的方法是很有前途的。

他说：“我们只轻微触摸了表面。” “我相信也许五年内，我们将取得更令人印象深刻的成果。”

最短的树

蒙娜丽莎（Mona Lisa）作为100,000个城市之间的路径

Christofides算法并非从搜索最短路径开始，而是从寻找最小的生成树开始-一组分支连接城市而没有闭环。与最短路径不同，最小生成树很容易构建-您需要先寻找两个城市之间的最短路径；这将是第一个分支。要添加以下内容，您需要找到新城市和前两个城市之一之间的最短路径-以此类推，直到覆盖所有城市。

生成的树不是旅行商问题的可能解决方案之一，因为它没有给我们闭合的路径。但是它可以变成一条路径，想象树枝是墙壁，然后沿着树走，使手指触摸墙壁直到开始。最终的步行经过每个城市然后返回，但通常距离最短的路径很远，因为它沿着相同的路段多次通过-我们在一棵树上每堵墙走两次，每侧一次。

但是，最坏情况下的最终路径不超过最短路径的两倍。通过添加经过特别选择的分支并应用一些技巧，Christofides展示了如何缩短此路径，以使它不超过最短路径超过50％。

最小的生成树是构建短期解决方法的自然起点。但是这种方法也为研究人员试图获得Christofides 50％的保证提供了一个起点。毕竟，尽管起初最小的生成树看起来很有效，但其他树可能更适合于将树转换为变通方法的过程-例如，您只需要向树中添加一条分支而不分支即可使其成为变通方法。

因此，目标是找到一棵在长度和简单转换为替代方法之间取得平衡的树。没有用于搜索理想树的有效算法（如果P = NP不为真），但是成功的近似算法仅需要找到足够好的算法。

分数旅程

通往“合理良好”树的路径包括一种流行的，尽管违反直觉的技术，该技术可以识别特定任务的分数解。例如，小范围的解决方法可能包括在明尼阿波利斯和底特律之间旅行，以及在克利夫兰和底特律之间旅行。从实际的角度来看，这样的路径是没有意义的。但是它可以用数学方式准确地描述，并且与经典的旅行推销员问题不同，可以有效地解决这种分数形式。

通过计算问题的分数形式的解，然后智能地对份额取整以获得原始问题的近似解，可以解决计算机科学中的许多近似问题。但是直到最近，还没有人想到如何解决旅行商问题。

2009年，斯坦福大学的Amin Saberi和当时的研究生Arash Asadpour开发了一种通用的舍入方案，该方案使用随机数选择一个整数解，该整数解保留了尽可能多的分数解性质。 Saberi认为这种模式让人想起“寻找钉子的沉重锤子”。而且他怀疑推销员的任务可能是正确的选择。

几个月后，现在在瑞士洛桑联邦理工学院工作的Saber，Asadpur，Gomans，斯坦福大学研究生Shayan Gharan和Aleksander Madry证明，新的舍入技术可以为一种选择提供良好的近似算法推销员的任务，即“不对称”情况。一年后，麦吉尔大学的Saberi，Garan和Mohit Singh使用相同的方法为通常的旅行推销员问题开发了一种新的近似算法。

最多的旅行商推销员问题是2006年计算的85,900个城市之间的路程。 “城市”的位置与贝尔实验室中特定计算机芯片的设计相对应，该解决方案是用激光切割技术的最短方法

收到城市和路线图后，新算法首先计算出行销商问题的精确分数解。然后，他将此解决方案四舍五入为一棵生成树，从理论上讲，该生成树应在长度和简单转换为变通方法之间取得平衡。最后，该算法在Christofides网络中包括此树，而不是最小生成树。

萨贝里说，新算法是“一个可以在几个小时内解释的想法，但是它的证明花了大约一年的时间。”

经过长时间的分析，Stanford / McGill团队能够针对一小部分推销员任务（“图形”）改进Christofides的算法。几个月后，在成功的启发下，其他团队使用了其他舍入方案，以更好的近似性获得了图形案例的算法。当前的记录是40％，比Christofides的50％好得多。

图形案例“包括了在一般问题中遇到的许多相同的困难，”阿罗拉说，并补充说，在图形案例中工作的方案对于一般的旅行推销员问题可能是有用的。

但是，Sabre说，解决一般的近似推销员问题可能需要新的思路。“数学发现就像在黑暗的房间里移动。他说：“你伸出手去找椅子，伸出手来找桌子，”他用数学家安德鲁·威尔斯（Andrew Wiles）来解释。“在某个时候，手找到了一个开关，突然一切都变得清晰了。就推销员的任务而言，即使在完成了许多工作之后，发现了可能的界限，在我看来，我们似乎也没有找到这种转换。”

IT专家在未铺砌的道路上行走

经过数十年的停滞，已经发现了旅行商问题的新捷径。

Christofides算法

最短的树

分数旅程

More articles: