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

An Surface-based DNA Algorithm for the Hamilton Circuit Problem

作　　者：方俊[1] 潘勇[1] 

机构地区：[1]湖南长沙民政职业技术学院软件学院,长沙410004

出　　处：《计算机工程与应用》2006年第30期62-64,71,共4页Computer Engineering and Applications

摘　　要：基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。论文采用荧光标记的策略,给出了一种新的哈密顿回路问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得哈密顿回路问题的所有解。在新模型中,解空间的生成过程与边的排列顺序无关。Biochemical reaction theory based DNA computation is of the massive inherent parallelism,so compared to silicon computer,DNA computer has most superiority out and away on NP problems.This paper purposes a new DNA algorithm of the Hamilton circuit problem based surface by using the method of fluorescence labeling.The DNA molecules of the solution space are fixed on the solid carrier,and then we get the all solutions of the perfect matching problem by the biochemical actions.In the new module,the edges order hasn＇t influence on the solution generating process .

关 键 词：DNA计算 表面方式 解空间 哈密顿回路 

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