基于自组装的N皇后问题DNA计算算法  

An Algorithm in Tile Assembly Model for N Queen Problem

作　　者：吴帆[1] 李肯立[1] 

机构地区：[1]湖南大学信息科学与工程学院,湖南长沙410082

出　　处：《电子学报》2013年第11期2174-2180,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.90715029;No.61070057);湖南省科技计划(No.2012WK3053)

摘　　要：N皇后问题是理论计算机科学中一个经典的NP难问题.自Adleman首次运用DNA计算来解决NP问题以来,DNA计算已成为计算机科学的研究热点之一,现有N皇后问题的DNA计算机算法多基于粘贴和剪接模型,存在生化操作复杂度和实验误差较高等问题.本文提出了一种基于DNA自组装模型来求解N皇后问题的DNA计算方法.算法通过减少实验操作步骤数,降低了生化解的错误率.算法使用的tiles分子块种类为O(n2),生化操作复杂性为O(1),其中n为皇后的个数.与求解N皇后问题的其它DNA算法的对比分析表明,本算法可提高生化解的准确性,降低算法生化实验的复杂度,具有良好的易操作性.DNA computing employs molecule manipulation to solve NP complete problems that can not be solved using tra-ditional Turing machine .With the deep studying of DNA computing ,we found that DNA computation suffers from relatively high error rates .How to decrease error rates has become an important part of DNA computing .This paper present DNA self-assembly model which decreases error rates through decreasing experiment operations .A new N Queen problem algorithm based on the self assembly model is proposed .The proposed algorithm needs O （ n2 ） types of tiles and the complexity of experiment operations is O （1 ） .Obviously ,this algorithm significantly reduces the complexity of the experiment ,thus improving the accuracy of experimen-tal results .

关 键 词：DNA计算 自组装模型 N皇后问题 tile模型 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]