| 一种求解集合覆盖问题的启发式算法 |
| |
| 引用本文： | 陈端兵 黄文奇. 一种求解集合覆盖问题的启发式算法[J]. 计算机科学, 2007, 34(4): 133-136 |
| |
| 作者姓名： | 陈端兵 黄文奇 |
| |
| 作者单位： | 华中科技大学计算机科学与技术学院,武汉430074;华中科技大学计算机科学与技术学院,武汉430074 |
| |
| 基金项目： | 国家自然科学基金 , 国家重点基础研究发展计划(973计划) |
| |
| 摘 要： | 集合覆盖问题是运筹学研究中的一个基本的组合优化问题,它通常描述成如下的一个覆盖问题:从一个m行、n列的0-1矩阵(aij)m×n中选出若干列盖住所有的行,使得付出的代价最小.集合覆盖问题被广泛应用到航空人员行程安排、电路设计、运输的车辆路线安排等领域.对这一问题,国内外学者提出了诸如遗传算法、模拟退火算法、蚁群算法、人工神经网络算法等求解算法.本文以贪心算法为基础,利用人类的智慧和经验,提出了一种求解集合覆盖问题的启发式算法.算法的主要思想为:从某个解出发,随机移除一定比例的列,再用贪心策略加入若干列.用本文提出的算法,对Beasley提出的45个测试实例进行了实算测试,所得结果和最优解的平均相对差值为0.44%,并且得到了其中33个实例的最优解,实算结果表明,本文提出的算法对求解集合覆盖问题是行之有效的.
|
| 关 键 词： | 集合覆盖 启发式算法 贪心策略 随机跳坑 |
A Heuristic Algorithm for Set Covering Problem |
| |
| CHEN Duan-Bing,HUANG Wen-Qi (School of Computer Science,Huazhong University of Science and Technology,Wuhan. A Heuristic Algorithm for Set Covering Problem[J]. Computer Science, 2007, 34(4): 133-136 |
| |
| Authors: | CHEN Duan-Bing HUANG Wen-Qi (School of Computer Science Huazhong University of Science Technology Wuhan |
| |
| Affiliation: | School of Computer Science, Huazhong University of Science and Technology, Wuhan 430074 |
| |
| Abstract: | |
| |
| Keywords: | Set covering problem Heuristic algorithm Greedy strategy Random off-trap |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
