(华中科技大学 控制科学与工程系, 武汉 430074)
摘 要:Ramsey数问题是一个著名的组合优化问题, 同时也是一个NP完全问题。构造对角Ramsey图是一个难处理的计算问题,使用穷举的算法来构造对角Ramsey图必然导致计算量的指数爆炸,穷举的DNA算法也不例外。提出了一个构造对角Ramsey图的递阶式DNA粘贴—剪接算法,该算法通过逐个添加顶点的思想, 逐步删除了问题的绝大部分非解,在一定程度上缓解了问题解的空间扩散。特别地, 专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算分析, 分析结果充分地肯定了该算法的有效性。
关键词:DNA计算; Ramey图; NP完全问题; 粘贴模型; 剪接模型
Design of DNA algorithm to construct diagonal Ramsey graph
GENG Xiutang, CHEN Zhihua
(Dept. of Control Science & Engineering, Huazhong University of Science & Technology, Wuhan 430074, China)
Abstract: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 stickersplicing 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. Particularly, computational complexity of the presented algorithm was analyzed with the construction of Ramsey graph with 43 vertices for R(5,5). The analysis results of the algorithm show that the presented algorithm is effective. ......