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

　　摘要：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计算机算法

　　如p为R（m，n）的下界，使用生成解空间的DNA计算机算法，由q顶点中的完全图的边穷举生成解空间，然后使用删除完全子图的DNA计算机算法和删除完全空图的DNA计算机算法将满足规定条件的链删除，最终将生成试管，检查测试最终的试管，看它是不是包含DNA链，来对R（m，n）是否等于p进行判断[3]。在DNA计算机算法中求解Ramsey数，是将生成解空间的DNA计算机算法、删除完全子图的DNA计算机算法、删除完全空图的DNA计算机算法与检测子算法相结合论文发表成一个整体来求解的。

　　DNA计算机算法的性能指标包括：生物的复杂性、算法中需要使用到的DNA分子链的数量与链的长度、测试试管数、杂交错误率等。

　　4 编码问题对DNA计算的影响

　　DNA计算中最主要的是编码问题，原因有：①DNA计算中序列的合成质量与编码有直接联系；②DNA计算能不能按照最初设计的目标进行，编码质量具有直接影响；③解空间的大小受编码质量的影响；④在DNA计算中最主要的难点是检测解。