最初以一个悬赏项目为引子。1962年春季，宝洁机构设立了一项奖金为1万美元的挑战活动，其内容是此番。设想两位执法人员欲驾车遍访美国，他们以芝加哥作为行程的出发点，途中务必途经32座指定都会，最终再返回芝加哥。需要为他们设计一条路径，以便他们在途中的总行程距离最为精简。听完这个悬赏项目，你是否感觉跃跃欲试？这个问题有一个貌似简单的解决方式：先找出所有穿过这33座城市的路径，再逐一测算它们的距离，然后把其中最短的那条路径告知宝洁公司，接下来只需静候那张价值1万美元的支票送到家里来。
这种通过逐一列出所有潜在路径的技巧在数学领域被称为“穷举法”。这种穷举法看似直接且完备，然而针对当前情形却存在一个显著障碍：因为潜在路径的总数极为庞大，所以无法进行逐一验证。
我们考察一下这个问题的潜在路径有多少种。起始城市必须是芝加哥，第二站从其余32个城市中挑选，因而有32种选项，第三站从剩下的31个城市中选定，有31种可能，依此类推。最终能够得到路径的总数就是32乘以31乘以30乘以……乘以3乘以2乘以1。这个数值在数学上称作32的阶乘。32的乘积是多少？大约为2.63乘以十的三十五代数，要是觉得这个数难以想象，可以拿沙子的总数来作比较。有人计算过，全球所有海岸沙滩和内陆沙漠里的沙子加在一起，总数大约在十的二十四次方到十的二十五次方之间，所以32的乘积大概相当于地球上所有沙子数量的数十亿倍。计算全部潜在路径的长度需要多长时间？以2009年全球运算能力最强的超级计算机集群IBM“走鹃”为例进行说明。走鹃拥有129600个处理单元，每秒能完成1点457万亿次运算。如果确定每条路径的长度仅需一次数学计算，那么借助这台超级计算机处理该任务，所需时间将超过两千八百亿年。阅读至此，或许部分读者会思考，鉴于计算机学科近几十年来进步神速，如今的巨型计算机能否攻克这个难题呢？2024年全球性能最强的计算机系统出自美国，名为Frontier，其运算速度达到了每秒百亿亿次，这个数字是2009年走鹃系统的千万倍。但是，经过一番推算可以明白，即便运用眼下最顶尖的巨型机系统，处理那涉及33座城市的旅行商难题，也要耗费近28万年。
因此，通过蛮力尝试的方式处理这个情形显然效果不佳，必须寻求速度更快且效率更高的计算方法。宝洁公司所提出的那个寻找环绕三十三座城市最短路径的课题，属于旅行商类问题。这类问题通常的表述为：针对一个特定的城市集合，探寻一条以某个城市为起点，遍历所有城市各一次并最终回到起点的最短路线。在阐述数学家解决旅行商问题的方案之前，我们必须关注一个事实，即自20世纪40年代以来，旅行商问题持续在数学界享有很高声誉，数学家们似乎从未停止过探索这个议题。那么，数学家为何会对这个问题产生浓厚兴趣呢？首先，旅行商问题蕴含诸多实际应用价值。
旅行商难题其实就是要确定最佳路径，而确定最佳路径这种需求由来已久，对许多人来说一直是个关键议题。最早着手研究怎样找到最短路径的群体，或许就是旅行商们。书中提及一封1925年旅行商写给其上司的信件。该旅行商供职于美国某企业，负责汇总玉米等农业作物的订购信息。这封信里，这名旅行者介绍了他在缅因州巡游的关键地点和行程安排，从7月持续到8月，总共探访了350个位置，他非常在意行程规划如何能让旅途过程最节省时间，毕竟他的旅行路线是反复推敲并调整过的，非常注重实用性和效率。
过去除了旅行商，法官、律师和牧师等许多职业的人也常需迁徙，法官和律师尤其如此，因为早在15世纪，英国司法管辖区制度就要求各地法庭每年固定开庭审理案件，这迫使他们在各自分管的城镇间来回奔波，必须精心设计行程路线。现代人从事销售工作，常常要驾车前往多个城镇探望顾客，规划一条便捷的行程对他们意义非凡，此即旅行商难题。另外，客运企业要安排客车在各站点之间载客，货运企业要设计货车运输货物的路径，还有外卖企业要为配送员规划最佳送餐路线，确保将多个订单送到不同位置，这些均属于旅行商问题范畴。除了为人类规划路径，旅行商问题还能为各类观测设备与加工装置规划最优移动轨迹。
美国喷气推进实验室的科研人员，运用空间望远镜在太阳系周边探寻围绕其他恒星公转的类地天体。由于空间望远镜的转动会消耗大量燃料，并且观测每颗恒星都要耗费较多时间，所以必须明确观测的次序，这实质上就是旅行商问题。机械制造业里，很多重复性劳动如钻孔和组装，通常由设备承担，这就引出了不少路径规划难题。以电子产品的生产流程为例，印刷电路板在加工时，需要自动钻头在多处钻孔，以便后续焊接各类电子元件和线路。怎样为钻头设计一条最优移动轨迹，使其总行程最短，便构成了一个典型的路径规划问题。另外，怎样为自动焊接设备规划一条最优路径，使其能接连处理多个焊接点，其核心也是一个旅行商问题。诸如去除硅晶片瑕疵、制造计算机芯片、对黄铜进行雕刻、运用激光技术雕刻水晶饰品等作业，均需为相应机器确定一条效能最高的路径，这些情况都属于旅行商问题。另外，诸如工厂的运营安排，微芯片的检验，光盘的图案存放方式等场景，同样能够转化为旅行商问题。
一个表面看来与旅行商问题没有关联，但实际上能够借助旅行商问题加以解决的任务，就是绘制基因组图谱。绘制基因组图谱，其核心是要弄清众多基因在染色体上的具体排布。要获取这一信息，必须经历两个环节。第一个环节，是要弄明白不同基因彼此之间的距离关系。第二个环节，则是依据前述信息，在染色体上摆放这些基因的具体位置。先来探讨第一个环节。我们想知道基因A和基因B在染色体上的相对位置。一种名为辐射杂种细胞作图的技术可用于此目的。这种技术首先通过辐射照射细胞，使基因A和基因B所在的染色体断裂。接着将辐射处理的细胞与正常细胞结合，产生辐射杂种细胞。在这些杂种细胞里，基因A和基因B会分别进入不同的染色体区域。重要环节在于，我们能够检测出这些辐射变异细胞里，基因A与基因B位于同一染色体的几率有多高。倘若A与B常常共存于一条染色体，意味着它们彼此邻近；倘若基因A和基因B多数分散在不同的染色体，表明它们相隔遥远。打个比方，这好比古代某个政权屡屡发生战事，而后每次战事结束后，胜者都会重新划定版图范围。当两个地点频繁被划入同一行政单位时，它们之间的距离通常较短，而不常被归为一处则表明相距较远。据此，我们可以依据两地同属一级行政区的频次，来推算它们彼此的远近程度。
已知多个基因间的相互顺序，怎样确定它们在染色体上的具体次序？这就涉及到旅行者难题了。可以把每个基因当作一个"地点"，它们彼此间的"间隔"就是先前计算出的基因相对距离。我们的任务是根据这些相互位置，找出一种基因排序方式，让邻近基因之间的间隔总和达到最低。这种顺序就是基因在染色体上的真实分布方式。举例来说，如果有三个基因分别是A、B、C，根据RH图谱分析可知：A与B距离较近，B和C之间距离也很短，而A和C的间隔相对较大。我们立刻会想到这三个基因的排列方式可能是A—B—C，因为这条路径的总跨度，要小于其他路径，比如B—A—C或者A—C—B等路线。
旅行商问题核心在于寻找最短路径，因此可借助该问题方法确定基因序列。通过前述技术，美国国立卫生研究院研究团队成功绘制了涵盖人类、恒河猴、马、狗、猫等多种生物的遗传图谱。由此，你当可立时体察到数学的强大作用了。诸多表面迥异的现实应用课题，一旦加以提纯，便会发觉它们都内蕴着同一的数学议题。攻克了这桩数学议题，那些应用课题也就迎刃而解了。借助前述的例证，我们得以明晰旅行商问题为数学家所垂青的首要缘由：它具有极为丰厚的实际应用价值。不过，在数学家眼中，旅行商问题的价值并不仅仅体现在实际应用层面。这个难题，象征着计算数学与计算机科学领域里一个极为关键的议题，即P是否能够等同于NP。
