传播数学干货，学会理性的方式去思考问题

我十几岁的儿子的课后工作是给 148 个家庭送报纸。 当我和他一起去送报纸时，我们会反复停车，步行到每家每户，然后回到车上。 这时候一个自然的问题是，如何选择一条让我们步行距离尽可能短的路线？

从一个角度来看，这是一项非常简单的任务：路线的数量是有限的，因此我们可以列出所有可能的路线并搜索其中最短的路线。 然而，当我们开始列出所有路线时，我们发现结果是一个巨大的数字：准确地说是 148 的阶乘。

148！ =

=2.5×10258。

这看起来是一个很大的数字。 今天的计算机每秒可以执行大约十亿次操作，而宇宙已经存在了大约 1,017 秒。 如果我们从宇宙之初就开始研究这些路线，我们只能研究大约 1,026 种可能性。 当然，报纸读者不会有耐心等待我们以这种方式找到解决办法。

考虑另一个类似的问题。

以下是我在密歇根州最喜欢的十个地方：

如果我们想找到访问这 10 个地方的最短路线，我们需要检查 10 种阶乘（即 1×2×3×4×…×9×10）的可能性。 这将导致超过 360 万种可能性找到这条最短路线。

上述问题的关键在于，即使要访问少量站点，不同组合中可能的路线数量也非常多。 直接列出所有可能性，计算最短路径将是相当昂贵的，并且在大多数情况下非常不现实。

1. 旅游供应商问题

上一节的例子都是旅行商问题（简称旅行商问题）的典型例子。 在这两种情况下，我们都希望使用总距离最小的路线来访问一些给定的站点。 更一般的情况是，我们希望选择一条最优路线，使我们关心的某些量（例如路线、距离成本等）最小化。

在上一节中，我们描述了一种通过考虑所有可能性来找到最佳路线的方法。 但这种方法涉及的可能性太多，计算量巨大，连超级计算机都无法承受。 另一方面，我们直觉地认为一定有更好的方法。 我和我的儿子发现了一个更好的方法。

事实上，对于一般的旅行商问题，数学家们一直没能找到找到最优路线的通用方法。 一般来说，这是一个很难解决的问题。 在本文中，我们将简要探讨旅行推销员这个有趣的问题，并描述一个新的结果。

阅读完上述两个示例后，您可能会开始寻找您周围的旅行商问题的示例。 例如，您将如何安排您的一天：上班、去杂货店、接孩子放学、去咖啡店。 可以想象，邮政公司，比如快递公司，在安排日常的包裹收寄时，会面临最短路线的问题。 在美国总统选举期间，候选人前往多个州参加政治竞选活动。 当他们在爱荷华州竞选时，竞选团队总是试图最小化成本并最大化候选人的曝光度。

库克的优秀新书《In of the》描述了旅行推销员问题的许多例子，该问题源于一名旅行推销员访问多个城市销售一家公司的产品。 此外，他还讲解了许多最新的应用，包括制定有效使用望远镜的时间表、研究基因图谱的新方法等。

又如，在一些数字电路板的生产中，会钻数千个孔，以便将电阻器和集成电路等电子元件嵌入其中。 钻这些孔的机器必须尽可能高效地访问电路板上的每个相应位置。 如何选择最佳路线是旅行推销员的另一个问题。

显然本文讨论的问题是普遍存在的，我们希望有一个好的解决方案。

2. 好到什么程度才算好？

本文第一节说，n 个节点的所有可能路由有 n 个阶乘，即

n!=n×(n-1)×(n-2)×…×3×2×1。

即使对于适当的 n，这也是一个难以处理的大数字。 向 148 户家庭递送报纸的路线堪称天文数字。 当考虑到电子电路板上的数千个孔时，这个问题变得更加困难。

数学家开发了一种评估问题难度的方法，即解决该问题的算法的复杂性。 一般来说，复杂性是一种衡量解决目标问题所需工作量的工具，作为给定数字（我们将这个数字称为 n）的函数。 比如我们之前讲的解决报纸投递路线的暴力算法的复杂度通常记为O(n!)，即我们粗略地认为它与n!成正比。

