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

DNA计算机算法对于Ramsey数的求解研究 　　摘 要 Ramsey作为计算机中常见的一种数学组合理论依据，其主要是由庞大的组合数学而构成，随着计算机信息技术的推广，它在代数学、逻辑学以及分析学等方面的应用也越来越广泛。Ramsey求解是一个相对比较困难的部分，到目前为止，由关于这方面的研究，只能求出9个Ramsey数的准确值。而本文研究的主要目的是探讨Ramsey数字求解在DNA生物分子超级计算模型中的求解可能性，通过具体数据模型的计算，以证明其应用的可靠性。希望通过本文的分析能实现提Ramsey的推广和普及。 　　【关键词】DNA计算机算法 Ramsey数的求解 　　Ramsey定理最早由英国Ramsey提出，发表论文中的组合数字定理证明之后引起了数学家们的注意。任意给出的两个正整数k与l，一定能找到最小数n。Ramsey的研究在数学技术有重要意义，它采用了很多技术，目前，求解大的Ramsey数还很难实现。随着计算机越来越快速发展，以往通过图解的方式，也开始由计算机所取代，其中DNA遗传算法等被很快应用其中。它的优点很多，例如步骤少，可行性很高，并且错误率比一般算法相比低很多等。 　　1 Ramsey数的研究发展与意义 　　1.1 Ramsey的由来 　　Ramsey定理最早由数学家F.R.Ramsey提出，发表于他的“On a problem of fomal logic”论文中，这篇论文里证明了Ramsey定理，是一个组合数字定理。起初的Ramsey默默无闻，直到一篇题为“A combinatorial problem in geometry”论文的横空出世，Ramsey定理才开始声名鹊起。7973年为庆祝论文其中一名作者P.Eraos的生日召开的组合数字会议，最终成为Ramsey的里程碑，更多的数学家涌入这一理论的研究，不断用新的理论和方法来丰富Ramsey定理。 　　1.2 Ramsey的发展和应用 　　现在Ramsey已经涉及到多个学科，其中包括数学、数论、数理逻辑、计算数学、图论、泛函分析等各种方面，更有甚者将数学归纳法与Ramsey相提并论，这已经证明了Ramsey理论研究的重要意义。而Ramsey理论也蕴含着一个深刻的哲学思想，就是当量到达一种程度时会出现某种结构，这种结构必然是有序的，其中必定出现某种量的最小值就是Ramsey数。 　　Ramsey理论的研究被广泛应用，它的结果也被越来越多的领域利用做其他方面的研究，例如1998年Fields奖的获得者W.T.Gowers就把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个不认识