摘要
提出了粘贴 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.
出处
《系统工程学报》
CSCD
北大核心
2008年第3期372-376,共5页
Journal of Systems Engineering
基金
国家自然科学基金资助项目(60403002)
湖北省自然科学基金资助项目(2007ABA407
2005ABA233)
湖北省教学研究资助项目(20040248)
浙江省自然科学基金资助项目(ZJNSF-Y105654)
