哈密尔顿回路问题的DNA表面计算模型  

Surface-based DNA algorithm for Hamiltonian path problem

作　　者：李朝鹏[1,2] 成运[1] 李肯立[2] 周旭[3] 

机构地区：[1]湖南人文科技学院通信与控制工程系,湖南娄底417000 [2]湖南大学计算机与通信学院,长沙410082 [3]嘉兴学院数学与信息学院,浙江嘉兴314001

出　　处：《计算机工程与应用》2010年第8期48-51,共4页Computer Engineering and Applications

基　　金：国家自然科学基金Grant No.60603053;国家自然科学基金重大项目Grant No.90715029;湖南省重点建设学科项目;湖南省教育厅项目 Grant No.09C546~~

摘　　要：首次提出用DNA表面计算模型来解决无向图哈密尔顿回路问题。该模型基于哈密尔顿回路问题的解空间,将问题解空间的DNA分子固定在固体载体上,对其进行荧光标记,然后通过相应的生化反应筛选出哈密尔顿回路问题的所有解。与已有的哈密尔顿路径问题的其它模型相比,新模型具有错误率低,编码简易,读取方便等更好的性能。The paper innovatively presents a surface-based DNA algorithm for solving Hamiltonian circuit problem in a nondirectional graph.The model,based on the solution space of Hamihonian problem,fixes the DNA molecules of solution space on the solid carrier,and fluorescence labels on them,and then gets all solutions of Hamiltonian circuit problem by certain biochemical actions.Compared with other models for Hamiltonian path problem,this model shows better performances on low rate of error,easily coding and conveniency to read.

关 键 词：DNA超级计算 表面计算模型 NP完全问题 哈密尔顿回路问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]