2020年10月25日，中科院物理所的Erica发布了一篇文章，探讨了旅行推销员问题（TSP）的历史与最新进展。TSP是理论计算机科学中的一个著名问题，涉及如何在多个城市之间找到最短的旅行路径。尽管这个问题看似简单，但随着城市数量的增加，其复杂性也急剧上升。几十年来，计算机科学家们一直在寻找更优的算法来解决这个问题。
1976年，Nicos Christofides提出了一种算法，可以找到TSP的近似解，并保证这个解最多比最优解长50%。然而，计算机科学家们一直相信，应该存在比Christofides算法更优的近似算法。直到2011年，Shayan Oveis Gharan等人提出了一个新的算法，利用随机过程创建树，然后再将其转换成完整的往返旅程。
在最近的一篇论文中，Anna Karlin、Nathan Klein和Shayan Oveis Gharan证明了10年前设计出的算法确实比Christofides算法要更好。新算法在Christofides算法的基础上，将近似比提高到了3/2 - 10³。虽然这一微小的数字看似不足为道，但许多理论计算机学家相信，它突破了理论和心理上的僵局。研究人员希望，这能为进一步的提高开辟道路。