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

Research of data reduction on set covering problem

作　　者：陈韬[1] 吴志勇[1] 孙乐昌[1] 张旻[1] 刘京菊[1] 

机构地区：[1]解放军电子工程学院

出　　处：《计算机应用研究》2010年第9期3307-3311,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(60972161);电子工程学院博士生创新基金资助(CX2007016)

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

关 键 词：集合覆盖 约简方法 约简算法 贪心算法 遗传算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]