《迷茫的旅行商》书评

Intellectual Endeavor

关于经典的TSP问题的一切...TSP问题看似简单，特别是在问题规模较小时，最优解似乎是不言自明的，但当问题规模不断扩大，即使是人脑这样的“超大规模并行”的wetware也会立刻感到无所适从、进而“迷茫”。那最终使我们走出黑暗的、不服输的智慧火花又一次在热烈的燃烧中接力，于是有了最近邻算法、有了贪心算法、有了插入算法、有了Christofides算法、有了LKH算法、有了线性规划算法...当问题解决方案带来的提升逐渐由量变转为质变，我们期待的或许已是另一场变革。

关于作者的其他贡献

作者William J. Cook在上世纪90年代曾参与过TSP求解器Concorde的开发。2001年，Concorde因为高效地求解了CMG公司于1996年提出的15,112城市的车辆路径问题获得5000欧元奖励；2005年，求解了电路板上的33,810城市的TSP；2006年，作者和他的同事精确求解了在芯片布线中产生的85,900城市的TSP，创下了当时TSP求解规模的世界纪录；2007年, Hahsler & Hornik对当时TSP的所有主流启发式算法和精确算法进行了评估。给Concorde的评价是“当时最先进的实现”“世界上最好的精确求解器之一”。Concorde至今仍在被广泛地应用于各行各业。它应用过的场合有：基因图谱、蛋白质功能预测、车辆路径问题求解、图像处理、船舶调度，等等。参考文献：[1] https://en.wikipedia.org/wiki/Travelling_salesman_problem[2] https://en.wikipedia.org/wiki/Concorde_TSP_Solver