加权集合覆盖问题的加权分治算法  

Measure and Conquer Algorithm for Minimum Weighted Set Covering Problem

作　　者：胡琳琳[1] 宁爱兵[1] 黄飞[1] 刘志民[1] 张惠珍[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《小型微型计算机系统》2016年第5期987-991,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(71401106)资助;上海市一流学科建设项目(S1201YLXK)资助;高等学校博士学科点专项科研基金联合课题(20123120120005)资助

摘　　要：加权分治技术是一种用于算法分析和设计的新方法,该技术通过对处理对象按不同重要程度而赋予不同的权值来更加精确的描述算法分支子问题规模的大小,从而降低算法的时间复杂度.分支降阶技术是广泛用于求解组合优化领域难题的技术之一,该技术的核心思想是将原问题分支成若干个子问题,并用递归来求解这些子问题.加权集合覆盖问题是一个典型的NP难题,利用加权分治技术对集合覆盖问题进行研究,给出了一个精确算法,降低了算法的时间复杂度.在进行算法处理之前,将问题转换成二分图,并提出相应的降阶规则,将原问题的规模进行了缩小,在此基础上运用加权分治技术来分析其算法的复杂度.研究表明运用加权分治技术能够得到较传统算法更精确的时间复杂度.The approach of measure and conquer is a new technique for algorithm design and analysis. The central idea of Measure and Conquer is to focus on the choice of the measure. In other words, the method first chooses a refined non-standard measure to measure the input size of the problem and its subproblems at each branching step of branch and bounded algorithm. Then the running time of the algorithm can be reduced by this approach. Branch and reduce is a widely used approach for solving combinatorial optimization problems. The core of the approach is to solve the problem by decomposing it into two or more subproblems, which can be recursively solved. Minimum weighted set covering problem is a typical NP-hard problem. In this dissertation, based on the branch and reduce technology, a fast recursive algorithm is designed, we develop and analyze an exact algorithm and reduce the running time complexity. In this paper, before the processing of algorithm, we converted the problem into binary map, and proposed the corresponding degrada- tion rules, and reduced the size of the original problem, based on the measure and conquer approach technology to analysis the time complexity of the algorithm. The result of this paper show that measure and conquer approach has a tremendous impact compared with the traditional algorithm.

关 键 词：加权集合覆盖问题 加权分治技术 分支降阶技术 时间复杂度 

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