从“退火技术”中，彻底理解计算机科学中最大的谜题—P与NP问题

在计算机科学中，有一个非常有趣的问题。

让我们想象一下这样一个情景。你是一名邮递员，得到了一个需要递送邮件的房子列表。路想象你是一个负责投递邮件的邮递员，有一个包含多个房子的递送名单。你需要决定递送邮件的顺序和路线。任务完成后，你可以回家休息。为了尽快完成工作并回家，你要找出一条最快的递送路线。在这个假设中，我们认为房子之间没有任何障碍，所以你可以直接从一个房子走到另一个。这个场景实际上是在引入一个关于最优路线规划的问题，这是一种常见的需要在多个地点之间找出最高效路径的优化问题。下面是一个例子。

• 30个房子的示例场景

在上面的图片中，房子以红点显示。蓝线显示了它们之间的潜在路径。尽管场景的陈述很简单，但实际上这是一个非常难以解决的问题。我在这里描述的是计算机科学中最古老、最有趣的问题之一，称为旅行推销员问题（Travelling Salesman Problem）。它可以这样陈述：

给定一个城市列表及其位置，访问每个城市恰好一次并返回起点的最短路线是什么？

在处理类似邮递员路线规划的问题时，可以利用图论这一数学分支的知识。在图论中，每个需要投递邮件的房子可以被视作一个顶点，而连接这些房子的路径则被视作边。这些边可以根据路径的长度进行加权。即使你之前不了解图论，也无需担心，因为相关的基础知识和概念会在后续进行详细解释，以便于理解如何运用图论来寻找最优路线。

在这篇文章中，我将介绍一些关于旅行推销员问题的历史。我们将讨论为什么它如此困难，以及解决它的一些不同方法。它被证明是一个很好的NP问题示例。旅行推销员问题最终与计算机科学中最重要的问题非常相关。

这个问题最早的已知提及出现在1832年出版的一本供旅行推销员使用的手册中。然而，该手册并没有讨论背后的数学原理。这类涉及优化路径的问题因其在日常生活中的实用性而可能已经被人们在过去千年间以某种间接方式处理过，尽管当时缺乏系统的数学理论来支持。到了20世纪初，随着汽车变得普遍，寻找最优路径变得更为重要。这促使数学家们开始开发简单的算法来在一系列给定点之间寻找最短路径，这是出于实际应用的需要。但是，在开发这些算法的过程中，他们很快就遇到了难题，显示出这个问题的复杂性和对更深入数学理论的需求。

让我们来谈谈为什么这个问题如此困难。举个例子，如果有五个房子，要确定访问这些房子的所有可能路径，我们需要计算5的阶乘，也就是5×4×3×2×1，总共有120种不同的访问顺序。虽然120种路线看起来很多，但对于现代电脑来说，检查这些路线在一秒钟内是可以做到的。

那么有30个房呢？这意味着有30的阶乘种可能的路线。这个数字是惊人的2.6 x 10^32。即使从宇宙开始就已经运行，今天存在的任何计算机也无法检查每一条路线。而且对于这个问题，30通常来说是一个相对较小的数字。想要在数千个不同点之间最小化路线的问题并不罕见。显然，我们需要一种比暴力计算更聪明的方法。

从自然中汲取灵感

为了在合理的时间内解决旅行推销员问题，数学家们尝试了各种各样的方法。其中一些直接从自然过程中获得灵感。

解决这个问题的最常见方法之一被称为退火（annealing）。它的名字来源于铁匠用来处理金属的技术。为了使金属更易于改变形状，铁匠会将其加热，如上图所示。当金属处于这种状态时，其中的原子可以自由移动。这使它们能够找到更合适的排列方式，从而改变金属的性质。随着金属冷却，原子的运动速度减慢，最终固定在这种新的排列中。

退火的关键方面涉及到所谓的局部最小值（local minima）。在材料的退火过程中，原子的移动和重新排列是至关重要的。原子排列的方式会影响材料的物理特性，如电荷分布。为了达到更优的属性，原子需要从一种排列状态转移到另一种。这种转移需要足够的能量，否则原子会保持在它们当前的排列状态。当材料被加热时，原子获得额外能量，使它们能够经过一个非最优的中间排列状态，最终转移到更理想的排列。这个过程中，原子最初可能进入到看似不理想的排列，但随着时间的推移，这些排列会发展成更加有序和理想的结构。

• 旅行推销员问题有时会像右边这样陷入局部最小值

让我们将这个应用到我们的问题上。在上图中，想象y轴代表在房子之间的给定路径上旅行所需的时间。x轴告诉我们可能的路径。我们希望找到一个y轴尽可能小的解决方案。然而，如果我们当前的解决方案陷入右侧的小凹槽，那么算法可能就会卡在那里。为了到达左侧那个最好的解决方案，首先需要经过一些较差的解决方案。我们如何让算法实现这一点呢？

我们通过借鉴退火的一些概念来实现这一点。模拟退火算法通过模仿金属退火过程来解决优化问题。算法从随机选择的路径开始，这个路径是潜在解决方案的一种，并设定一个初始的“温度”变量，影响解决方案的变动可能性。在算法的每一步，都会对当前路径进行小的随机调整来生成一个新路径。如果这个新路径更短，就会替换掉原来的路径。如果新路径更长，算法也可能以一定概率接受它，这个接受概率与“温度”变量有关：温度越高，接受更长路径的可能性就越大。随着算法的进行，“温度”逐渐降低，使得算法越来越不可能接受更长的路径，这帮助算法最终找到尽可能短的路径。

