期刊鉴别 论文检测 免费论文 特惠期刊 学术答疑 发表流程

一种求解Ramsey数的DNA计算机算法

时间:2014-10-20 10:50 文章来源:http://www.lunwenbuluo.com 作者:欧阳丽娜 点击次数:

  摘要:Ramsey数是整个组合数学中最有魅力、最具难度的研究课题。Ramsey的理论知识广泛存在组合数学领域,在锻炼人们逻辑思维和数学思维方面起着重要作用。求解Ramsey数极其困难,到目前为止求解出的Ramsey数只有9个准确值。由于Ramsey数的搜索范围比较广,如果按照以前的传统算法,会导致计算机无法求解。使用DNA计算机算法求解Ramsey数的问题比电子计算机要完善很多。对一种用于求解Ramsey数值的DNA计算模型与算法进行了研究。

  关键词关键词:Ramsey数;DNA计算机算法;编码;解空间; 完全子图; 完全空图

  0 引言

  20世纪30年代,英国著名数学家Ramsey发表了一篇论文,文中对一个组合数学定理进行了证明,这个定理以他的名字命名为Ramsey定理。Ramsey理论在使用数学技术时也促进了数学技术的发展。Ramsey数求解很不容易,针对规模比较大的Ramsey数,如今的方法在传统计算机上很难实现。20世纪90年代,加州节能数学家Adleman,开创了DNA计算机,并且利用DNA计算机求解NP完全的7顶点有向Hamilton路径问题,之后,将DNA计算机和DNA计算模型形成理论计算机学科领域一个新的研究点[1]。本世纪初,其DNA计算已经具有很大的内存与同时运算的功能,从理论上来讲,DAN计算可以克服传统电子计算机内存小和运算慢的一些问题。

  1 Ramsey数

  求解Ramsey数的问题一直受到人们关注,但是人们对Ramsey数的了解很少,因为求解Ramsey数非常困难。如果使用传统计算机遍历方法,需要把不同染色点全部遍历,然而对于范围大的Ramsey数,对应的不同染色点就是天文数字了,根本无法使用传统的计算机遍历方法来进行求解。

  求解Ramsey数的问题,可以说是目前组合数学中的最大问题。以前人们通过理论进行Ramsey数的求解,但是Ramsey数的范围不断扩大,这时候计算机也不能很好地协助了。DNA发展了10多年,求解Ramsey数的DNA计算机算法不断发展,形成了3个子系统 [2],通过每个子系统对理论进行论证,来进一步创建DNA计算机算法求解Ramsey数的模型。

  2 求解Ramsey数的DNA计算模型

  DNA计算模型是Ad leman-Lip none模型与粘贴模型的结合,将两模型的优点结合起来,使其具有了更多优点,比如:随机储存能力强、降低杂交后的错误率低、生化试验可行性高等,这些优点已经使用在DNA计算机算法的子集和、因式分解等一些问题设计中。可以将Ramsey数的问题转化成编码输入在DNA碱基序列里并生成解空间。例如:把一个试管设想成由多个数字组成的集合{1,3,5,7,9},DNA对该试管进行以下操作:抽取、合并、检测、复制、添加、丢弃、读取。 目前很多人都会认为,DNA计算是使用生物学科来进行问题的求解,这种认识似乎也没有错,在DNA计算中,具体模型的设计不仅仅是定量化,更多的还是精确的计算模型。

  3 求解Ramsey数的DNA计算机算法

  3.1 DNA计算机算法思想

  如果要将Ramsey数中的R(m,n)进行求解,首先可以在数学公式中得到R(m,n)的上下界,然后把下界到上界出现的一些问题进行解空间,结合Ramsey数的一些理论及定义,将所有满足条件的部分链删除,对最终的试管进行检查测试,初步了解空间中的DNA所有链有没有全部删除,以此确定现在所得到的值是不是满足要求的Ramsey数。使用这种方法,按照顺序来验证下界到上界中间的每一个数,直到获得R(m,n)的具体数值。求解Ramsey数的DNA计算机算法框架大致为:①对Ramsey数进行生成的解空间,并基于下界;②对解空间中部分完全子图的DAN链进行删除;③对解空间中部分完全空图的DAN链进行删除;④将Ramsey数的结果进行检测和读取。

  3.2 DNA计算机算法

  3.3 求解Ramsey数中R(m,n)的DNA计算机算法


  •   论文部落提供核心期刊、国家级期刊、省级期刊、SCI期刊和EI期刊等咨询服务。
  •   论文部落拥有一支经验丰富、高端专业的编辑团队,可帮助您指导各领域学术文章,您只需提出详细的论文写作要求和相关资料。
  •  
  •   论文投稿客服QQ: 论文投稿2863358778 论文投稿2316118108
  •  
  •   论文投稿电话:15995089042
  •  
  •   论文投稿邮箱:lunwenbuluo@126.com

联系方式

  • 论文投稿客服QQ: 论文投稿2863358778
  • 论文投稿客服QQ: 论文投稿2316118108
  • 论文投稿电话:15995089042
  • 论文投稿邮箱:lunwenbuluo@126.com

热门排行

 
QQ在线咨询
咨询热线:
18915033935
微信号咨询:
15995089042