10.1 人机对战

1997年，世界冠军Gary Kasparov与IBM公司的深蓝（Deep Blue）计算机之间展开一场国际象棋比赛。这场较量俨然如同知名体育赛事，参赛双方均吸引了热情的支持者。有人希望机器发展再受到几年的牵制，于是为人类冠军加油助威；也有人是软硬件爱好者，因而投入计算机阵营。科幻作家Charles Sheffield负责为IBM公司报道该竞赛。在本质上属于计算问题的赛事中，人类居然能与大型计算机势均力敌，不相上下，这一事实令保持中立的Sheffield颇为意外。他开始思索，如果换作其他棘手的计算难题，人类能否具有同样的竞争力，比如换成TSP。

面对一场TSP的人机大决战，如果按照Sheffield的建议，不考虑特殊学习和训练，我会赌计算机取胜。这种选择一部分是因为我的个人经验。在2007年的一次数学研讨会上，Sylvia Boyd提出一道50座城市的TSP，掀起一场挑战赛，规则是所有计算一律要求人工完成。挑战赛持续了一天，我和Dave Applegate得出了获胜路线（如图10-1所示），以微弱的优势战胜另一位TSP研究者Gérard Cornuéjols。可惜的是，这条路线不是最优路线。我们研究TSP已经有20年了，可是在计算机不到一秒钟就能算出的结果面前，依然只能望洋兴叹。

图10-1　数学会议上的获胜路线