Domatic Partition问题的DNA计算方法研究  

Research on DNA Computing Method of Domatic Partition Problem

作　　者：赵洪超[1] 刘希玉[1] 

机构地区：[1]山东师范大学管理科学与工程学院,山东济南250014

出　　处：《微电子学与计算机》2012年第10期152-156,共5页Microelectronics & Computer

基　　金：国家自然科学基金项目(61170038)

摘　　要：Domatic partition问题是一类经典的NP完全问题,在诸多领域中有着广泛的应用,但是至今仍没有多项式时间内的解决方案.DNA计算是一种并行计算能力极强的计算方式,粘贴模型是DNA计算中一种基于粘贴运算的计算模型,基于该模型提出了一种求解domatic partition问题的DNA算法,该算法在多项式的时间内通过两步筛选过程即可以在初始解空间中找出问题的解.为证明该算法的可行性,用java程序对算法进行了仿真模拟,程序在计算机上运行的结果证明此算法是正确且有效的.Domatic partition problem is one of the classical NP complete problems, which is widely used in various areas. However, it has no polynomial time solution so far. DNA computing is a method which has very strong parallel computing power, and the sticker model which is based on the sticker operator is one of the computing models in DNA computing area. In this paper, it puts forward an algorithm based on the sticker model, which can solve the domatic partition problem, and the algorithm can find the feasible solutions through two steps in polynomial time. To prove the feasibility of the algorithm, it uses a java program to simulate the algorithm, and the results of the program running on the computer prove the correctness and the effectiveness of the algorithm.

关 键 词：支配集 domatic PARTITION DNA计算 粘贴模型 

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