http://acm.scu.edu.cn/soj/problem.action?id=2294

SCU上的这一题就是求一无向图的最大独立子集.
在网上搜了下,知道了最大全完图与最大独立子集问题是等价的,而且好像都是NP问题.
找到一求最大独立子集的算法,如下,可是自己按那算法写的个程序,却一直超时.实在不知道该怎么优化.

请教个位牛人,不知还有什么更好的方法?或者如何实现这个算法时间消耗会比较少?


如何求图的最大独立集
具体程序实现可以通过求最小覆盖集来求最大独立集。 
图G(V,E)的覆盖集D是顶点集的一个子集,并满足:任意  <vi,vj>属于E,vi属于D或vj属于D    
定义  *，+  满足交换率，结合率，  
且  *对+分配  (a+b)*c  =  a*c  +  b*c  
吸收率：  
a+ab  =  a  
a*a  =  a  
a+a  =  a  
这样，求极小覆盖集：   
 M(连乘)(    (v[i]    +    M(所有与v[i]相邻的点)      )  
i=0  to  n                            
结果化简后的每个因子项即对应一个极小覆盖集。  
for  example:  
a---b---c  
 \  /  \  /  
   d      e  
(a+bd)(b+acde)(c+be)(d+ab)(e+bc)  
 =  acde+abe+bcd+abc+bde      
acde,abe,bcd,abc,bde  既是G的各个极小覆盖集。
因为极小覆盖集和极大独立集互补，用abcde  减去各个极小覆盖集，  
既得到极大独立集：  
b  dc  ae  de  ac    
其中dc  ae  de  ac是最大独立集
算了一下，发现根据式子直接运算就可以得到最简答案，不需要什么技巧。  
比如初始化为  a  +  bd。  
然后用  b  +  acde分别和上面的式子相乘，相乘时注意运用  a*a=a（可以用集合来实现），相加时注意运用  a+a=a和a+ab=a（如果其它项是该项的子集则取消该项)，一直下去就能得出最终结果了。

• NP完全问题，搜索+剪枝 (1054) wywcgs 2006-10-13 15:04:01