我们再举一个例子。 您想要在电话簿中查找号码。 一种方法是搜索整个电话簿，一次一个条目，直到找到您想要的内容。 这里的工作量与电话簿中的条目数 n 成正比，因此我们说该算法的复杂度为 O(n)。 如果电话簿的大小加倍，那么我们可能需要做两倍的工作。

当然，存在一种更好的算法来查找电话号码，即二分搜索算法或简称二分搜索。 如果电话簿是按姓氏笔划排序的，您可以在电话簿中间打开它，确定要查找的条目的姓氏笔画是在其之前还是之后。 比如上半部分，打开上半部分的中间，判断你的目标项是在上半部分还是下半部分。 下半场也是如此。 然后重复。 这里所需的工作量为 O(log(n))，大致与 n 的以 2 为底的对数成正比。 在这种情况下，如果电话簿的大小增加了一倍，您只需再执行一步即可。 显然这是一个更好的算法。

请注意，这种复杂性度量与解决问题的算法有关，而不是与问题本身有关。

考虑裤子和衬衫的另一个问题。 假设你有 n 条裤子和衬衫，当你早上穿衣服时，你想要考虑所有可能的组合。 由于总共有 n2 种组合，因此所需的工作量为 O(n2)。 如果 n 加倍，我们需要做大约四倍的工作。

我们现在定义一个非常重要的问题类，称为P类。 如果有一个 O(nk) 算法来解决一个问题，其中 k 是某个整数，那么该问题属于 P 类。这里的 P 代表“多项式”，运行该算法所需的工作量与某个多项式成正比名词

我们通常将 P 型问题视为“简单”问题，即使相应的指数 k 是一个非常大的数。 旅行商问题的暴力算法的复杂度是 O(n!)。 如果我们将 n 加 1，我们需要做 n 倍的工作。 这种工作量的增加是非常可怕的。

到目前为止，我们还不知道旅行商问题是否属于P类。换句话说，没有已知的算法可以解决具有多项式复杂度的一般旅行商问题。 但这并不意味着明天就不会有人找到如此出色的算法。

另一类问题称为 NP：如果可以使用多项式时间算法验证可能的解决方案，则问题是 NP。 换句话说，解验证算法是 O(nk)，其中 k 是某个整数。

一般来说，验证可能的解决方案比找到它更容易。 例如，找到质因数是一个具有挑战性的问题，而验证乘法是否相等则相对容易。 我们可以验证P∈NP。 换句话说，如果我们可以在多项式时间内给出问题的解决方案，那么我们就可以验证我们在多项式时间内有一个解决方案。

令人惊讶的是，我们不知道旅行商问题是否属于 NP 问题！ 考虑欧几里德旅行供应商的特殊情况：在这种情况下，站点取自欧几里德空间，访问站点的成本是欧几里德距离。 如果我们固定一个常数k，我们就可以询问一条路线的距离是否小于k。 这看起来是一个简单的问题，回答它需要计算一些平方根，但没有已知的多项式时间算法来确定一些平方根的总和是否小于 k！

鉴于此，这吸引我们去思考非常特殊的P型问题，事实上，我们不知道不属于P型的问题。在已知的问题中，我们不知道任何属于NP的问题类但不属于P类。 因此，人们自然会问是否P=NP？ 这是数学中一个重要的数学难题，是克莱数学研究所设立的六百万美元难题之一。

最后一类问题是 NP 完全问题：如果 NP 中的任何问题可以在多项式时间内简化为该 NP 完全问题，则该问题属于此类。 虽然我们不知道旅行商问题是否是NP问题，但引人注目的是它确实是一个NP完全问题。 因此，如果你能找到旅行商问题的多项式时间算法，那么我们就会知道 P = NP。 反过来，您将收到 100 万美元。

在 2002 年进行的一项调查中，比尔询问一组专家是否相信 P=NP。 61 人认为这是不正确的，只有 9 人认为这是正确的。 此外，大多数人认为真相还需要很长时间才能揭晓，而问题的彻底解决需要全新的思维。 您可以在此处查看调查结果。