这给我们的算法提供了找到最佳解决方案的机会，并帮助它不会陷入局部最小值。随着时间的推移，温度变量会略微降低，选择较差解决方案的机会也随之减少。这模拟了金属冷却时的真实过程，并最终确定一个解决方案。

上面的动图展示了退火算法的实际应用。这个算法会在每个时间步重复整个路径的处理过程。注意，在早期，路径在每一步都会发生巨大变化。这是因为温度较高，算法更有可能接受提出的改变。随着过程的继续，值逐渐“冷却”，每个后续的变化都不那么剧烈。考虑到我们是从一个完全随机的路径开始，最终的解决方案似乎非常合理。这个过程对于30个房子来说效果很好，这是之前看似不可能的。

旅行推销员问题可以通过多种方法解决。其中模拟退火算法只是众多策略之一，该算法在实践中有不同的变体，包括如何选择可能的新解决方案以及如何调整算法的“温度”参数。这个参数的调整对于算法能否接受新的、可能不是最优的解决方案至关重要。在许多实现中，算法会以指数级的方式降低温度，这使得算法在开始时可以广泛探索，在过程中逐渐降低接受新解决方案的机率，最终更加集中于优化找到的解决方案。

P vs. NP

• 数独是一个NP问题，你能解决它吗？

旅行推销员问题是计算机科学中的NP问题的一个例子，这类问题可以在多项式时间内验证解决方案的正确性，但未知是否能在多项式时间内找到解决方案。这与P问题不同，后者既能在多项式时间内找到解决方案，也能在多项式时间内验证解决方案。这两类问题是否相同，即所有可以快速验证的问题是否也能快速解决，构成了计算机科学中的一个重大未解之谜，被称为P vs NP问题。这个问题非常关键，以至于Clay数学研究所提供了100万美元的奖金，奖励任何能证明这一点的人，因为它对理解我们如何有效解决复杂问题有重大意义。

这里的区别在于找到解决方案与验证解决方案。上面，我展示了经典的数独谜题。如果你以前从未玩过，我建议你尝试一下！在数独游戏中，玩家面对的是一个部分填充的方格板，通常是9x9的网格。这个网格被进一步划分为9个3x3的小盒子。游戏的目标是填充剩余的空格，使得每一行、每一列以及每一个3x3的盒子中的数字从1到9各出现一次。

在解决数独或类似的谜题时，通常会预设这些谜题至少有一个解。这种预设避免了玩家感到沮丧，因为他们知道通过正确的方法可以找到答案，而谜题设计者也因此能保持他们的声誉和工作。但如果你不确定谜题是否有解，挑战就会增加。在这种情况下，除了尝试解决谜题外，还需要确定谜题是否确实有解。这意味着即使使用正确的逻辑和方法，也可能无法找到答案，如果谜题本身就是无解的。因此，除了求解，还需要对谜题本身的可解性进行验证。

• 上面棋盘的一个解

这是一个易于验证但难以回答的问题。如果有人找到了答案，检查其正确性相对容易。然而，得到那个答案却很难。随着数独棋盘的大小增长，找到解变得越来越困难。然而，验证答案仍然相对容易。因此，由于求解和验证的对比，数独是一个NP问题。

P问题是计算机科学中一类既容易解决又容易验证解决方案的问题。这些问题可以通过高效的算法在多项式时间内找到解决方案，并且也可以在多项式时间内验证给定解决方案的正确性。例如，判断一个数字是否为质数就属于P问题，因为存在有效的算法能在合理时间内完成这一判断和验证。简而言之，P问题是那些对于计算机而言相对容易处理的问题。

为了将旅行推销员问题转换为这种语言，我们需要稍微改变一下问题的陈述。相反，我们将其描述如下：

给定一个城市列表及其位置，是否存在一条连接它们的路径，其长度最多为L？

旅行推销员问题是一个典型的NP问题，因为虽然验证给定的路径解决方案是否小于某个长度L是简单的（只需将所有路径的长度相加并比较总和与L），但实际上找到这样一个满足条件的路径却可能极其困难。即使运用如模拟退火这样的算法进行大量试验，也可能因为算法涉及的随机性而无法找到长度小于L的路径。这种解决方案的难以发现与其验证的简易性形成鲜明对比，从而使旅行推销员问题被分类为NP问题。

而这只是这个问题最简单形式的描述！还有许多现实世界的场景可以应用于增加复杂性。考虑像下面示例中那样，有一条河流穿过地图中间的情况。

• 一个解的例子是100个没有河流穿过中心的家庭

穿越河流的路径需要更多时间，并且会对路径的总长度有更大的贡献。在上面的示例解决方案中，你可以看到对不穿越河流有明显的偏好。尽管有多种可能性可以穿越河流，但最终路径只穿越了两次！与下面没有河流穿过中心的同样房子布局进行比较。

• 100个房子的示例解决方案，没有河流穿过中心

这实际上只是触及了旅行推销员问题的表面。还有更多的变体值得了解！同样重要的是要记住，上述解决方案并不保证是最佳的。退火算法效果不错且实用，但可能还有更好的解决方案。