漫画：什么是旅行商问题（NP）？

淩亂°似流年 2023-07-17 11:30 1阅读 0赞

![format_png][]

![format_png 1][]

![format_png 2][]

![format_png 3][]

需要规划出怎样的路线呢？举个例子：

有一个快递员，要分别给三家顾客送快递，他自己到达每个顾客家的路程各不相同，每个顾客之间的路程也各不相同。

![format_png 4][]

那么，想要把快递依次送达这三家，并最终回到起点，哪一条路线所走的总距离是最短的呢？

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

![format_png 11][]

**旅行商问题**

和小灰所遇到的问题类似，旅行商问题所描述的是这样一个场景：

有一个商品推销员，要去若干个城市推销商品。该推销员从一个城市出发，需要经过所有城市后，回到出发地。每个城市之间都有道路连通，且距离各不相同，推销员应该如何选择路线，使得总行程最短呢？

![format_png 12][]

这个问题看起来很简单，却很难找到一个真正高效的求解算法。其中最容易想到的，是使用**穷举法**：

把所有可能的路线穷举出来，计算出每一条路线的总行程：

A-B-C-D-E-F-G-H-I

A-B-C-D-E-F-G-I-H

A-B-C-D-E-F-H-G-I

A-B-C-D-E-F-H-I-G

A-B-C-D-E-F-I-H-G

A-B-C-D-E-F-I-G-H

......

像上面这样排列组合，从所有路线中找出总行程最短的路线。显然，这个方法的时间复杂度是**O(n！****)**，随着城市数量的增长，花费的运算时间简直不可想象！

后来，人们想出了许多相对优化的解决方案，比如**动态规划法**、**分枝定界法**（这个算法很有意思，以后会专门写一篇漫画来详细介绍）......但是，这些算法的时间复杂度仍然是指数级的，并没有让性能问题得到根本的解决。

![format_png 13][]

![format_png 14][]

**P和NP**

NP到底是什么意思呢？

我们曾经学习过许许多多的算法，这些算法的时间复杂度都可以用多项式来表示，比如：

归并排序的时间复杂度是O（nlogn）

冒泡排序的时间复杂度是O（n^2）

Floyd算法的时间复杂度是O（n^3）

尽管这些算法的运行时间有数量级上的差别，但是它们的时间复杂度都可以用O（n^k）来表示，k是一个常数。

因此，这些算法都是**多项式时间算法**，能用多项式时间算法解决的问题被称为**P问题**( Polynomial)。

人们常说，能用钱解决的问题都不是问题，在计算机科学家眼中，能用多项式时间解决的问题都不是问题。

然而，世间还存在许多变态的问题，是无法（至少是暂时无法）在多项式时间内解决的，比如一些算法的时间复杂度是O（2^n），甚至O（n!）。

随着问题规模n的增长，计算量的增长速度是非常恐怖的。这类问题被称为**NP问题**（Non-deterministic Polynomial），即非确定多项式问题。

有些科学家认为，所有的NP问题终究都可以在多项式时间内解决，只是我们暂时还没有找到方法；也有些科学家认为，某些NP问题永远无法在多项式时间内解决。

这个业界争论可以用一个公式来表达：

**NP = P？**

![format_png 15][]

![format_png 16][]

![format_png 17][]

**归约和NPC**

这里所说的NPC问题可不是游戏当中的NPC，它究竟是什么意思呢？要想理解NPC问题，我们需要先了解**归约**的概念。

归约，可以简单理解成问题之间的转化。例如问题Q是一个一元一次方程的求解问题：3x+6 = 12，这个问题可以转化成一个一元二次问题Q'：0x^2+3x+6 = 12。

显然，问题Q并不比问题Q'更难解决，只要有办法解决Q'，就一定能够解决Q。对于这种情况，我们可以说**问题Q归约于问题Q'**。

