DNA计算机算法对于Ramsey数的求解研究

1、    dna计算机算法对于ramsey数的求解研究    摘 要 ramsey作为计算机中常见的一种数学组合理论依据，其主要是由庞大的组合数学而构成，随着计算机信息技术的推广，它在代数学、逻辑学以及分析学等方面的应用也越来越广泛。ramsey求解是一个相对比较困难的部分，到目前为止，由关于这方面的研究，只能求出9个ramsey数的准确值。而本文研究的主要目的是探讨ramsey数字求解在dna生物分子超级计算模型中的求解可能性，通过具体数据模型的计算，以证明其应用的可靠性。希望通过本文的分析能实现提ramsey的推广和普及。【关键词】dna计算机算法 r

2、amsey数的求解ramsey定理最早由英国ramsey提出，发表论文中的组合数字定理证明之后引起了数学家们的注意。任意给出的两个正整数k与l，一定能找到最小数n。ramsey的研究在数学技术有重要意义，它采用了很多技术，目前，求解大的ramsey数还很难实现。随着计算机越来越快速发展，以往通过图解的方式，也开始由计算机所取代，其中dna遗传算法等被很快应用其中。它的优点很多，例如步骤少，可行性很高，并且错误率比一般算法相比低很多等。1 ramsey数的研究发展与意义1.1 ramsey的由来ramsey定理最早由数学家f.r.ramsey提出，发表于他的“on a problem of fo

3、mal logic”论文中，这篇论文里证明了ramsey定理，是一个组合数字定理。起初的ramsey默默无闻，直到一篇题为“a combinatorial problem in geometry”论文的横空出世，ramsey定理才开始声名鹊起。7973年为庆祝论文其中一名作者p.eraos的生日召开的组合数字会议，最终成为ramsey的里程碑，更多的数学家涌入这一理论的研究，不断用新的理论和方法来丰富ramsey定理。1.2 ramsey的发展和应用现在ramsey已经涉及到多个学科，其中包括数学、数论、数理逻辑、计算数学、图论、泛函分析等各种方面，更有甚者将数学归纳法与ramsey相提并论，

4、这已经证明了ramsey理论研究的重要意义。而ramsey理论也蕴含着一个深刻的哲学思想，就是当量到达一种程度时会出现某种结构，这种结构必然是有序的，其中必定出现某种量的最小值就是ramsey数。ramsey理论的研究被广泛应用，它的结果也被越来越多的领域利用做其他方面的研究，例如1998年fields奖的获得者w.t.gowers就把ramsey理论应用到泛函分析，在banach空间以及极值组合论做出了重大贡献。2 dna计算机算法对于ramsey数的求解模理论建立分析2.1 课题研究意义传统ramsey研究方法如寻找循环图和cayley图等方式通常都无法得到较大的的ramsey精确值，只能

5、得到它的上下界。因为这种传统计算方式的局限性，还有ramsey本身研究的困难性，计算机研究ramsey数的方法理所当然的产生。模拟退火算法、dna遗传算法都是比较常用的ramsey数研究办法，而本文主要讲述dna计算机算法对于ramsey数的求解研究分析。2.2 计算方法dna遗传算法这种新型的计算方法，主要以dna与一些相关生物酶等元素做基本材料，是基于生化反应的原理得出的分子生物计算方式。现在，已经有很多学者投入这一研究领域。最早的dna算法于1994年由adleman开创。1995年lipton，1997年ouyang，2006年li等人相继提出更多问题的dna算法研究。不论哪种dna计

6、算方式，通常第一步会生成一个包含正确和不正确解的初始数据池，使用对应的dna计算法来去除不正确的，然后检测出正确的解，就是dna操作中所得到的问题的解。只是这种方式受到各种规模限制，而且会导致dna指数上涨。现今，用计算机求解ramsey成为了一种趋势，但是在求解较大ramsey数方面，仍然是非常复杂的，需要的时间也很久。3 ramsey数的dna计算机算法问题及思想3.1 ramsey数的计算原理以数学上原本存在的公式可以得出r（m，n）上下界，从下界到上界的过程中产生的解空间，除去部分的链，检测最终试管，如果初始空间dna链都被删除，当前值就可以确定为要求的ramsey数。可以用这种方法验

7、证上下界间的每一个数，得出具体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郭里.若干图