个人技术笔记

NP完全问题

发布时间：2015-12-07  栏目：软件算法  评论：0 Comments

NP完全问题(NP-C问题)， NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。

这里主要把问题分为三类：

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

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

3.  NP完全（NP-Complete）。从非形式的意义上来说，如果一个问题属于NP，且与NP中的任何问题是一样“难的”（hard），则说它属于NPC类，也称它为NP完全的。换句话说，如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题（Non-deterministic Polynomial complete problem）。NP完全问题也叫做NPC问题。

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

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

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

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

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

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

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

留下评论

You must be logged in to post a comment.