arXiv:2208.07777v3 公告类型: 替换 摘要：最大独立集（MIS）问题是广泛应用于各种领域的已知NP完全问题。启发式方法常被用来高效地处理这一问题的大规模实例，在合理的时间内提供高质量的解决方案。然而，启发式方法面临诸如陷入局部最优和在解空间内进行冗余搜索的挑战。本文介绍了一种高效解决MIS问题的启发式算法，结合了两项创新技术。第一项技术是一种递归评估机制，用于监测解决方案的进展情况并识别局部最优，触发重新启动以避免收敛到次优结果。第二项技术利用基于采样的推理规则有选择地固定顶点，从而缩小搜索空间并提高效率。在多个广泛认可的真实世界基准测试中的全面实验评估表明，所提出的算法在解决方案质量、计算效率和稳定性方面优于最先进的算法。