编者按：目前介绍旅行商问题比较全面的电子书是《The Traveling Salesman Problem and Its Variations》和《The Traveling Salesman Problem: A Computational Study》，汇聚了当今最高效的优化算法，有志于解决TSP的同志们推荐一看。

数学家们努力想搞定这个似乎不可解的问题，在这一过程中他们隐隐约约地看到了计算的局限性。

通过计算，找出在众多城市间旅行的最短路线彻底无望了吗（不是只找一条比较好的路线，而是要找一条肯定最短的路线）？

旅行商问题

此问题被称为旅行商问题（traveling salesman problem，简称TSP）。至少从19世纪初开始，历代数学家就一直在为这个问题冥思苦想，绞尽脑汁而不得其解。

找到一种能迅速摆平任意一个TSP的方法，将是数学界取得的一项惊人突破。利用复杂性理论（complexity theory），这种方法可以高效地解决任何计算问题，而且所得答案很容易验证。

蒙娜丽莎—— 一个旅行商问题的解

绝大多数数学家认为，这样的方法是不可能存在的。

不过，还是让我们来做一个假设：你要去100000座城市旅行。难道真没有办法找到最短旅游路线？我们的意思不是要找到解决所有TSP的方法，而只是问，在这100000座城市中旅游时，最短的路线是什么。

企鹅—— 一个旅行商问题的解

为了解决这个难题，你最好记住尤基·贝拉（Yogi Berra，美国一位棒球明星）的忠告：“当你走到岔路口时，慎之！”我们可以借助一种名为线性规划的工具来实现这一策略：在遇到岔路口时，不要马上决定是否走某条路，而是给连接两座城市的道路分配一个分数。在这种模型中，完全可以让“半个”推销员分别走岔路口的两条支路。

此过程开始时有这样一个要求：对于每座城市，分配给来路和去路的分数之和应等于1。随后，会有更多的限制一步一步地添加进来，而每条限制均与分配给各条道路的分数之和有关。线性规划最终会为我们指出，走哪条路是最佳选择，从而得出最短路线。

罗马斗兽场—— 一个旅行商问题的解

我要补充的是，“100000座城市”其实并不是一个假想的问题，而是美国欧柏林学院的罗伯特·博施（Robert Bosch）提出的一个含有100000个点的点阵，用最短路线把这些点连起来，将会是蒙娜丽莎的画像。目前，数学家都在为解决这个难题而努力。

或许我们无法搞定每一个TSP问题，但是层出不穷的新招将会逐步扩大可解范围。总体看来，复杂性理论认为，在科学研究以及其他领域中，通用计算方法的潜力是有限的。它们有哪些局限性？这些局限性在多大程度限制了我们对知识的探索？研究TSP问题的意义正在于此。

在美国13509个城市之间旅行的最佳路径