《迷茫的旅行商》 刘雪峰解读

《迷茫的旅行商》｜刘雪峰解读

序言

你好，欢迎每天听本书，我是刘雪峰。今天我要为你解读的这本书，名字叫《迷茫的旅行商》。听到这本书的名字，你第一时间是不是觉得它讲的是一个旅行商在旅途中不断探索、寻找自我的故事。你猜错啦，答案在副标题：一个无处不在的计算机算法问题。

旅行商问题，是一个经典的数学问题。而这本书，讲的是科学家如何在这个问题上一步一步往前突破的。

这本书的作者威廉·库克教授（William J. Cook），是加拿大滑铁卢大学教授，美国国家工程院院士，美国数学学会、美国工业与应用数学学会以及美国运筹学和管理学研究协会会员。他的研究领域专注于运筹学和优化领域，尤其以其对旅行商问题的研究而闻名。

可以说，这是一位顶尖科学家，围绕他一生专注的科研领域，写给大众的一本科普书。从这本书中，我们不仅可以看到科学家在难题前不断求索的努力，听到各种有趣的故事，更可以让我们从科学家解决问题的思路中得到很多启发。

这本书分为12个章节，可以大致分为2个部分。第一个部分主要是介绍背景，也就是旅行商问题的历史渊源和该问题对实际生产生活的意义。第二个部分按照时间顺序，介绍科学家们在这个问题上不断取得的进展和突破。我们首先进入第一部分，问题和背景。

问题和背景

我们先从一个悬赏开始。

1962年春天，宝洁公司发起了一项奖金是1万美元的竞赛，题目是这样的。

假设两个警官打算开车环游美国，他们以芝加哥为旅途的起点，中途必须经过32个指定城市，最后再回到芝加哥。请为他们规划一条路线，使得他们在路上的总里程最短。

听完这个悬赏，你是不是跃跃欲试？因为这个问题的解法似乎非常直接：一个人只要把所有经过以上33个城市的路线找出来，依次计算长度，然后将最短的一条路线寄给宝洁公司，便可坐等1万美元支票寄到家中。

这种直接列举所有的可能路线的方法在数学中被叫“暴力穷举”（brute force）。暴力穷举这个策略看起来简单而完美，但在这个问题上会面临一个潜在的困难：由于可能的路线总数极其庞大，根本不可能逐一检验。

我们来看看这个问题的可能路线有多少。第一个城市固定是芝加哥，而第二座城市是从剩下的32个城市中选择一个，因此有32种可能的选择，第三座城市从剩下的31个城市中选择一个，有31种选择，以此类推。最后可以得到路线的总数就是32×31×30×……×3×2×1。这个数字在数学上记做32的阶乘。

32的阶乘有多大呢？大概是2.63×10^35，如果你对这个数字没有概念的话，我们拿沙粒的数量打比方。有人统计过，把地球上海岸线的沙滩和内陆沙漠的所有沙粒数量加起来，大约是10^24到10^25。所以，32的阶乘可能相当于整个地球上所有沙粒数量的数十亿倍。

那么计算出这么多可能路线的长度需要多长时间呢？书中拿当时2009年全球最快超级计算机集群 IBM“走鹃”（ Roadrunner ）打比方。走鹃包含129600个计算核心，运算速度可达每秒1457万亿次。假设计算每条路线的长度只需要一次算术运算，那么用这台超级计算机来解决该问题，需要超过两万八千亿年。

看到这里，可能感兴趣的读者会想，因为过去几十年里，计算机领域的发展一日千里，那么当前的超级计算机是否可以解决该问题呢？2024年排名第一的超级计算机集群是美国的前沿 （Frontier），每秒钟可以完成“百亿亿次”计算，是2009年走鹃的一千万倍。然而，如果我们稍加计算就会发现，即使这台当前最先进的超级计算机集群，解决上面的33个城市的旅行商问题也需要28万年。

所以，用暴力穷举的方法来解决这个问题显然是不行的，我们需要更快、更高效的算法。

上面的宝洁公司出的这个找到环绕33座城市最短路线的问题，就属于旅行商问题。旅行商问题的一般形式是：在给定的一组城市中，寻找一条从某个起始城市出发，经过每个城市一次并返回起始城市的最短路径。

