基于粘贴DNA芯片模型的八皇后问题算法  

Algorithm of sticker DNA chip model on Eight Queens problem

作　　者：周康[1,2] 同小军[1,2] 许进[1] 

机构地区：[1]华中科技大学控制科学与工程系,湖北武汉430074 [2]武汉工业学院数理科学系,湖北武汉430023

出　　处：《系统工程学报》2008年第3期372-376,共5页Journal of Systems Engineering

基　　金：国家自然科学基金资助项目(60403002);湖北省自然科学基金资助项目(2007ABA407;2005ABA233);湖北省教学研究资助项目(20040248);浙江省自然科学基金资助项目(ZJNSF-Y105654)

摘　　要：提出了粘贴 DNA 芯片模型,该模型综合了粘贴模型的筛选功能和 DNA 芯片模型的检测功能.利用这两个特点设计了基于粘贴 DNA 芯片模型的求解八皇后问题全部解的 DNA 算法.该算法首先产生所有可能的解,再分别按照行要求,列要求和对角线要求逐步筛选出八皇后问题的全部解.利用 DNA 芯片检测出实验结果,然后对每个实验步骤分析了算法的生化实现过程并得到了八皇后问题的全部解.最后讨论了算法的复杂性及其优势.In this paper, a model of sticker DNA chip is brought forward. This model combines the filter function of sticker model and the check function of DNA chip model. And using this two characteristics, an algorithm of sticker DNA chip model to obtain all solutions of Eight Queens problem is designed. In the algorithm, all possible solutions are gotten. Then all solutions of Eight Queens problem are obtained gradually, according to row restriction, line restriction and diagonal restriction, respectively. The experiment result is checked by DNA chip. Biochemistry realizing process of each experiment step of this algorithm is analyzed, and all solutions of Eight Queens problem are obtained. Fially, complexity and predominance of the DNA algorithm are discussed.

关 键 词：八皇后问题 粘贴DNA芯片模型 DNA编码 分离实验 

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