第4章 探寻路线

我们并不宣称该程序万无一失，只是说它能在可行的计算时间内给出较好的结果。

——Robert Karg和Gerald Thompson，1964年¹

_{1. Karg, R. L., G. L. Thompson. 1964. Management Science 10, 225–248.}

就算听到TSP不可解的断言，巡回旅行商也不会大惊小怪。他照旧会发动汽车，上路拜访顾客，履行自己的使命。基于这种脚踏实地的心态，便出现了另一种思路，即暂时抛开必须找到绝对最优解的念头，转而关注如何尽快求出近优解。在新观点的影响下，人们为了让旅行商来得及回家吃晚饭，提出了各种富有想象力的想法。事实上，在这一方向的TSP研究中，许多技巧和方法得到了发展和应用，如今亦成了计算科学领域的重要工具，如模拟退火算法（simulated annealing）、遗传算法（genetic algorithm）、局部搜索算法（local search）等。寻找路线的题目相当于沙箱，用来测试旨在从大量情形中寻找最优解的算法。这些题目同样也是TSP研究的训练场，只不过在这里，训练科目不胜枚举，得到的结论也非同小可。