作者：陈端兵; 黄文奇集合覆盖启发式算法贪心策略随机跳坑
摘要：集合覆盖问题是运筹学研究中的一个基本的组合优化问题，它通常描述成如下的一个覆盖问题：从一个m行、n列的0—1矩阵（aij）m×n中选出若干列盖住所有的行，使得付出的代价最小。集合覆盖问题被广泛应用到航空人员行程安排、电路设计、运输的车辆路线安排等领域。对这一问题，国内外学者提出了诸如遗传算法、模拟退火算法、蚁群算法、人工神经网络算法等求解算法。本文以贪心算法为基础，利用人类的智慧和经验，提出了一种求解集合覆盖问题的启发式算法。算法的主要思想为：从某个解出发，随机移除一定比例的列，再用贪心策略加入若干列。用本文提出的算法，对Beasley提出的45个测试实例进行了实算测试，所得结果和最优解的平均相对差值为0．44％，并且得到了其中33个实例的最优解，实算结果表明，本文提出的算法对求解集合覆盖问题是行之有效的。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
