集合覆盖问题的模型与算法  

Model and algorithm for set cover problem

作　　者：王继强[1] 

机构地区：[1]山东财经大学数学与数量经济学院,济南250014

出　　处：《计算机工程与应用》2013年第17期15-17,72,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.10901093)

摘　　要：集合覆盖问题在网络设计领域中有着良好的应用背景,但它在算法复杂性上却是NP-困难问题。建立了集合覆盖问题的0-1规划模型,给出了源于贪心思想的近似算法,并从原始-对偶规划的角度进行了证明,基于LINGO软件的传感器网络最优设计案例验证了模型的正确性和算法的有效性。The set cover problem has favourable applications in areas of network design, but it is NP-hard in computational com-plexity. A 0-1 program model is formulated for the set cover problem. An approximation algorithm deriving from greedy idea is put forward, and is proved from the angle of primal-dual program. A case study of sensor network optimal design based on LINGO software demonstrates correctness of the model and effectiveness of the algorithm.

关 键 词：集合覆盖 近似算法 0-1规划 对偶规划 线性交互式通用优化器(LINGO) 

分 类 号：Q784[生物学—分子生物学] TP301.6[自动化与计算机技术—计算机系统结构]