4.6 路线之王

启发式算法需要在运行时间和路线质量之间权衡取舍。有些算法成本最为昂贵，人们愿意花费超长的计算时间，只求达到可以实现的最好结果。他们的竞争毫无限制，相互毫不手软，热烈程度堪比一级方程式赛车。选手竞相寻找周游难题数据集的路线，力图突破当前最好路线的长度。

图4-30　Keld Helsgaun（左）和永田裕一（右）

毫无疑问，在该领域，丹麦人Keld Helsgaun和日本人永田裕一双双荣登世界冠军的宝座。Helsgaun的LKH程序自从1998年诞生以来，一直是寻找路线领域的标杆，而他也在不断扩展和改进他的算法，向其注入诸多新鲜的思想。对世界旅行商问题，他的路线是迄今最好的；对破纪录的85 900座城市TSP，他的路线是绝对最优的；在VLSI Test Collection的排行榜上，他的名字随处可见。¹不过永田裕一也不甘落后，他实现了一种TSP遗传算法，并以此求出了《蒙娜丽莎》TSP挑战的已知最佳路线，也给出了National TSP Collection中规模最大的两道题目的最佳答案。²你如果有一道大规模的题目，希望得到出色的答案，找这两位就对了。

^{1. http://www.tsp.gatech.edu/vlsi/index.html.}

^{2. http://www.tsp.gatech.edu/world/countries.html.}