%0 Journal Article
%T 基于自组装的N皇后问题DNA计算算法
%A 吴帆
%A 李肯立
%J 电子学报
%P 2174-2180
%D 2013
%R 10.3969/j.issn.0372-2112.2013.11.010
%X N皇后问题是理论计算机科学中一个经典的NP难问题.自Adleman首次运用DNA计算来解决NP问题以来，DNA计算已成为计算机科学的研究热点之一，现有N皇后问题的DNA计算机算法多基于粘贴和剪接模型，存在生化操作复杂度和实验误差较高等问题.本文提出了一种基于DNA自组装模型来求解N皇后问题的DNA计算方法.算法通过减少实验操作步骤数，降低了生化解的错误率.算法使用的tiles分子块种类为O（n2），生化操作复杂性为O（1），其中n为皇后的个数.与求解N皇后问题的其它DNA算法的对比分析表明，本算法可提高生化解的准确性，降低算法生化实验的复杂度，具有良好的易操作性.
%K DNA计算
%K 自组装模型
%K N皇后问题
%K tile模型
%U http://www.ejournal.org.cn/CN/abstract/abstract8123.shtml