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

吴帆; 李肯立

doi:10.3969/j.issn.0372-2112.2013.11.010

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-07-16

- 基于自组装的N皇后问题DNA计算算法
- An Algorithm in Tile Assembly Model for N Queen Problem
- 电子学报 2013年41卷第11期页码：2174-2180
- 作者机构：
  
  湖南大学信息科学与工程学院,湖南,长沙,410082
- 作者简介：
- 基金信息：
  
  国家自然科学基金 (No.90715029，No.61070057）;湖南省科技计划 (No.2012WK3053）
- DOI：10.3969/j.issn.0372-2112.2013.11.010
  中图分类号： TP3
- 纸质出版：2013
- 稿件说明：
移动端阅览
吴帆, 李肯立. 基于自组装的N皇后问题DNA计算算法[J]. 电子学报, 2013,41(11):2174-2180.

WU Fan, LI Ken-li. An Algorithm in Tile Assembly Model for N Queen Problem[J]. Acta Electronica Sinica, 2013, 41(11): 2174-2180.
吴帆, 李肯立. 基于自组装的N皇后问题DNA计算算法[J]. 电子学报, 2013,41(11):2174-2180. DOI： 10.3969/j.issn.0372-2112.2013.11.010.

WU Fan, LI Ken-li. An Algorithm in Tile Assembly Model for N Queen Problem[J]. Acta Electronica Sinica, 2013, 41(11): 2174-2180. DOI： 10.3969/j.issn.0372-2112.2013.11.010.

摘要

N皇后问题是理论计算机科学中一个经典的NP难问题.自Adleman首次运用DNA计算来解决NP问题以来，DNA计算已成为计算机科学的研究热点之一，现有

皇后问题的DNA计算机算法多基于粘贴和剪接模型，存在生化操作复杂度和实验误差较高等问题.本文提出了一种基于DNA自组装模型来求解N皇后问题的DNA计算方法.算法通过减少实验操作步骤数，降低了生化解的错误率.算法使用的tiles分子块种类为

（

），生化操作复杂性为

（1），其中

为皇后的个数.与求解

皇后问题的其它DNA算法的对比分析表明，本算法可提高生化解的准确性，降低算法生化实验的复杂度，具有良好的易操作性.

Abstract

DNA computing employs molecule manipulation to solve NP complete problems that can not be solved using traditional 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

Queen problem algorithm based on the self assembly model is proposed.The proposed algorithm needs

(

) types of tiles and the complexity of experiment operations is

(1).Obviously

this algorithm significantl

y reduces the complexity of the experiment

thus improving the accuracy of experimental results.

关键词

Keywords

references

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据