最大独立集问题的算法研究综述
来源：计算机工程与应用杂志2026年第15期北京时间：
作者：颜冬, 王晓峰, 锁小娜, 胡思敏, 宋家欢
单位：1.北方民族大学 计算机科学与工程学院，银川 750021；2.北方民族大学 图形图像智能处理国家民委重点实验室，银川 750021；
摘要：最大独立集问题是典型的NP-难组合优化问题，在无线网络设计、社交网络分析、资源分配与图挖掘等领域具有广泛应用。由于其计算复杂度高，学界针对不同类型的图结构与应用需求，提出了多种启发式、智能优化及机器学习方法以获得高质量近似解。以MIS的研究发展为主线，从启发式算法、智能优化算法和机器学习算法三大范式展开综述，对代表性方法的基本原理、改进思路、性能表现与求解精度进行系统分析，归纳各类算法的优势与局限。结合不同图结构与规模，讨论其适用场景与评测基准，并进一步探讨未来的研究趋势与算法设计方向。
关键词：最大独立集,智能优化算法,启发式算法
基金资助：宁夏自然科学基金（2024AAC03165，2024AAC03169）；宁夏青年拔尖人才项目（2021）。
