NP-Hard问题浅谈

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

项目github地址：bitcarmanlee easy-algorithm-interview-and-practice
欢迎大家star，留言，一起学习进步

看相关算法的paper的时候，经常会出现NP-Hard这个词。本博主也不是纯数学系出身，对于这么高深的问题自然没有特别深入独到的理解。但是本博主的习惯就是看到一个东西老在眼前晃来晃去但自己还不是很明白，就有强迫症一定要搞明白这到底是个什么玩意。so，咱们就来看看这个NP-Hard问题，怎么用最简单的方式去了解。

1.世界七大数学难题之首

2000年，美国克莱数学研究所公布了世界七大数学难题，又称千禧年大奖难题。其中P与NP问题被列为这七大世界难题之首，从而大大激发了对这一问题的研究热情。

普林斯顿大学计算机系楼将二进制代码表述的“P=NP?”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。
康奈尔大学的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：
反证法。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到了矛盾。(上面内容来自wiki百科)

难怪本博主之前对这个问题理解不深刻。看到上面的资料宝宝放心了，说明宝宝智商还是正常的。

2.算法复杂度

要计算或解决一个问题，该问题通常有一个大小规模，用n表示。例如，若分析计算一个二进制数，该数有多少位，这个位就是其大小规模。再比如，从n个数里面找出最大的那个数，这个n就是该问题的规模大小。怎么找？我们要比较n-1次才能得到结果，这个n-1就是所花的时间，也就是时间复杂度。再比如，将n个数按从大至小排序，n是其规模大小，若是我们按这样的方法：第一次从n个数里找最大，第二次从n-1个数里找最大，以此类推，需要的比较次数就是n(n-1)/2,称我们所用的方法为算法，称n(n-1)/2为该算法的时间复杂度。对于时间复杂度，当n足够大时，我们只注重最高次方的那一项，其他各项可以忽略，另外，其常数系数也不重要，所以，n(n-1)/2我们只重视n的平方这一项了，记为O(n的平方），这就是该算法对该问题的时间复杂度的专业表示。
上面这段描述，估计大家都能看懂，就不在啰嗦了。重点在下面，前方高能预警，大家注意了。

所有形如 $a*n^k+b*n^{(k-1)}+c*n^{(k-2)}+\cdots$ 都可记为 $O(n^k)$ ，$ n^{k$为n的k次方，*自然就是乘法了，这样的复杂度为多项式(polynomial)时间复杂度。若是时间复杂度为$k}n $， k 为大于 1 的常数，或者$ n! $的时间复杂度，或者比$ n!$更大的时间复杂度，就称为指数型时间复杂度。显然，当n足够大时，指数型时间比多项式要大得多的多。

3.P问题与NP(Non-deterministic Polynomial )问题

所有能用多项式时间算法计算得到结果的问题，称为多项式问题，也就是P，所有绝对不可能用多项式时间求解的可解问题，称为指数型问题。当然，还有一类问题属于不可解问题，也就是说你无论花多少时间也不能得到解答。

有这样一类问题，假使你得到了问题的解，我要验证你的解是否正确，我验证所花的时间是多项式，至于求解本身所花的时间是否是多项式我不管，可能有多项式算法，可能没有，也可能是不知道，这类问题称为NP问题。
NP概念的奥妙在于，它躲开了求解到底需要多少时间这样的问题，而仅仅只是强调验证需要多少时间，从而为P与NP这一千年难题的产生埋下了伏笔。显然，P肯定是NP，因为你既然能用多项式求解，就肯定能用多项式验证（难不成我再算一遍！），但NP是否是P谁也确定不了。另外，目前已经很明确的指数型问题也肯定不是NP。

用通俗的话来解释，NP问题就是其解的正确性很容易被检验出来，这里的很容易检验指的是存在一个多项式算法。

4.最具代表性的NP-Hard问题：TSP

售货员旅行问题 (traveling salesman problem)，是最具有代表性的NP问题之一。假设一个推销员需要从香港出发，经过广州，北京，上海，…，等 n 个城市，最后返回香港。任意两个城市之间都有飞机直达，但票价不等。现在假设公司只给报销 C 块钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？
推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排! 这将是个天文数字。
这个天文数字到底有多大？目前的方法接近一个一个的排着试，还没有找到更好可以寻得最短路径的方法。对七个城而言，共有 6!=720 个排法，还比较简单；，但若有 20 个城，则排法就有 19! 种。因故在排列组合里 n! 写起来轻松。但 $1.21*10^{17}$ 是一个大得不得了的数字。若每秒钟排一次，要排 $3.84*10^9$ 年（一年约为 $3.15*10^7$ 秒），即使使用计算器，每秒排一百万次（不容易做到）也得重做三千年才能找到答案。「生也有涯，知也无涯」，想不到区区二十个城，要三十个世纪才能找到答案。