在我们介绍数学家针对旅行商问题的算法之前，我们需要注意一个现象，就是自从20世纪40年代开始一直到现在，旅行商问题一直在数学界颇负盛名，数学家似乎一直都在不断研究这个问题。

那么，为什么数学家会关心这个问题呢？

首先，旅行商问题有很多实际意义。

旅行商问题本质上是一个规划路线的问题，而规划路线问题很早开始，对于很多人就是一个很重要的问题。

最早关心如何找到最优路线的一类人可能就是旅行商。书中举了一个旅行商在1925年写给其老板的信。这位旅行商在美国一家公司上班，工作内容是收集玉米等农作物的订单。在这封信中，该旅行商列出了他在缅因州巡回的主要目的地和路线。该旅行商从7月到8月，共经过了350个地点。他很关心路线如何走才能让旅途时间最短，因为他的旅行路线是精心设计并修改过的，效率很高。

除了旅行商之外，过去有很多其他职业的人，包括法官、律师，以及牧师也需要四处奔波。早在15世纪，英国的司法管辖区制度规定各地的法庭需要每年定期开庭审理案件，因此法官和律师都要在自己管辖的各城镇之间巡回，他们也需要规划路线。

进入近代社会，推销员往往需要开车去不同的城市拜访客户，找到一条高效的路线对于他们来说非常重要，这也是旅行商问题。

此外，客运公司需要规划客车如何在多个站点接送乘客，货运公司需要规划货车如何配送货物的路线，以及外卖平台公司需要为外卖送餐人员找到一条最优的路线，把多个订单送到不同的地点，这些都是旅行商问题。

除了为人类规划路线，旅行商问题还可以为各种观测仪器和加工设备规划最优移动路线。

美国喷气推进实验室的科学家，操作空间望远镜在太阳系附近寻找环绕其他恒星旋转的类地行星。因为空间望远镜的转动需要耗费大量燃料，而且研究每颗恒星也需要花费大量时间，因此如何确定观测的先后顺序非常重要，这个本质上也是旅行商问题。

现代制造业中，包括钻孔、装配这样的重复性工作常常由机械设备来完成，由此也产生了很多旅行商问题。例如，电子设备中的印制电路板在制作过程中，很多地方需要由自动钻孔机打上小孔，用来焊接各种芯片和电路连接。如何为自动钻孔机规划一条路线，让钻孔机总的移动路线最短，这就是一个旅行商问题。此外，如何为自动焊锡机找到一个最优的路线，让它能够完成多个焊点的焊接任务，本质上也是一个旅行商问题。

清理硅晶片缺陷、生产计算机芯片、黄铜雕刻、激光雕刻水晶工艺品等应用，都需要为相关的设备找到一条效率最佳的路线，这都是旅行商问题。

此外，工厂的作业生产调度、微处理器的测试、DVD的纹理存储布局等等应用，都可以转化成旅行商问题。

书中还讲了一个看似和旅行商问题毫不相关，但是本质上可以用旅行商问题来解决的问题，这就是绘制基因组图谱。

绘制基因组图谱，本质上是要确定多个基因在染色体上的相对位置。

要得到这个信息需要两个步骤。首先，确定不同基因两两之间的相对距离。然后再根据以上信息在染色体上排列这些基因的位置。

先看第一步。我们想知道两个基因，基因A和基因B在染色体上的距离远近。一个技术叫做辐射杂种细胞作图，简称RH作图技术。该技术首先用辐射线照射细胞，切断基因A和基因B所在的染色体，然后把这些经过辐射处理的细胞与正常细胞融合，形成辐射杂种细胞。在这些辐射杂种细胞中，基因A和基因B会分散到不同的染色体片段上。关键来了：我们可以测试这些辐射杂种细胞中，基因A和基因B出现在同一个染色体上的比例。如果A和B经常出现在同一个染色体上，说明它们的位置很接近；如果基因A和基因B通常分布在不同的染色体上，说明它们的位置很远。

