周炎涛，李肯立，罗 兴，黎福海，朱 青

（1.湖南大学 电气与信息工程学院，湖南 长沙 410082； 2.湖南大学 信息科学与工程学院，湖南 长沙 410082）

最大团问题（Maximum clique problem，MCP）又称为最大独立集问题，是图论中的一个经典组合优化问题，也是一类NP完全问题[1].求解MCP算法主要有二类：确定性算法和启发式算法，前者有回溯法、分支限界法等 .随着问题规模的增大（顶点增多和边密度变大），求解问题的时间复杂度越来越高，确定性算法显得无能为力，不能有效地解决这些NP完全问题 .后者有蚁群算法、顺序贪婪算法、DLS－MC算法和智能搜索算法等，大部分确定性算法所不能解决的图，用启发式算法都能得到有效解决，但启发式算法不一定能找到最优解，有时只能找到近似值[2].近年来，常借鉴算法之间优势互补策略，形成新的混合启发式算法来求解最大团问题[3].

DNA计算是应用分子生物技术进行计算的新方法，具有高度并行性、大容量、低能耗等特点，为解决NP完全问题开辟了一条新途径[4].自Adleman首次运用DNA计算来解决NP问题以来[5]，研究者对最大团问题的分子求解方法进行了很多有益的尝试，如基于粘贴模型的最大团问题算法[6]、质粒DNA算法[7]、闭环求解最大团问题算法[8]等，但这些方法均存在实验操作步骤过多、活体内不易操作以及环化效率不高等弊端.此外，Brun采用自组装DNA计算给出了路径寻找问题[9]，以及可满足性问题的自组装计算模型的解决方案[10].文献[11]在分布式系统中建立自组装模型解决自由等……