NP完全性问题

    在学习算法设计与分析时，经常会提到NP完全性问题，到底什么是NP完全性问题? ...

    NP完全性问题属于"计算复杂性"研究的课题。 所谓计算复杂性，通俗说来，就是用计算机求解问题的难易程度。其度量标准有两个：一是计算所需步数或者指令数(时间复杂度)；二是计算所需的存储单元数(空间复杂度)。它不是对一个具体问题去研究它的计算复杂性，而是依据难度去研究各种计算问题之间的联系，按复杂性把问题分成不同的类，即复杂性类。

    再强调一下，问题的复杂性和算法的复杂性的区别是：只就时间复杂性来说，算法的复杂性是指解决一个问题的算法执行的时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度。计算复杂性要研究的是后者。

    如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则称这种可以在多项式时间内解决的判定性问题属于p类问题。p类问题就是所有复杂度为多项式时间的问题的集合。

   然而有些问题很难找到多项式时间的算法(或许根本不存在)，比如"找出无向图中哈密尔顿回路"问题。但是我们发现如果给了我们该问题的一个答案，就可以在多项式时间内判断这个答案是否正确。给出一个任意的回路，我们很容易判断它是否是哈密尔顿回路(只要看是不是所有的顶点都在回路中就可以了)。这种可以在多项式时间内验证一个解是否正确的问题成为NP问题，又称易验证问题类。

    简单地说，存在多项式时间的算法的一类问题称为P类问题；而像梵塔问题、推销员旅行问题等，至今没有找到多项式时间算法解的一类问题，称为NP类问题。


    复杂性理论中最具理论意义的当数NP完全性问题(NPC问题)，即由于"P=NP是否成立"这个问题难以解决，从NP类的问题中分出复杂性最高的一个子类，把它叫做NP完全类。已经证明，任取NP类中的一个问题，再任取NP完全类中的一个问题，则一定存在一个具有多项式
时间复杂性的算法，可以把前者转变成后者。这就表明，只要能证明NP完全类中有一个问题是属于P类的，也就证明了NP类中的所有问题都是P类的，即证明了P=NP。

    目前已知的NP完全性问题就有2000多个，在图上定义的许多组合优化问题是NP完全性问题，如货郎问题、调度问题、最大团问题、最大独立集合问题、Steiner树问题、背包问题、装箱问题等，遇到这类问题时，通常从以下几个方面来考虑，并寻求解决办法：

    (1) 动态规划法：较高的解题效率。

    (2) 分枝限界法： 较高的解题效率。

    (3) 概率分析法： 平均性能很好。

    (4) 近似算法： 近似解代替最优解。

    (5) 启发式算法：根据具体问题的启发式搜索策略在求解，在实际使用可能很有效，但有时很难说清它的道理。