打个比方。好比古代一个国家经常打仗，然后每次打完仗，胜利者都会重新划分行政区域。如果某两个地方经常会被分到同一个行政区域，那么这两个地方应该离得比较近，反之则比较远。因此我们可以通过这两个地方出现在同一个行政区域的次数，来推测它们的相对距离。

当得到多个基因两两之间的相对位置关系，如何得到它们在染色体上的排列顺序呢？

这就用到旅行商问题了。我们可以把每个基因看作是一个“城市”，它们之间的“距离”就是我们第一步得到的基因之间的相对距离。

我们的目标是，根据这些相对位置关系，找到一种基因排列顺序，使得相邻基因之间的距离总和最小。这个排列顺序就是染色体上这些基因的实际排列顺序。

比如说，假设我们有3个基因A、B、C，通过RH作图我们知道：A和B很近，B和C也很近，但是A和C比较远。你大脑第一时间想到的这三个基因的排列顺序，是不是应该是A—B—C？

因为A—B—C这条路线的总长度，会比其他的路线，例如B—A—C、A—C—B等更短。

旅行商问题，本质上就是找一条总长度最短的路线。因此我们可以用旅行商问题的解法来找到基因的排列顺序。

用上面的技术，美国国立卫生研究院（National Institutes of Health）的研究小组构建了包括人、恒河猴、马、狗、猫等很多物种的基因组图谱。

看到这里，你应该能够立刻感受到数学的威力了。很多看似完全不同的实际应用问题，如果你把它进行抽象，就会发现它们本质上都对应着同一个数学问题。解决了这个数学问题，也就解决了这些应用问题。

通过上面的例子，我们知道了为什么旅行商问题被数学家关注的第一个原因：实际应用的价值很大。然而，对于数学家而言，旅行商问题的意义绝不仅仅局限于实际应用中的价值。旅行商问题，代表了计算数学、计算机科学中的一个极其重要的问题，这就是P是否等于NP。

我们进入下一节，P等于NP吗？这个表述如果你感觉有点困惑，没关系，我们在后面会展开解释。

P等于NP吗？

前两年国内有一部热播的电视剧《天才基本法》，它反复提到了“P=NP”问题。这可是一个计算数学领域天大的难题，它耗费了无数科学家的大量时间和精力，迄今也未能解决。这个问题的重要性好比物理学中的大统一理论、数学中的哥德巴赫猜想，是皇冠上的明珠，是无数科学家梦寐以求的目标。毫不客气地说，如果有人能够解决这个问题，那么这个人将一举成名，同时这个成就也将是数学界近百年最伟大的发现。

旅行商问题，就和P=NP问题相关。

我们回到宝洁公司悬赏的这33个城市的最短路线问题。先说一个好消息，早在1954年，美国加州的兰德公司的三位数学家，乔治·丹齐格（George Dantzig）、雷·富尔克森（Ray Fulkerson），以及塞尔默·约翰逊（Selmer Johnson），提出了一个基于线性规划的方法，通过手工计算，用了几星期时间就得到了环游美国48座城市的最短路线。

很显然，这三位数学家解决的这个48个城市的路线问题，比宝洁公司的33个城市的路线问题难得多，所以宝洁公司的这个问题其实已经被解决了。

不过先别高兴得太早，尽管这三位数学家解决了环游美国48个城市的难题，但是我们不能说旅行商问题已经被解决了。

关键在于问题的规模。如果城市的数量再大一些，这些数学家提出的算法所需要的时间，可能又将是一个天文数字。也就是说，针对更多城市的旅行商问题，这些数学家并没有找到通用的，足够好的算法。

你看到这里，肯定脑子里有一个疑问：什么叫做“好”的算法？

直觉上，好的算法就是能够在比较短的时间内找到问题答案的算法。

但是要知道，绝大多数情况下，算法找到问题答案的时间，都会和问题的规模有关系。

对于旅行商问题而言，找到48个城市的最短路线，显然要比33个城市的难度高得多，因此哪怕我们再苛刻，也不能要求一个算法对于任意不同规模的旅行商问题，都能在某个固定时间（比如一分钟）内找到答案。

所以我们一定得允许在城市数量增加时，算法的求解时间相应增加。

