[转载]NP难、NP完全
2017-02-22 15:21阅读：
NP-Hard和NP-Complete的区别
对NP-Hard问题和NP-Complete问题的一个直观的理解就是指那些很难（很可能是不可能）找到多项式时间算法的问题.
因此一般初学算法的人都会问这样一个问题: NP-Hard和NP-Complete有什么不同? 简单的回答是根据定义,
如果所有NP问题都可以多项式归约到问题A, 那么问题A就是NP-Hard; 如果问题A既是NP-Hard又是NP,
那么它就是NP-Complete. 从定义我们很容易看出, NP-Hard问题类包含了NP-Complete类. 但进一步的我们会问,
是否有属于NP-Hard但不属于NP-Complete的问题呢? 答案是肯定的. 例如停机问题, 也即给出一个程序和输入,
判定它的运行是否会终止. 停机问题是不可判的, 那它当然也不是NP问题. 但对于SAT这样的NP-Complete问题,
却可以多项式归约到停机问题. 因为我们可以构造程序A, 该程序对输入的公式穷举其变量的所有赋值, 如果存在赋值使其为真, 则停机,
否则进入无限循环. 这样, 判断公式是否可满足便转化为判断以公式为输入的程序A是否停机. 所以,
停机问题是NP-Hard而不是NP-Complete.
NP:全称nondeterministicpolynomialtime，指可以在多项式时间内可验证问题。经常有人误把NP理解为non-polynomialtime。
NP 是 Non-deterministic Polynomial 的缩写,NP
问题通俗来说是其解的正确性能够被很容易检查的问题, 这里'很容易检查'指的是存在一个多项式检查算法.
例如, 著名的推销员旅行问题(Travel Saleman Problem or
TSP):假设一个推销员需要从香港出发, 经过广州, 北京, 上海,....., 等 n 个城市， 最后返回香港。
任意两个城市之间都有飞机直达， 但票价不等。现在假设公司只给报销 $C 块钱,
问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 $C ?
推销员旅行问题显然是 NP 的. 因为如果你任意给出一个行程安排,
可以很容易算出旅行总开销. 但是, 要想知道一条总路费小于 $C 的行程是否存在, 在最坏情况下, 必须检查所有可能的旅行安排!
这将是个天文数字.
NP-complete 问题是所有 NP 问题中最难的问题. 它的定义是,
如果你可以找到一个解决某个 NP-complete 问题的多项式算法, 那么所有的 NP 问题都将可以很容易地解决.
通常证明一个问题 A 是 NP-complete 需要两步, 第一先证明 A 是
NP 的, 即满足容易被检查这个性质; 第二步是构造一个从某个已知的 NP-complete 问题 B 到 A 的多项式变换,
使得如果 B 能够被容易地求解, A 也能被容易地 解决. 这样一来, 我们至少需要知道一个 NP-complete 问题.
第一个 NP complete 问题是 SAT 问题, 由 COOK 在 1971
年证明. SAT 问题指的是, 给定一个包含 n 个布尔变量(只能为真或假) X1, X2, .., Xn 的逻辑析取范式,
是否存在它们的一个取值组合, 使得该析取范式被满足? 可以用一个具体例子来说明这一问题, 假设你要安排一个 1000 人的晚宴, 每桌
10 人, 共 100 桌. 主人给了你一张纸, 上面写明其中哪些 人因为 江湖恩怨不能坐在同一张桌子上,
问是否存在一个满足所有这些约束条件的晚宴安排? 这个问题显然是 NP 的, 因为如果有人建议一个安排方式,
你可以很容易检查它是否满足所有约束. COOK 证明了这个问题是 NP-complete 的,
即如果你有一个好的方法能解决晚宴安排问题, 那你就能解决所有的 NP 问题.
这听起来很困难, 因为你必须面对所有的 NP 问题, 而且现在你并不知道任何的
NP-complete 问题可以利用.COOK 用非确定性图灵机( Non-deterministic Turing Machine
) 巧妙地解决了这一问题.
正式地, NP 问题是用非确定性图灵机来定义的,
即所有可以被非确定性图灵机在多项式时间内解决的问题. 非确定性图灵机是一个特殊的图灵机, 它的定义抓住了'解容易被检查' 这一特性.
非确定性图灵机有一个'具有魔力的'猜想部件, 只要问题有一个解, 它一定可以猜中. 例如, 只要存在哪怕一个满足约束的晚宴安排方式,
或是一个满足旅行预算的行程安排, 都无法逃过它的法眼, 它可以在瞬间猜中.
在猜出这个解以后,检查确认部分和一台普通的确定性图灵机完全相同,也即是等价于任何一个实际的计算机程序.
COOK 证明了,任意一个非确定性图灵机的计算过程,即先猜想再验证的过程,
都可以被描述成一个 SAT 问题,这个 SAT
问题实际上总结了该非确定性图灵机在计算过程中必须满足的所有约束条件的总和(包括状态转移, 数据读写的方式等等), 这样,
如果你有一个能解决该 SAT 问题的好的算法, 你就可以解决相应的那个非确定性图灵机计算问题, 因为每个 NP
问题都不过是一个非确定性图灵机计算问题, 所以, 如果你可以解决 SAT , 你就可以解决所有 NP 问题. 因此, SAT 是一个
NP-complete 问题.
有了一个 NP-complete 问题, 剩下的就好办了,
我们不用每次都要和非确定性图灵机打交道, 而可以用前面介绍的两步走的方法证明其它的 NP-complete 问题. 迄今为止,
人们已经发现了成千上万的NP-complete 问题, 它们都具有容易被检查的性质, 包括前面介绍的推销员旅行问题. 当然更重要的是,
它们是否也容易被求解, 这就是著名的 P vs NP 的问题.
贪心法
贪心法(Greedy
algorithm)是一种在每一步选择中都采取在当前状态下最好/优的选择，从而希望导致结果是最好/优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，
那这就是一种贪心算法。
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它每对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
贪心法可以解决一些最优性问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
贪心法解题特点
贪心法有一个共同的点就是在最优求解的过程中都采用一种局部最优策略，把问题范围和规模缩小最后把每一步的结果合并起来得到一个全局最优解。
贪心法解题的一般步骤
（1）从问题的某个初始解出发；
（2）采用循环语句，当可以向求解目标前进一部时，就根据局部最优策略，得到一个部分解，缩小问题的范围和规模；
（3）将所有部分解综合起来，得到问题最终解。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3.
只能求满足某些约束条件的可行解的范围。
穷举法
穷举法，或称为暴力破解法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。
破译方法
穷举法是一种针对于密码的破译方法。这种方法很像数学上的“完全归纳法”并在密码破译方面得到了广泛的应用。简单来说就是将密码进行逐个推算直到找出真正的密码为止。比如一个四位并且全部由数字组成其密码共有10000种组合，也就是说最多我们会尝试10000次才能找到真正的密码。利用这种方法我们可以运用计算机来进行逐个推算，也就是说用我们破解任何一个密码也都只是一个时间问题。
当然如果破译一个有8位而且有可能拥有大小写数字、字母、以及符号的密码用普通的家用电脑可能会用掉几个月甚至更多的时间去计算，其组合方法可能有几千万亿重种组合。这样长的时间显然是不能接受的。其解决办法就是运用字典，所谓“字典”就是给密码锁定某个范围，比如英文单词以及生日的数字组合等，所有的英文单词不过10万个左右这样可以大大缩小密码范围，很大程度上缩短了破译时间
字母A、B、C、...Z等（26个）
3.小写字母a、b、c、...z等（26个）
4.特殊字符～、＄、＃、@、&、＊等（33个）一般较少用
5.用户自定义字符。
如果一个多位数并且有可能包含以上所有字符的密码的组合方法一定多的惊人，相对来讲破译的时间也会长的没法接受，有时可能会长达数年之久。
字典
当然如果破译一个有8位而且有可能拥有大小写数字、字母、以及符号的密码用普通的家用电脑可能会用掉几个月甚至更多的时间去计算，其组合方法可能有几千万亿重种组合。这样长的时间显然是不能接受的。其解决办法就是运用字典，所谓“字典”就是给密码锁定某个范围，比如英文单词以及生日的数字组合等，所有的英文单词不过10万个左右这样可以大大缩小密码范围，很大程度上缩短了破译时间。
超级计算机也不在少数，例如IBM为美国军方制造的“飓风”就是很有代表性的一个。
迭代法
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。
迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。
利用迭代算法解决问题，需要做好以下三个方面的工作：
一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
例：
验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象：对于任意一个自然数 n ，若 n 为偶数，则将其除以 2 ；若 n
为奇数，则将其乘以 3 ，然后再加 1 。如此经过有限次运算后，总可以得到自然数 1
。人们把谷角静夫的这一发现叫做“谷角猜想”。
要求：编写一个程序，由键盘输入一个自然数 n ，把 n
经过有限次运算后，最终变成自然数 1 的全过程打印出来。
分析： 定义迭代变量为 n
，按照谷角猜想的内容，可以得到两种情况下的迭代关系式：当 n 为偶数时， n=n/2 ；当 n 为奇数时， n=n*3+1 。用
QBASIC 语言把它描述出来就是：
if n 为偶数 then
n=n/2
else
n=n*3+1
end if
这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次，才能使迭代变量 n 最终变成自然数 1
，这是我们无法计算出来的。因此，还需进一步确定用来结束迭代过程的条件。仔细分析题目要求，不难看出，对任意给定的一个自然数 n
，只要经过有限次运算后，能够得到自然数 1 ，就已经完成了验证工作。因此，用来结束迭代过程的条件可以定义为： n=1
。参考程序如下：
cls
input 'Please input
n=';n
do until n=1
if n mod 2=0 then
rem 如果 n 为偶数，则调用迭代公式
n=n/2
n=n/2
