一种求解图论中最大独立集问题的启发式算法

摘要

最大独立集问题是著名的NP-hard问题,在许多领域都有广泛的实际应用.在给定无向图G=(V,E)中,最大独立集是顶点V的一个子集I,I中顶点的数量最大且任意2个顶点都不相邻.本文提出了一种启发式的最大独立集问题算法RI-DS-TS,本算法由3部分组成:随机初始化,基于度与支撑的顶点挑选,基于禁忌搜索的独立集优化.本文给出了RI-DS-TS算法的具体步骤,并使用DIMACS基准中的实例对RI-DS-TS算法进行了验证,通过和目前已知的最优结果对比,本算法在满足经济性的同时取得了令人满意的效果.