构造对角Ramsey图的DNA算法设计

• 作者: 耿修堂 陈智华
• 来源期刊: 计算机应用研究
• 关键词: DNA计算 Ramey图 NP完全问题 粘贴模型 剪接模型
• 年，卷（期）: 2009,（3）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 827-831
• 页数: 5页
• 分类号: TP183
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2009.03.007

摘要

Ramsey数问题是一个著名的组合优化问题, 同时也是一个NP完全问题.构造对角Ramsey图是一个难处理的计算问题,使用穷举的算法来构造对角Ramsey图必然导致计算量的指数爆炸,穷举的DNA算法也不例外.提出了一个构造对角Ramsey图的递阶式DNA粘贴-剪接算法,该算法通过逐个添加顶点的思想, 逐步删除了问题的绝大部分非解,在一定程度上缓解了问题解的空间扩散.特别地, 专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算分析, 分析结果充分地肯定了该算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	耿修堂	华中科技大学控制科学与工程系	6	33	3.0	5.0
2	陈智华	华中科技大学控制科学与工程系	18	53	5.0	6.0