论文部分内容阅读
利用最大团问题解空间特殊的结构特征，提出一种基于染色划分构建高维约束指导局部搜索移动方向的改进RLS算法——RLS-Ⅱ算法，该算法提高了局部搜索向最优解靠近的概率．基于吸收态Markov链理论，建立了RLS和RLS-II算法求解最大团问题的数学模型，分析了两种算法的吸收时间，并在77个标准测试算例上对分析结果进行了实验验证．理论分析及实验结果都表明，染色划分过滤确实能够有效改善RLS算法的性能，且平均染色组长度越大，性能改进的概率和幅度就越大．