摘 要 Ramsey作为计算机中常见的一种数学组合理论依据，其主要是由庞大的组合数学而构成，随着计算机信息技术的推广，它在代数学、逻辑学以及分析学等方面的应用也越来越广泛。Ramsey求解是一个相对比较困难的部分，到目前为止，由关于这方面的研究，只能求出9个Ramsey数的准确值。而本文研究的主要目的是探讨Ramsey数字求解在DNA生物分子超级计算模型中的求解可能性，通过具体数据模型的计算，以证明其应用的可靠性。希望通过本文的分析能实现提Ramsey的推广和普及。
【关键词】DNA计算机算法 Ramsey数的求解
Ramsey定理最早由英国Ramsey提出，发表论文中的组合数字定理证明之后引起了数学家们的注意。任意给出的两个正整数k与l，一定能找到最小数n。Ramsey的研究在数学技术有重要意义，它采用了很多技术，目前，求解大的Ramsey数还很难实现。随着计算机越来越快速发展，以往通过图解的方式，也开始由计算机所取代，其中DNA遗传算法等被很快应用其中。它的优点很多，例如步骤少，可行性很高，并且错误率比一般算法相比低很多等。
1 Ramsey数的研究发展与意义
1.1 Ramsey的由来
Ramsey定理最早由数学家提出，发表于他的“On a problem of fomal logic”论文中，这篇论文里证明了Ramsey定理，是一个组合数字定理。起初的Ramsey默默无闻，直到一篇题为“A combinatorial problem in geometry”论文的横空出世，Ramsey定理才开始声名鹊起。7973年为庆祝论文其中一名作者的生日召开的组合数字会议，最终成为Ramsey的里程碑，更多的数学家涌入这一理论的研究，不断用新的理论和方法来丰富Ramsey定理。
1.2 Ramsey的发展和应用
现在Ramsey已经涉及到多个学科，其中包括数学、数论、数理逻辑、计算数学、图论、泛函分析等各种方面，更有甚者将数学归纳法与Ramsey相提并论，这已经证明了Ramsey理论研究的重要意义。而Ramsey理论也蕴含着一个深刻的哲学思想，就是当量到达一种程度时会出现某种结构，这种结构必然是有序的，其中必定出现某种量的最小值就是Ramsey数。
Ramsey理论的研究被广泛应用，它的结果也被越来越多的领域利用做其他方面的研究，例如1998年Fields奖的获得者就把Ramsey理论应用到泛函分析，在Banach空间以及极值组合论做出了重大贡献。
2 DNA计算机算法对于Ramsey数的求解模理论建立分析
2.1 课题研究意义
传统Ramsey研究方法如寻找循环图和Cayley图等方式通常都无法得到较大的的Ramsey精确值，只能得到它的上下界。因为这种传统计算方式的局限性，还有Ramsey本身研究的困难性，计算机研究Ramsey数的方法理所当然的产生。模拟退火算法、DNA遗传算法都是比较常用的Ramsey数研究办法，而本文主要讲述DNA计算机算法对于Ramsey数的求解研究分析。
2.2 计算方法
DNA遗传算法这种新型的计算方法，主要以DNA与一些相关生物酶等元素做基本材料，是基于生化反应的原理得出的分子生物计算方式。现在，已经有很多学者投入这一研究领域。最早的DNA算法于1994年由Adleman开创。1995年Lipton，1997年Ouyang，2006年Li等人相继提出更多问题的DNA算法研究。
不论哪种DNA计算方式，通常第一步会生成一个包含正确和不正确解的初始数据池，使用对应的DNA计算法来去除不正确的，然后检测出正确的解，就是DNA操作中所得到的问题的解。只是这种方式受到各种规模限制，而且会导致DNA指数上涨。现今，用计算机求解Ramsey成为了一种趋势，但是在求解较大Ramsey数方面，仍然是非常复杂的，需要的时间也很久。
3 Ramsey数的DNA计算机算法问题及思想
3.1 Ramsey数的计算原理
以数学上原本存在的公式可以得出R（m，n）上下界，从下界到上界的过程中产生的解空间，除去部分的链，检测最终试管，如果初始空间DNA链都被删除，当前值就可以确定为要求的Ramsey数。可以用这种方法验证上下界间的每一个数，得出具体R（m，n）。
3.2 关键环节
找到一种好的选边策略是快速计算的关键。Ramsey问题可以归结成为一个NP完全问题，最终转化为图着色问题，也就是多顶点便之间的双染色问题，以非解4（3，3）的排除验证为例，即证明任意4个人中要么至少3个人认识，要么至少3个不认识，此命题明显是不正确的。
现已确定R（5，5）是43-49之间的某一个数字。假设我们要用此算法验证 43（5，5）是否为正解，则可以将所有5边形看作顶点设计Origami，所有的C43共903条边都设计成2种颜色。之后将尽量多的点和边混合到一起，相当于搜索边中每一个可能的解。顶点处进行Origami荧光特异性设计，只能连接指定的边并且当N个边的颜色相同时便呈现荧光。这样若43为非解时，便会出现大片不显荧光的组合，即可排除结论。
4 结论
本文主要运用理论知识与小规模排除为例，简单说明了DNA计算机算法在Ramsey数理论上的运用和意义。为Ramsey数的求解提供创新的思路，但由于现有技术的局限性，该算法上可解的Ramsey数仍然有限，随着各方面条件的成熟，DNA计算机算法对于Ramsey数的求解一定会更加完善。
参考文献
[1]宋智超.一种基于DNA折纸术求解Ramsey数的算法[J].电源技术应用，2013（7）.
[2]郭里.若干图论问题的DNA计算机算法研究[D].湖南大学，2009.
作者简介
徐智杰（1985-），男，大学本科学历。现为山西金融职业学院助教。研究方向为计算机科学与技术。
中国论文网(www.lunwen.net.cn)免费学术期刊论文发表,目录,论文查重入口,本科毕业论文怎么写,职称论文范文,论文摘要,论文文献资料,毕业论文格式,论文检测降重服务。 返回电子论文列表
