尝试计算访问大量城市的最短路线是否毫无希望？ 不仅仅是一条好的路线，而是有保证的最短路线。 这项任务是长期存在的挑战，被称为旅行推销员问题，或简称 TSP。
找到一种可以快速解决 TSP 每个实例的方法将是数学上的一个惊人突破。 使用复杂性理论，这种方法将使我们能够有效地解决任何可以轻松验证答案的计算问题。 大多数数学家都认为这是不可能的。
但是，假设您获得了 100,000 个城市的位置。 找到最短路线真的不可能吗？ 我们不是要求解决 TSP 的每个实例，只是想找到绕这些特定位置的最快方法。
关于支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。 通过购买订阅，您正在帮助确保有关塑造我们当今世界的发现和想法的具有影响力的故事的未来。
为了迎接挑战，您最好的选择是听从瑜伽大师贝拉的建议：“当你走到岔路口时，就走过去。” 一种名为线性规划的工具允许我们通过为连接城市对的道路分配分数，而不是立即决定是否使用某条道路来做到这一点。 在这个模型中，让一半的推销员沿着岔路的两个分支走是完全可以的。 该过程从对每个城市的要求开始，即分配给到达和离开道路的分数之和均为 1。 然后，逐步添加更多限制，每个限制都涉及分配给道路的分数之和。 线性规划最终会为我们指出每条道路的最佳决策，从而指出最短的可能路线。
我应该补充一点，100,000 个城市并非假设性的挑战。 当前的计算正逼近奥柏林学院的罗伯特·博世创建的一组漂亮的 100,000 个点的解决方案，其中巡回路线描绘出了蒙娜丽莎的画像。 我们可能无法解决 TSP 的每个示例，但新的想法可以推动可解性的前沿。
这就是大局：复杂性理论表明，科学和其他领域的通用计算技术的能力存在局限性。 这些局限性是什么？它们在多大程度上限制了我们对知识的追求？ 这就是对 TSP 进行研究的全部意义。
本文以“旅行推销员案例”为标题在印刷版上发表。