周晓清，叶安胜，张志强

(1.电子科技大学 计算机科学与工程学院，四川 成都 611731；2.成都大学 信息科学与工程学院，四川 成都 610106)

0 引 言

1 问题及符号的定义

1.1 加权互斥最大集合覆盖问题的定义

1.2 问题转换

1.3 符号定义

为了描述方便，文中还定义如下符号：

1.4 递归算法时间复杂度的通用公式

假设基于分支搜索方法的递归算法下某个分支后，得到如下的一个递推公式T(n)≤T(n-n1)+T(n-n2)+…+T(n-nr)， 即将原问题分解为r个大小的子问题，其中r≥2，n为原问题的规模(比如图中的顶点数)，ni和n-ni分别为原问题分支后第i个子问题的减少量和第i个子问题规模。令T(n)=xn， 则上述递推公式可以转化为求解方程xn-xn-n1-xn-n2-…-xn-nr=0的最大实根。设c为该方程的最大实根，则在该分支下最坏的时间复杂度为O*(cn)， 称c为该递归关系式的分支因子。由于分支搜索算法不止一个分支，那么就将算法所有分支中最差的运行时间作为整个算法运行时间上界。

2 算法的设计及相关的性质定理

2.1 算法初步思想

2.2 性质和定理

以下将证明算法设计中用到的一些性质和定理。

证明：假设OPT为实例I中不包含顶点v的最优解，那么存在另外一个可行解OPT′=OPT∪v， 使得 |OPT′∩X|>|OPT∩X| 成立，这与OPT为最优解相矛盾，所以可以将度为0的顶点直接加入解中。

证明：由于交集图G的最大度Δ(G)≤1， 所以交集图G中顶点只存在以下两种情况，要么是度为0的独立点，要么是两个顶点相连的线段。

对于第一种情况，根据性质1可知，可直接将度为0的顶点加入解中。对于第二钟情况，首先判断两个顶点与X相交的情况，将与X相交元素更多的那个顶点加入解，如果两个顶点同X相交元素一样多，那么将权重较小的那个顶点加入解。如……