人们很容易相信 P 不等于 NP：我们的经验是，测试可能的解决方案通常比找到解决方案容易得多。 由于算法研究的历史较短，因此有理由相信，随着该领域的成熟，我们将发现一些基本的新技术，这些技术可能证明这些任务需要同样多的努力。

3. 我们所知道的

看来旅行商问题是一个难题，尽管我们还不能 100% 确定。 更糟糕的是，答案可能很长时间都不会揭晓。 与此同时，我们能做些什么来解决这个问题呢？

除了 O(n!) 蛮力算法外，我们目前最好的算法是 Held 和 Karp 在 1962 年发现的 O(n2×2n) 算法。注意，它的复杂度是指数级的而不是多项式的，并且这个结果还没有被证实。过去50年有所改善。

然而，人们不断提出新的方法来克服旅行供应商问题，这也促使人们继续基于更大的站点集寻找最佳路线。 1954年，使用线性规划方法找到了所有48个州和哥伦比亚特区的所有主要城市的最短路线。 此后，在3038个城市（1992年）、13509个城市（1998年）和85900个城市（2006年）中找到了最佳路线。 这些计算中使用的一些计算机代码称为 ，它是免费提供的。

一个令人惊奇的例子是，旅行商问题的 100,000 个站点中的几乎最优路线可以用来重建达芬奇的《蒙娜丽莎》。

请记住，一般旅行供应商问题是根据不同站点之间旅行成本的衡量标准来定义的。 一般的旅行商问题很难解决，但对于某些特殊情况可能存在好的算法。 例如，欧几里得旅行商问题也被认为是NP完全问题。 现在我们来看看欧几里得旅行商问题的结果，希望它能更清楚地显示 P=NP 问题。

4.多项式时间近似方案

如果一项工作太难完成，我们会寻求近似的方法。 也就是说，如果我们无法找到旅行商问题的绝对最短路径，也许我们可以找到一条不超过最短路径的 10% 或 5% 的路径。

1976年，人们发现了一种多项式时间算法，可以用来生成不超过最佳路线50%的路线。 然而，延伸的问题是：如果我们修复错误，我们能否找到一条路线，使其长度与最短路线之间的差异在给定的误差范围内。

20 世纪 90 年代，Arora 独立发现了一种算法，可以在多项式时间内给出欧几里得旅行商问题的近似解。 Arora发现了这样一个算法：对于给定的C>1，可以找到一条长度不超过最短路径的1+1/C倍的路径。 我们将描述他的算法的复杂性的随机形式。

Arora的算法应用了动态规划中一种称为四叉树（）的数据结构。 首先，考虑欧几里得旅行供应商问题中我们想要访问的站点并将它们放置在网格中。

现在，让我们关注这个正方形，并将其分为四个正方形。

继续这个过程将产生一个四叉树，其中树中的每个点都是一个正方形，每个内部点都有四个子节点。 树的根是一个内部正方形。

现在我们可以开始描述 Arora 的算法，用于寻找旅行商问题的近似解。 我们固定数字C，寻找一条长度不超过最优路径1+1/C倍的路径。 例如，给定C=10，那么我们将找到一条长度不超过最优路径长度10%的路径。

我们将构造一棵四叉树，使得每个叶子仅包含旅行商问题中的一个位置。 如果两个位置非常接近，我们的树将需要向下到相对较深的树来找到分隔两个点的正方形。 为了避免这个麻烦，我们将稍微扰乱这些点：如果原来的大方形网格的边长为L，那么我们将构造一个宽度为L/(8nc)的网格，并将每个位置向上移动到其最近的网格点。

虽然两个站点可能会移动到同一个网格点，但我们将确保两个站点之间的距离至少为L/(8nc)。 现在，我们通过划分其中包含多个点的格来构造一棵四叉树。 我们观察两点：假设OPT是最优路径的长度。 由于 L 是初始盒子的边长，因此我们有 OPT/C。 另外，请注意，每个点移动的距离小于 L/(8nc)，这意味着每条路线的总长度最多将改变 2n×L/(8nc)。 由于我们正在寻找一条长度不超过 OPT/C 的最短路线长度的路线，因此这是可以接受的扰动。

