经典Ramsey数DNA计算模型(Ⅰ):位序列计算模型  

Classical Ramsey Number DNA Computing Model(Ⅰ):Add-Bit-Sequence Model

作　　者：许进[1,2] 范月科[2] 

机构地区：[1]北京大学信息科学技术学院高可信软件技术教育部重点实验室,北京100871 [2]华中科技大学分子生物计算机研究所,武汉430074

出　　处：《计算机学报》2008年第12期2073-2080,共8页Chinese Journal of Computers

摘　　要：Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一.对于经典Ramsey数,至今只有9个Ramsey数得到解决.按照传统的算法,其搜索空间太大,当前的电子计算机无法胜任.研究表明,DNA计算在求解困难的NP-完全问题上优于电子计算机.目前已经建立了众多求解NP-完全问题的DNA计算模型,但未见到用于求解Ramsey数的DNA计算模型.作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解.全文共分两篇,该文属首篇,建立了一种可适用于DNA计算模式的所谓的求解Ramsey数的位序列计算模型,其中的位序列是以图的相邻矩阵下三角阵中行从左到右、列从上到下的排列次序.文中重点对该模型的机理与使用方法进行了分析研究.Classical Ramsey number problem is a NP complete problem. It takes exponential time to solve classical Ramsey number problem with traditional electronics computer. It is necessary to study new computation methods because traditional electronics computer faces with greatly difficulty in solving NP complete problem. DNA computing possesses high parallelism in data and higher storage capacity than normal systems. Hence, in theory, it is feasible to solve NP complete problems with DNA computing. A novel method is proposed and used to solve the classical Ramsey number problem in this paper. Firstly, a method for DNA sequence code based on graphic sequence is presented. In order to reflect all possible information of p-order graphs, it is focused on the encoding of p-order complete graph. The number of the edges in the graph is p ＊ （p-- 1）/2!. The delta-encoding method is selected. The sequences of encodings are the edges 1,2,…, p＊（p-1）/2!. Here, the edges 1,2,.--,p~ （p--1）/2! represent adjacent lower triangular matrix array in order from left to right, top to bottomin the graph G. The character of this encoding is to sort them into p-1 classes, and the edges in the i class are composed of {v1 ,vm＋1 }, {v2,vi＋1,…, {vi,vi＋l}, i=1,2,…,p-1. According to the encoding, the length p… （p-1）/2! of 0-1 sequence can be mapped to all labeled sub-graphs with p vertexes. It means that arbitrary 0-1 sequence with length p＊ （p-1）/2! corresponds to the graph with the order p; On the other hand, any order p for the labeled graph corresponds to 0-1 seouence with length 9 ＊ （9-1）/21.Secondly, some problems are discussed, such as the set problem of labeling sub-graph and un-labeling sub-graph, especial the method of sequence denoted. Finally, in order to delete the incorrect solutions in the first, the idea, method and process of deleting incorrect solutions are presented, and an instance is presented to illuminate the proposed method. The basic idea is to construct a graph by bit by step. In

关 键 词：经典RAMSEY数 DNA计算 位序列计算模型 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]