算法分析与设计 —— NP完全性理论
确定性算法和非确定性算法
(1)确定性算法:整个执行过程中每一步都只有一个选择,则称A是确定性算法。对同样的输入,输出结果一定相同。
(2)非确定性算法:在每一时刻,根据当时的状态和输入,若机器有多个动作可供选择,第一个获得结束的成功选择使算法终止,此时称算法为非确定性的。
P类问题
用一个确定性算法在多项式时间内可解的问题。
(1) P类问题是NP问题的子集(如果P类问题既然能在多项式时间内求解,也必然能在多项式时间在验证它的解)
NP类问题
能在多项式时间内验证得出一个正确解的问题。
(1)对于哈密尔顿回路问题,如果给出一个任意的回路,我们可以很容易的判断出该回路是否是哈密尔顿回路(看是不是所有顶点都在回路中),故哈密尔顿回路是NP问题。
约化
(1)一个问题A可以约化成问题B的含义即是,可以用解决问题B的解法来解决问题A,或者说,问题A可以“变成”问题B。如:一元一次方程可以“约化”为一元二次方程
(2)问题A可“约化”为问题B的直观意义:B的时间复杂度高于或等于A的时间复杂度。也就是说,问题A不比问题B难
(3)约化具有传递性:如果问题A可约化成问题B,问题B可约化成问题C,则问题A一定可约化成问题C
(4)约化需要在多项式时间内完成
NP完全问题(NPC)
存在这样一个NP问题,所有的NP问题都可以在多项式时间内约化成它,则这个问题是NPC问题。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。
(1)NPC问题是NP问题的子集。
(2)目前为止我们还不能证明NPC问题有多项式算法(即NP等于P),也不能证明NPC问题没有多项式算法(即NP不等于P)。因此,我们一般认为NPC问题是难解问题。
(3)如何证明一个新问题A是NPC问题
-
证明A∈NP;
-
选取一个已知的NPC问题B;
-
构造一个从B到A的变换f;
-
证明f为一个多项式变换。
(4)哈密尔顿回路也是NPC问题,但尚未被解决。(通过上述证明过程可被证明)
NP难问题(NPH)
存在这样一个NPC问题,所有的NPC问题都可以在多项式时间内约化成它,则这个问题是NPH问题