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

Design of DNA algorithm to construct diagonal Ramsey graph

作　　者：耿修堂[1] 陈智华[1] 

机构地区：[1]华中科技大学控制科学与工程系,武汉430074

出　　处：《计算机应用研究》2009年第3期827-831,共5页Application Research of Computers

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

摘　　要：Ramsey数问题是一个著名的组合优化问题,同时也是一个NP完全问题。构造对角Ramsey图是一个难处理的计算问题,使用穷举的算法来构造对角Ramsey图必然导致计算量的指数爆炸,穷举的DNA算法也不例外。提出了一个构造对角Ramsey图的递阶式DNA粘贴—剪接算法,该算法通过逐个添加顶点的思想,逐步删除了问题的绝大部分非解,在一定程度上缓解了问题解的空间扩散。特别地,专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算分析,分析结果充分地肯定了该算法的有效性。Ramsey number problem is a famous optimization problem,and is also a NP complete problem.So constructing diagonal Ramsey graph is an intractable computation problem.To solve the problem with exhaustion method,the space complexity will grow exponentially,and the instance is similar with primitive DNA algorithm.This paper proposed a recursive DNA sticker-splicing algorithm to construct diagonal Ramsey graph.The proposed algorithm could delete some incorrect solutions by adding the vertices stage by stage.As a...

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]