求解集合覆盖问题的离散动态凸化方法

作者：刘秀梅; 欧阳菲

来源：宁德师范学院学报(自然科学版), 2019, 31(02): 120-133.

DOI：10.15911/j.cnki.35-1311/n.2019.02.005

• 集合覆盖
• 离散全局极小解
• 罚函数
• 辅助函数

集合覆盖问题是一个基本的组合优化问题,它是NP(多项式复杂程度的非确定性)完全问题.通过罚函数把问题转化为一个无约束最优化问题,给出一个辅助函数.它和问题有相同的离散全局极小解,设计一个算法,通过极小化该辅助函数得到问题的一个近似离散全局极小解.数值试验表明,算法对求解集合覆盖问题是有效的.