加权互斥最大集合覆盖问题的精确算法  

Exact algorithms for weighed mutually exclusive maximum set cover problem

作　　者：周晓清 叶安胜 张志强 ZHOU Xiao-qing;YE An-sheng;ZHANG Zhi-qiang(School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China;College of Information Science and Engineering,Chengdu University,Chengdu 610106,China)

机构地区：[1]电子科技大学计算机科学与工程学院,四川成都611731 [2]成都大学信息科学与工程学院,四川成都610106

出　　处：《计算机工程与设计》2020年第12期3412-3418,共7页Computer Engineering and Design

基　　金：四川省教育厅科研项目重点基金项目(15ZA0354);国家重点研发计划基金项目(2016YFB0800605)。

摘　　要：加权互斥最大集合覆盖问题是一个NP难问题,为解决该问题设计一个分支搜索算法,采用测量治之方法对算法运行时间界进行分析,得到算法的时间复杂度为O^*(1.3132 m),改进该问题原有的最佳运行时间界O^*(1.325 m)。通过比较可知,基于测量治之方法分析得到的结果优于传统方法分析得到的结果,可以在不改变算法的前提下通过度量设置的改变进一步改进算法的运行时间界,度量设置方案越详细得到的结果更好。The weighted mutually exclusive maximal set cover problem is a NP-hard problem.To solve this problem,a branch and reduce algorithm was designed and it was analyzed using the measure-and-conquer method.Its running time bound was O^*(1.3132 m)which improved the original best running time bound O^*(1.325 m)for this problem.The comparison shows that the result obtained using the measure-and-conquer method is better than that obtained by the traditional method.Through the measure-and-conquer method,the algorithm running time bound can be further improved by changing the measure settings without changing the original algorithm,and the scheme of measure settings is more detailed and the results obtained are better.

关 键 词：NP难问题 分支搜索 测量治之 精确算法 加权互斥最大集合覆盖问题 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]