虽然两个站点可能会移动到同一个网格点，但我们将确保两个站点之间的距离至少为L/(8nc)。 现在，我们通过划分其中包含多个点的格来构造一棵四叉树。

由于我们的扰动，四叉树的深度现在为 O(log n)，因此四叉树中的方格数为 T= O(n log n)。

我们可以通过缩放平面来假设该站点具有积分坐标。 这不会影响路线的相对长度，我们可以稍后恢复。

下面我们描述了一种动态规划算法来找到旅行商问题的近似解。 在每个方格中，我们将限制路线上的那些点进入该方格。 最后，我们在区间[C log L, 2C log L]中选择一个整数m，它是2的幂。在每个方格的边缘上，我们均匀地放置m+1个间隔的点，称为gates()。

引入门概念的动机是我们只需要检查进入正方形的路线上相对较少的位置。 而且门越多，我们的路线就越接近最优路线。

由于 m 是 2 的幂，因此内部点的门也是由它生成的每个子节点的门。

我们现在考虑一个多路径问题，该问题由每个方格上的一组门 a1、a2、a3...、a2p 组成。 我们将找到一组最短路径：连接 a1 到 a2、a3 到 a4 等，并访问网格内的每个 TSP 站点。

对于叶点来说，这是一个相对简单的问题：我们列出所有可能的路径并找到其中最短的路径。 对于上述问题，只有以下两种可能和最短路径的集合。 多路径问题的解决方案如右图所示。 对于每个门集 a1、a2、a3...、a2p，我们保留该解决方案的记录。

对于内部点，我们有一个像这样的多路径问题：

假设我们已经解决了所有可能的子节点的多路径问题。 此时，为了解决内部点的多路径问题，我们考虑内部边缘上可能产生多路径子节点的每个门的选择。

现在我们找到子点多路径问题的解决方案来构造到父点的多路径。

这样，我们只需要搜索内部边缘上所有可能的门选择，就可以找到父点多路径问题的解决方案。

我们沿着树搜索直到到达根部，当边界上没有门时，我们就解决了多路径问题。 这给出了一条路线，该路线给出了旅行商问题的近似解决方案。

为了估计运行该算法所需的计算量，我们需要记住四叉树中有 T = O(n log n) 个正方形。 稍微小心一点，我们可以枚举我们想要解决多路径问题的门的选择，这将给出 Arora 算法复杂度的估计 O(n(log n) o(c))。

我们找到的路线可能有一些交叉点，但是我们可以在不增加路线长度的情况下消除这些交叉点。

不幸的是，上述算法可能无法找到与给定精度的旅行商问题的解不同的路线。 例如，当路由在四叉树中多次相交时，就会发生这种情况。

因此，Arora 引入了变换四叉树，在需要的时候对四叉树中的方格进行变换，让它们有一定的环绕效果，如下图所示。

Arora 分析了这些变换对算法生成的路线与网格边缘之间的交叉点数量的影响。 该分析表明，如果随机选择转移，算法找到长度小于 (1+1/C) OPT 的路线的概率至少为 1/2。

为了确保我们得到一条在误差范围内的路线，我们可以尝试每一种可能的变换，只取相应路线中最短的。 假设站点有积分坐标，我们只需要考虑L2变换，这会增加运行时间L2 = O(n2)的倍数，因此算法仍然可以在多项式时间内完成。

5. 总结

由于Arora算法的执行效率不是特别高，因此我们应该将这一结果主要视为理论结果。

前面提到的欧几里得旅行卖家问题是NP完全的，这意味着如果可以找到一个多项式时间算法来解决欧几里得旅行卖家问题，那么P = NP。 Arora的结果并没有证明这个结论，但它告诉我们可以使用多项式时间算法以任何所需的精度来近似最佳路线。 问题在于，要求的准确度越高，相应的工作量就越大。

为了表彰 Arora 及其对此问题的重要贡献，2010 年计算机协会授予他们戈德尔奖。

通过：大卫，大州

翻译：石永堂博士，南开大学数学学院副教授

校对：唐涛，香港浸会大学数学讲座教授