好算法和坏算法的关键，就在于增加的快慢。好的算法，这个求解时间随着城市数量增加不能太快。

那么什么叫快，什么叫慢呢？

数学家有一个定义，只要一个算法找到答案所需要的时间，能做到n^k可以了。这里的n就是问题的规模。

对于旅行商问题，n就是城市的数量。指数k可以是任意值，例如取2、3或者更大的数，但必须是固定的，不能随着n的增加而增加。例如，如果算法的时间是n^3，那么这个算法就是好的。

n^k 是n的多项式，因此满足这个条件的算法，叫做多项式时间算法。多项式时间算法是一个好算法。

如果一个算法所需要的时间和规模的关系是k^n ，例如2^n、3^n等这样的指数函数形式，那么这些算法是一个“坏”的算法。当然，比指数函数更慢的，还包括之前提到的n的阶乘，阶乘级的算法也不是好算法。

我们举个例子来说明一下好算法和坏算法的差距。假设一个算法是多项式时间算法，所需要的时间和规模的关系是n^3，另外一个算法是指数时间算法，关系是2^n。为了看得更清楚，我们拿一台每秒钟能够进行109 次计算的计算机，看看这个计算机运行这两个算法所花费的具体时间的差别。

当n小于10的时候，指数时间算法所需要的时间更短，但当n超过10以后，指数时间算法花费的时间就会超过多项式时间算法，并且随着n的增大，这个差距越大。

具体来说，当n=25时，第一个算法需要0.02毫秒，而第二个算法则需要0.03秒。这个还差距不大。

当问题规模n到了50的时候，多项式时间算法所需要的时间增加到了0.1毫秒，增加得不多。但指数时间算法的时间，从0.03秒，一下子达到了13天。

而如果n增加到100的时候，多项式时间算法的耗时增加到了1毫秒，但是指数时间算法增加到了40万亿年。

这就是为什么指数时间算法被称为“坏的算法”，因为当问题规模比较大的时候，算法需要的时间就变得不可接受了。

因而，在计算机算法领域，我们有一个最基本的假设：所有实用的、快速的、高效的算法，所需要的计算量，和问题规模的关系，都应该是多项式级别的。

你可能会问，如果n比较小，那么指数时间算法的耗时，可能会比多项式时间算法更短啊。没错，但是计算机的发明就是为了处理大规模数据的。所以科学家在比较算法快慢的时候，就是比较在问题规模比较大的时候的表现。

算法可以明确地分为好算法和坏算法的这种思想，彻底改变了计算数学。从此大家都有了明确的目标，为了一个问题找到好的算法，并且不断提高算法效率。

然而，对于旅行商问题，尽管数学家们一直在前赴后继地改进算法效率，但是一直没能找到多项式时间的算法。于是，很多数学家就产生了一个想法：是不是旅行商问题，从理论上就不存在好的算法呢？

当时的几个数学家也说过这样的话：

比如，杰克·埃德蒙兹在1967年说：“依我猜想，旅行商问题没有好的算法。”

梅里尔·弗拉德在1956年说：“要想成功解决该问题，很可能需要另辟蹊径，使用前所未有的新方法。事实上，该问题的通用解法很可能压根不存在，若能证实这个结论也是很有价值的。”

理查德·卡普在1972年说：“我们在本文中给出了一些定理。它们有力地显示（尽管不足以证明）：该问题像许多别的问题一样，也将是一道永恒的难题。”

我们可以看出，数学家们在思考问题时的思路和角度，和普通人是不同的。

为了看清这一点，我先来问你一个问题。当你拿到一道数学题的时候，你应该干什么？

多数人会认为：当然应该着手找这个问题的解法。

而对于这个问题的难度，我们大部分人是不会主动去研究的。因为在我们眼中，问题到底难不难和你有没有找到好的解法有着密切关系。也就是我们常听说的这句话：难者不会，会者不难。

而数学家的反应可能会出乎你的意料。他们拿到一道题之后，不是首先去找这个问题的解法，而是首先会去研究一下这个问题本身的难度。而且“难者不会，会者不难”在他们眼中是不成立的，问题的难度和解决方法没有直接关系。

