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

作     者：周晓清 叶安胜 张志强 ZHOU Xiao-qing;YE An-sheng;ZHANG Zhi-qiang

作者机构：电子科技大学计算机科学与工程学院四川成都611731 成都大学信息科学与工程学院四川成都610106 

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

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2020年第41卷第12期

页      码：3412-3418页

摘      要：加权互斥最大集合覆盖问题是一个NP难问题,为解决该问题设计一个分支搜索算法,采用测量治之方法对算法运行时间界进行分析,得到算法的时间复杂度为O^*(1.3132 m),改进该问题原有的最佳运行时间界O^*(1.325 m)。通过比较可知,基于测量治之方法分析得到的结果优于传统方法分析得到的结果,可以在不改变算法的前提下通过度量设置的改变进一步改进算法的运行时间界,度量设置方案越详细得到的结果更好。

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

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.16208/j.issn1000-7024.2020.12.017

馆 藏 号：203997205...