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个不认识，此命题明显是不正确的。

现已确定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-），男，大学本科学历。现为山西金融职业学院助教。研究方向为计算机科学与技术。

作者单位

山西金融职业学院 山西省太原市 030008