同时，这种归约可以逐级传递，比如问题A归约于问题B，问题B归约于问题C，问题C归约于问题D，那么我们可以说问题A归约于问题D。

在NP问题之间，也可以存在归约关系。我们把众多的NP问题层层归约，必定会得到一个或多个“终极问题”，这些归约的终点就是所谓的**NPC问题**（NP-complete），也可以翻译成NP完全问题。上面所讲的旅行商问题，被科学家证明属于NPC问题。

![format_png 18][]

就数量上而言，NP问题远比P问题要多，而NP之中的NPC问题也仅占极少数，所以P、NP、NPC之间的关系可以用下图来表示：

![format_png 19][]

俗话说擒贼先擒王，只要有朝一日，我们能够找到NPC问题的多项式时间算法，就能够解决掉所有的NP问题！但遗憾的是，至今还没有人能够找到可行的方法，很多人认为这些问题是无解的。

![format_png 20][]

![format_png 21][]

![format_png 22][]

![format_png 23][]

![format_png 24][]![format_png 25][]

![format_png 26][]

—————END—————

[format_png]: /images/20230528/f876fe6fbffd4d2596f4caa724877446.png
[format_png 1]: /images/20230528/6c6961870dcb41deaa67d7882828505c.png
[format_png 2]: /images/20230528/bf594ac61f754c14a784966d97921b44.png
[format_png 3]: /images/20230528/b9f7722f1cac4b23a31e7ed649cb508c.png
[format_png 4]: /images/20230528/320c1e260d9f4f1e959f9385e040bf8e.png
[format_png 5]: /images/20230528/29705601f27e439f8c9431f759c6b459.png
[format_png 6]: /images/20230528/a807565640834b17a460d264b9daf2fb.png
[format_png 7]: /images/20230528/9256c854f3fd4bb19e85c5059b46b7cd.png
[format_png 8]: /images/20230528/313b4459741640aa8fd1ee7a559bbcc3.png
[format_png 9]: /images/20230528/19e61ad3fb39409893e892c1663c52be.png
[format_png 10]: /images/20230528/71554404c2c14ca6a6fab1e9abdb0441.png
[format_png 11]: /images/20230528/f9ad06f9076b4fd6932eaf4ec36d4e7f.png
[format_png 12]: /images/20230528/63a74d9146ed4cca83a3b7f219051c9b.png
[format_png 13]: /images/20230528/61027e65f0484109b9efefbfd4239617.png
[format_png 14]: /images/20230528/ffeb25c7720049bab5ab1384a182f489.png
[format_png 15]: /images/20230528/bfb79e5d479840aab8559ee20fa5b5ff.png
[format_png 16]: /images/20230528/5df4ce99dd474c58ba57f8f0ce325d8e.png
[format_png 17]: /images/20230528/ea890f98d3234e71a39acb3308339586.png
[format_png 18]: /images/20230528/6319de5564bc4ee1a918b6939d621291.png
[format_png 19]: /images/20230528/1f48fbdec7064eefbc1b5f7de2ac9ff1.png
[format_png 20]: /images/20230528/a090606bdf544c0ca82fecd26d0f66a7.png
[format_png 21]: /images/20230528/fe5babbeb29848278e43591bd32c3d23.png
[format_png 22]: /images/20230528/7baa121373b7447e8f0c26e9559ccebb.png
[format_png 23]: /images/20230528/8edbc36449144f1e9ee184afee58c5cc.png
[format_png 24]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3A5T1ZsR0ZVdVhpYkl6NkxvcDV0RkRZMG1Wak1QbzBSSFBIUmljQ3o2SmVOMmVFNm94YmlibUJXYlRwYkdMR3ROempnWnV3V0xscmJnM2cvNjQw?x-oss-process=image/format,png
[format_png 25]: /images/20230528/8520be7ff9074e929a5dcc404142b5f9.png
[format_png 26]: /images/20230528/c12d2369c9de4a64a4a1cf8bab47cb9c.png