互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

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


□ 耿修堂 陈智华

  (华中科技大学 控制科学与工程系, 武汉 430074)
  
  摘 要:Ramsey数问题是一个著名的组合优化问题, 同时也是一个NP完全问题。构造对角Ramsey图是一个难处理的计算问题,使用穷举的算法来构造对角Ramsey图必然导致计算量的指数爆炸,穷举的DNA算法也不例外。提出了一个构造对角Ramsey图的递阶式DNA粘贴—剪接算法,该算法通过逐个添加顶点的思想, 逐步删除了问题的绝大部分非解,在一定程度上缓解了问题解的空间扩散。特别地, 专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算分析, 分析结果充分地肯定了该算法的有效性。
  关键词:DNA计算; Ramey图; NP完全问题; 粘贴模型; 剪接模型
  中图分类号:TP183 文献标志码:A
   文章编号:10013695(2009)03082705
  
  Design of DNA algorithm to construct diagonal Ramsey graph
  
  GENG Xiutang, CHEN Zhihua
  
  (Dept. of Control Science & Engineering, Huazhong University of Science & Technology, Wuhan 430074, China)
  
  Abstract: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 stickersplicing algorithm to construct diagonal Ramsey graph. The proposed algorithm could delete some incorrect solutions by adding the vertices stage by stage. As a result, the proposed algorithm relieved the need of space computation. Particularly, computational complexity of the presented algorithm was analyzed with the construction of Ramsey graph with 43 vertices for R(5,5). The analysis results of the algorithm show that the presented algorithm is effective. ......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017