| 集合覆盖问题的模型与算法 |
| |
| 引用本文： | 王继强. 集合覆盖问题的模型与算法[J]. 计算机工程与应用, 2013, 49(17): 15-17 |
| |
| 作者姓名： | 王继强 |
| |
| 作者单位： | 山东财经大学 数学与数量经济学院，济南 250014 |
| |
| 摘 要： | 集合覆盖问题在网络设计领域中有着良好的应用背景，但它在算法复杂性上却是NP-困难问题。建立了集合覆盖问题的0-1规划模型，给出了源于贪心思想的近似算法，并从原始-对偶规划的角度进行了证明，基于LINGO软件的传感器网络最优设计案例验证了模型的正确性和算法的有效性。
|
| 关 键 词： | 集合覆盖 近似算法 0-1规划 对偶规划 线性交互式通用优化器（LINGO） |
Model and algorithm for set cover problem |
| |
| WANG Jiqiang. Model and algorithm for set cover problem[J]. Computer Engineering and Applications, 2013, 49(17): 15-17 |
| |
| Authors: | WANG Jiqiang |
| |
| Affiliation: | School of Mathematics and Quantitative Economics, Shandong University of Finance and Economics, Jinan 250014, China |
| |
| Abstract: | The set cover problem has favourable applications in areas of network design, but it is NP-hard in computational complexity. 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. |
| |
| Keywords: | set cover approximation algorithm 0-1 program dual program Linear Interactive and General Optimizer（LINGO） |
|
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
