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

摘要：

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

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

所属期刊栏目：41

分类号：TP301(计算技术、计算机技术)

资助基金：四川省教育厅科研项目重点基金项目;国家重点研发计划基金项目

在线出版日期：2020-12-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：3412-3418