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

作     者：耿修堂 陈智华 GENG Xiu-tang;CHEN Zhi-hua

作者机构：华中科技大学控制科学与工程系武汉430074 

基　　金：国家自然科学基金资助项目(60373089 60674106 60533010) 

出 版 物：《计算机应用研究》 (Application Research of Computers)

年 卷 期：2009年第26卷第3期

页      码：827-831页

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

主 题 词：DNA计算 Ramey图 NP完全问题 粘贴模型 剪接模型 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1001-3695.2009.03.007

馆 藏 号：203818053...