举个很形象的例子。你毕业去了一家高科技公司，上级丢给你一个和企业生产相关的数学问题，找你要这个问题的解法。你研究了几天，也找不到一个好的解法，然后你只能愁眉苦脸地对上级说，这个问题你没找到答案。

但如果上级把这个问题丢给一个数学家，虽然最后他也没能找到这个问题的解法，但是与你不同的是，他会拿着一堆数学证明，理直气壮地去和上级说：“领导，虽然我没能做出这道题，但是这不是我的问题。因为我从理论上证明了，这个问题本质太难了，不光我做不出来，世界上任何人都做不出来。”

这就是理论的价值。

所以，数学家们对问题本身的难度感兴趣。他们想知道，哪些问题从理论上存在好的算法，哪些问题从理论上就不存在好的算法。

数学家们，把理论上存在好算法的问题叫做P问题。这里的P是多项式时间（polynomial-time）的意思，也就是我们可以找到一个算法，它解决该问题的时间是问题规模的多项式函数，也就是前面提到的nk的含义。

什么样的问题存在好的算法呢？

排序问题就有好的算法。排序就是把一组数按照从大到小顺序排列。对于一个长度为n的数组，数学家们已经证明了，最快的排序算法所需要的时间，是n×log n。这是一个多项式时间的算法。

我们平常在打牌的时候通常会一边抓牌一边按照大小把牌的顺序排好。绝大部分人都不会觉得这是一个难题。这是因为排序问题的本质很简单。

除了排序问题，还有很多问题，包括在序列中查找某个数、判断一个数是否为质数等问题都属于P问题。我们能够用多项式时间算法来解决这些问题，因此当这些问题的规模增大的时候，这些算法的耗时不会出现爆炸式增长。

但是对于我们刚才的旅行商问题，是否属于P问题呢？

很遗憾，我们不知道答案。

不知道答案的意思是，有可能属于P问题，也有可能不属于P问题。

为此，科学家们发明了一个词，叫做NP问题。这里的NP，不是非多项式（not polynomial），而是非确定性多项式（non-deterministic polynomial），也就是这些问题，我们“不确定是否能用多项式时间解决”。

NP问题有两个特点，第一就是找到答案很难，换句话说，我们还没能找到一个多项式时间解决该问题的算法。

NP问题的第二个特点是，问题的验证比较容易。关于这一点会涉及一些数学概念，我们不深入介绍。拿旅行商问题来说，虽然让我们找一条长度短于100英里的路线不容易，但是只要别人给我们一条路径，我们就可以很快地验证它是否满足这个要求。

这个给我们带来了一点希望，因为如果连验证答案都很难，那么我们可以想象，在多项式时间内找到这个问题的解，就非常渺茫了。

通俗地来说，解决很难但验证很快的问题就是NP问题，旅行商问题就是NP问题。而且数学家们已经提出了一些严格的方法，可以从理论上证明某些问题属于NP问题。

看到这里，你应该可以意识到关键所在了：NP问题，有没有可能和P问题是同一类问题？这就是P是否等于NP。

P是否等于NP，换句话来说，就是是否“所有可以轻松验证的问题也可以轻松解决”？

支持P=NP的科学家，认为存在某一种方法，可以将NP问题转化为P问题，只是我们现在暂时还没有找到这个方法。而持相反态度的科学家认为，NP问题和P问题不是一类问题，我们永远无法在多项式时间内解决NP问题。

假设P=NP是真的，那么我们首先要注意的，就是当前的加密系统。因为加密系统的核心原理，就是把一个很大的整数分解成为两个质数的乘积。这个问题是NP问题，迄今没有效率很高的解法。但如果P=NP，这意味着存在高效的算法进行质因数分解，意味着现有加密体系从本质上已经不安全了。

当然，P=NP可能给我们带来更多的好处。规模再大的旅行商问题都能很快找到最短的路线，工厂能达到最大的生产能力，航班也能安排得当、避免延误，因为这些资源分配问题、规划问题大部分都是NP问题。由此科学界、经济界、工程界将会出现更加强大的工具和方法，重大突破源源不断。

