宁爱兵， 刘艳芳， 王英磊

（上海理工大学管理学院，上海 200093）

集合覆盖问题（set covering problem，SCP）是组合优化中一个典型NP（non－deterministic polynomial time，非确定多项式时间算法）难解问题，是计算机和运筹学中的一个经典问题，在人员调动、网络安全、资源分配、电路设计、运输车辆路径安排等领域有着广泛的应用［1－4］.

对于集合覆盖问题，目前国内外主要有两种处理方法：一种是采用启发式算法［2－3］；另外一种是采用精确算法或近似算法［1，4］.各种算法的优缺点及其对比将在后面介绍.

本文将集合覆盖问题转换成二分图，再在二分图上给出降阶规则，给出上界和下界子算法，最后结合成一个新的降阶算法.

1 问题及算法介绍

1.1 问题简介

集合覆盖问题是一个优化问题，其原型是多资源选择问题.集合覆盖问题可以看作是图的顶点覆盖问题的推广，它也是一个NP难问题.

集合覆盖问题的一个实例〈X，F〉由一个有限集X及X的一个子集族F组成.子集族F覆盖了有限集X，也就是说X中每一元素至少属于F中的一个子集，即对于F中的一个子集C⊆F，若C中的X的子集覆盖了X，即，则称C覆盖了X.集合覆盖问题就是要找出F中覆盖X的最小子集C＊，使得｜C＊｜＝min｛｜C‖C⊆F且C覆盖X｝.

1.2 问题转换

在算法处理之前，将该问题转换成二分图来进行处理，转换方法如下：

将集合覆盖问题〈X，F〉中X的每个元素作为二分图的一个顶点子集X，把F中的每个元素作为二分图的另一个顶点子集F，F中的元素是集合.若F中的元素f1包含X中的元素x1，则在f1与x1之间连线，否则不连线.

这样处理后，得到一……