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

• 作者: 吴帆 李肯立
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: DNA计算 自组装模型 N皇后问题 tile模型
• 年，卷（期）: 2013,（11）
• 所属期刊栏目: 学术论文
• 页码范围: 2174-2180
• 页数: 7页
• 分类号: TP3
• 字数: 4684字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2013.11.010

摘要

N皇后问题是理论计算机科学中一个经典的NP难问题。自Adleman首次运用DNA计算来解决NP问题以来，DNA计算已成为计算机科学的研究热点之一，现有 N皇后问题的DNA计算机算法多基于粘贴和剪接模型，存在生化操作复杂度和实验误差较高等问题。本文提出了一种基于DNA自组装模型来求解N皇后问题的DNA计算方法。算法通过减少实验操作步骤数，降低了生化解的错误率。算法使用的tiles分子块种类为 O （ n2），生化操作复杂性为O（1），其中 n为皇后的个数。与求解 N皇后问题的其它DNA算法的对比分析表明，本算法可提高生化解的准确性，降低算法生化实验的复杂度，具有良好的易操作性。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李肯立	湖南大学信息科学与工程学院	130	931	16.0	22.0
2	吴帆	湖南大学信息科学与工程学院	5	48	3.0	5.0