当前的大部分科学家认为P不等于NP，但是也没有人能用理论证明这一点。美国计算机科学家、1985年图灵奖获得者理查德·卡普（Richard Karp）也认为P不等于NP。他说：“我认为传统的证明方法是远远不够的，解决这个问题需要一种绝对新奇的手段。直觉告诉我，这个问题最终会由一位不被传统思想束缚的年轻科学家解决掉。”

尽管这个问题还没能解决，但是数学家们前赴后继地在旅行商问题上投入，也提出了很多算法。很多在旅行商问题上的算法，对运筹学和优化理论产生了深远的影响。我们将进入下一节，旅行商问题的解法。

旅行商问题的解法

解决旅行商问题的解法有几类。我们首先说说精确解法。精确解法能够保证找到旅行商问题的最优的路线，但是很显然，这些算法都不是多项式时间的。

能够解决旅行商问题的一类经典算法，被称为线性规划方法（linear programming）。

还记得我们之前提到过解决48个城市的旅行商问题的兰德公司的三位数学家嘛？这三位数学家之一，乔治·丹齐格（George Dantzig），被誉为线性规划之父。

线性规划，不仅可以用来解决旅行商问题，而且是解决一类数学问题的通用方法。数学家们解决一个实际问题的思路，和我们小时候做应用题有点像。对于一个实际问题，数学家们首先会对该问题建模，也就是把该问题抽象成一个数学模型，然后就可以脱离开实际问题，围绕该数学模型，通过数学工具，找到最后问题的答案。

丹齐格提出线性规划，针对的是一类特殊的数学模型。这个模型是要找到一组变量的最优值，在满足一些规定条件的约束下，让某一个目标函数取最大值或最小值。特别注意的是，这个约束条件和目标函数，都是关于变量的线性函数。这就是“线性规划”的由来。

针对线性规划模型，丹齐格在1947年提出了单纯形法（Simplex algorithm），单纯形法标志着线性规划理论的正式建立和广泛应用。

丹齐格有一个精彩的故事，这个故事后来被好莱坞改编成了电影《心灵捕手》。1939年，年轻的丹齐格在美国加州大学伯克利分校读研究生一年级。有一天，他上课迟到了，这门课的授课教师是杰尔日·内曼（Jerzy Neyman）。内曼教授当时在黑板上写了两道统计学领域著名的未解难题。丹齐格进了教室，看到这两道题目，以为是课后作业，便匆匆忙忙抄下来。过了一段时间，丹齐格把自己的解答交了上去，让内曼大吃一惊。最后这两道“作业题”的解答，成为丹齐格博士毕业论文的主要内容。

丹齐格从伯克利毕业时正值二战。二战期间，他在美国空军研究规划问题，也就是如何快速地计算兵力部署、人员训练、后勤补给等方案。

战争结束时，丹齐格在美国国防部工作，开始针对如何实现军队规划流程的自动化展开研究，由此在1947年创立了线性规划，并提出了解决线性规划模型的单纯形法。

书中还讲了这样一个故事。虽然现在看来单纯形法已经成为解决线性规划模型的基础方法，但是回到当年，丹齐格在提出了这个方法之后，自己并不那么自信。1948年，在威斯康星大学的一场会议上，丹齐格公开了通用线性规划模型及其求解所用的单纯形法。但在一大群德高望重的数学家和经济学家面前，他只是个年轻后生，因此内心忐忑不安。在报告后的讨论环节，哈罗德·霍特林（Harold Hotelling），当时已经是数学界成名已久的重量级人物，站起身来，只说了一句话：“可我们都知道世界不是线性的。”面对这么狠的批评，丹齐格一下子无言以对。

突然听众中又有一人举起了手，那是著名的冯·诺依曼（John von Neumann）。他说：“主席，主席，如果报告者不介意的话，我愿意替他回答。”丹齐格当然求之不得。冯·诺依曼接着说：“报告者把题目定为‘线性规划’，陈述原理的时候也很谨慎。你的应用要是满足他的原理，那就用他的模型；要是不满足，那就不用呗。”

丹齐格在往后的几十年里，对这个故事津津乐道。据丹齐格在斯坦福大学的同事表示，他在自己办公室外面挂了一幅漫画，配图文字写道：“幸福就是假设世界是线性的。”

