近似算法之顶点覆盖问题近似算法之顶点覆盖问题

近似算法 ?许多具有实际意义的问题都是NP完全问题。我们不知道如何在多项式时间内求得最优解。但是，这些问题往往十分重要，我们不能因此而放弃对它们的求解，即使一个问题是NP完全的，也有它的求解方法。实际应用中，近似最优解一般都能满足要求。返回近似最优的方法称为近似算法。
这里补充几个概念。
多项式时间 ?指O(1)、O(logN)、O(N2)等这类可用多项式表示的时间复杂度，通常我们认为计算机可解决的问题只限于多项式时间内。而O(2N)、O(N!)这类非多项式级别的问题，其复杂度往往已经到了计算机都接受不了的程度。
P类问题、NP问题、NP完全问题 ?所有可以在多项式时间内求解的判定问题构成P类问题
—————————
?所有非确定性多项式时间内可解的判定问题构成NP类问题
—————————
?NP中的一类比较特殊的问题，这类问题中每个问题的复杂度与整个类的复杂度有关联性，假如其中任意一个问题在多项式时间内可解的，则这一类问题都是多项式时间可解。这些问题被称为NP完全问题（NP-C）
—————————
话不多说，上表

问题类型	是否能在多项式时间内求解	是否能在多项式时间内验证
P类	是	是
NP类	是or否	是
NP-C	未知	是

顶点覆盖问题顶点覆盖 ?顶点覆盖是一个点集。无向图G=(V,E)的一个顶点覆盖是一个子集V'?V，使得如果（u，v）是G的一条边，则u∈V’，或者v∈V’（也可能两者都成立）。一个顶点覆盖的规模是其中所包含的顶点数。
顶点覆盖问题 ? 在一个给定的无向图中，找出一个具有最小规模的顶点覆盖，并称这样的顶点覆盖为最优顶点覆盖。
顶点覆盖问题的算法 ? 顶点覆盖问题是一个NP完全判定问题的最优化形式。虽然在一个图G中寻找最优顶点覆盖比较困难，但是找出近似最优的顶点覆盖还是相对容易的。
以下是针对顶点覆盖问题的近似算法的伪代码

APPROX-VERTEX-COVER(G)
1 C=?
2 E'=G.E
3 while E'≠?
4 ? let(u,v)be an arbitrary edge of E'
5 ? C=C∪{u,v}
6 ? remove from E' every incident on either u or v
7 return C

APPROX-VERTEX-COVER是一个多项式时间的2近似算法[1]