构造对角Ramsey图的DNA算法设计*

Ramsey数问题是一个著名的组合优化问题, 同时也是一个NP完全问题。构造对角Ramsey图是一个难处理的计算问题，使用穷举的算法来构造对角Ramsey图必然导致计算量的指数爆炸，穷举的DNA算法也不例外。提出了一个构造对角Ramsey图的递阶式DNA粘贴—剪接算法，该算法通过逐个添加顶点的思想, 逐步删除了问题的绝大部分非解，在一定程度上缓解了问题解的空间扩散。特别地, 专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算分析, 分析结果充分地肯定了该算法的有效性。

Design of DNA algorithm to construct diagonal Ramsey graph

Ramsey number problem is a famous optimization problem, and is also a NP complete problem. So constructing diagonal Ramsey graph is an intractable computation problem. To solve the problem with exhaustion method, the space complexity will grow exponentially, and the instance is similar with primitive DNA algorithm. This paper proposed a recursive DNA sticker-splicing algorithm to construct diagonal Ramsey graph. The proposed algorithm could delete some incorrect solutions by adding the vertices stage by stage. As a result, the proposed algorithm relieved the need of space computation. Parti-cularly, computational complexity of the presented algorithm was analyzed with the construction of Ramsey graph with 43 ver-tices for R(5,5). The analysis results of the algorithm show that the presented algorithm is effective.