线性规划在工业界用途极广，令人惊叹，你说得上来的任何部门几乎都有它的用武之地。显然，通过线性规划安排生产，每天能节省数不清的自然资源。线性规划还能省钱，《纽约时报》就曾专门针对线性规划发表过文章，“解决工业上的线性规划问题，是涉及每年上百亿美元的大事业”。

回到旅行商问题，这个问题是线性规划中的一个特殊分支：整数规划。因此解决整数规划的方法基本上都可以用于解决旅行商问题。如何找到效率更高的旅行商问题的算法，是众多研究者一个明确的目标。在这条“没有最快，只有更快”的道路上，包括本书的作者在内的科学家开始了竞赛。从动态规划算法，到割平面法、分支定界法，各种算法被不断提出。

尽管我们知道，这些算法都不是多项式时间算法，但是在很多问题中，它们已经表现得很好，因此在各个领域中都得到了广泛地应用。

除了精确解法之外，数学家们还有另外一种思路：抛开必须找到绝对最优解的念头，转而关注如何尽快求一个还不错的解。放弃最优解带来的好处是可以让计算速度大大加快，让多项式时间的算法成为可能。

在这条道路上，最早期的算法，叫做启发式算法。所谓的启发式，是靠人类的经验总结出来算法的规则。

例如，在从头开始构建旅行商的路线时，最容易想到的方法就是每次都在没有到过的城市中选择最近的一个。这种算法称为最近邻算法（nearest-neighbor algorithm），这个算法得到的路线虽然通常不是最短的，但是速度非常快。

除了启发式算法之外，还有一类算法，叫做元启发式算法（metaheuristic），即用来设计启发式算法的启发式算法。

元启发式算法的代表包括爬山法、模拟退火算法、遗传算法、蚁群算法等。我们在解读《心中有数》的一文里，提到了模拟退火算法。在这里我们来介绍一下遗传算法。

遗传算法是从生物角度出发，把路线当成能够逐渐变异和进化的生命有机体。遗传算法解决旅行商问题的思路大致如下。首先形成路线的初始“种群”，可以通过反复从随机城市出发使用最近邻算法获取大量的可能路线。然后在种群中选取若干对比较好的路线，让它们“交配”“变异”（即综合这些路线），得到一批子代路线，再从中选出比较好的子代路线中重复之前的步骤，最后最优秀的路线最终将脱颖而出，成为唯一的生存赢家。

总结

最后，我对这本书做一个总结。

这本《迷茫的旅行商》的作者库克教授是一名在运筹学、组合优化领域的科学家，从这本他科研领域的科普书中，我们不仅能够看到针对一个问题，一代代的科学家不断求索的历史，听到了各种有趣的故事，更让我们对于数学家解决问题的思路有了更深的认识。他们总是通过一些假设（尽管有时候假设不尽合理），把实际问题抽象成数学问题，他们会把问题本身和问题的解决方法分开，以及他们总是在前人的基础上不断提高等等。

当然，因为篇幅原因，书中还有大量的例子，感兴趣的朋友，也推荐你去亲自翻开这本书，你会感受到更多数学家的思维和有趣的故事。

你还可能感兴趣的是，现在旅行商问题发展得怎么样了？要说近十年来科学界的最大进步，恐怕大家都会投票给人工智能。没错，人工智能现在已经渗透到了多个科学研究领域里，包括以旅行商为代表的运筹学领域。研究人员开始利用深度学习、强化学习等人工智能技术来解决旅行商问题，并且已经取得了很多突破。我们期待着在不久的将来，能够看到更多在算法和理论上的进展，我们也相信这些进展可以更深层次地改变我们的生活和工作方式。

好，今天这本《迷茫的旅行商》，我们就讲到这里。恭喜你，又听完了一本书！

划重点

1、旅行商问题不是一个简单的路线规划问题,而是一个无处不在的计算机算法问题,涉及众多实际应用领域。

2、P问题不是指容易解决的问题,而是存在多项式时间算法的问题,NP问题是不确定是否存在多项式时间算法的问题。

3、数学家解决问题不是直接寻找答案,而是先研究问题本身的难度,探索问题的理论属性。