集合覆盖问题的数据约简研究*

针对当前解决大规模集合覆盖问题的算法普遍存在着效率不高的问题，提出了一套削减数据规模的约简方法，并给出了一个能够与其他所有解决集合覆盖问题算法相结合的约简算法。用Beasley提出的45个测试用例进行试验，结果显示贪心算法和遗传算法在结合了约简算法后能够在更少的时间内得到更优的解，表明该约简方法和约简算法可以有效提高传统算法和智能算法解决大规模集合覆盖问题的效率。

Research of data reduction on set covering problem

When solving the large-scale set covering problem (SCP), there is a universal efficiency problem for most algorithms. To solve the problem, this paper proposed a suite of reduction theories to reduce the data scale and gave a universal DRA which could be combined with all the algorithms solving SCP. 45 instances proposed by Beasley are tested. Experiments results show that after combined with DRA, the greedy algorithm and genetic algorithm can achieve better solutions with less time, which indicates that the reduction theory and DRA can effectively improve the efficiency for both traditional algorithms and intelligent algorithms to solve SCP.