它产生于三个人求解一道经典数学问题的研究工作。这个历史悠久的问题叫做“旅行商问题”，无论靠人工计算还是借助最快的计算机都一直无法解决。——IBM 新闻稿，1964 年① 1962 年春天，宝洁公司发起了一场广告宣传活动，在应用数学家中引起了不小的反响。活动的重头戏是一项竞赛，奖金高达1 万美元，在... 查看全部[ 1.1 环游美国之旅 ]
兰德小组的研究工作解决了环游美国48 州的难题，却没有彻底解决TSP。他们取得了一次巨大的成功，并不意味着就能搞定规模更大的题目。事实上，如果拉斯维加斯赌场把TSP 的最终结果作为一项赌博项目，那么在数学家看来，把赌注押在“TSP 永远无法彻底解决”上会有更大的胜算。对此，必须明确一点：我们要找的所... 查看全部[ 1.2 不可能的任务吗 ]
将来或许会有人一举攻破终极的复杂性问题，给出惊天动地的答案。在那之前，我们能做什么？直面旅行商问题，目标非常明确：求解更大规模、更难解决的情形。 TSP 是算法工程（algorithm engineering）①的代表问题。这门研究学科重视实用性，以不达目的誓不罢休为理念。理论上，TSP 的规模一... 查看全部[ 1.3 循序渐进，各个击破 ]
图1-11 的T 恤衫图案出自Jessie Brainerd 之手，她曾参加2007 年的布达佩斯数学项目。①在应用数学专业或者计算机科学专业，每一名毕业不久的合格本科生都能一眼看出这幅图的主题就是TSP。按照许多大学的课程设置，学习旅行商问题都是必经之路。最近，甚至连美国的中学课本里都有该问题的简... 查看全部[ 1.4 本书路线一览 ]