《计算机应用研究》|Application Research of Computers

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

Research of data reduction on set covering problem

免费全文下载 (已被下载 次)  
获取PDF全文
作者 陈韬,吴志勇,孙乐昌,张旻,刘京菊
机构 解放军电子工程学院 合肥 230037
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2010)09-3307-05
DOI 10.3969/j.issn.1001-3695.2010.09.028
摘要 针对当前解决大规模集合覆盖问题的算法普遍存在着效率不高的问题,提出了一套削减数据规模的约简方法,并给出了一个能够与其他所有解决集合覆盖问题算法相结合的约简算法。用Beasley提出的45个测试用例进行试验,结果显示贪心算法和遗传算法在结合了约简算法后能够在更少的时间内得到更优的解,表明该约简方法和约简算法可以有效提高传统算法和智能算法解决大规模集合覆盖问题的效率。
关键词 集合覆盖;约简方法;约简算法;贪心算法;遗传算法
基金项目 国家自然科学基金资助项目(60972161)
电子工程学院博士生创新基金资助项目(CX2007016)
本文URL http://www.arocmag.com/article/1001-3695(2010)09-3307-05.html
英文标题 Research of data reduction on set covering problem
作者英文名 CHEN Tao, WU Zhi-yong, SUN Le-chang, ZHANG Ming, LIU Jing-ju
机构英文名 Electronic Engineering Institute of PLA, Hefei 230037, China
英文摘要 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.
英文关键词 set covering; reduction theory; data reduction algorithm(DRA); greedy algorithm; genetic algorithm
参考文献 查看稿件参考文献
 
收稿日期
修回日期
页码 3307-3311
中图分类号
文献标志码 A