基于闭环DNA模型的八皇后问题算法.pdf

4 2007，43(6) and ComputerEngineeringApplations计算机工程与应用 基于闭环DNA模型的八皇后问题算法 周 康1’2，同小军1’2，许进2 ZHOU TONG XU 9 Jin2 Kan91,2 Xiao-junl,2 1．武汉工业学院数理科学系．武汉430023 2．华中科技大学控制科学与工程系，武汉430074 ofMathematicsand 1．Department Physics，WuhanPolytechnic 430023，China University，Wuhan ofContmlScienceand ofScienceand 430074，China 2．Department Engineering，HuazhongUniversity Technology，Wuhan ZHOU circleDNA of Kang，TONGXiao-Jun，XUJin．Closed and algorithmEightQueensproblem．ComputerEngineering Applications，2007，43(6)：4-6． Abstract：Inthis modelofclosedcircleDNA anditsbasal are forward． paper，a computing biochemistryexperimentsbrought ThenclosedcircleDNA allfeasiblesolutionsof is forward．The and algorithm finding EightQueensproblemput realizingsteps modeoftheclosedcircleDNA ale allfeasiblesolutionsof are obtained． realizing algorithmanalyzed，and EightQueensproblem oftheDNA isdiscussed． Finally，complexityalgorithm ofclosedcircleDNA Keywords：EightQueensproblem；model computing；DNAencoding；deleteexperiment 算法的实现步骤及其实现方式并得到了全部的可行解。最后讨论了算法的复杂性。 关键词：八皇后问题；闭环DNA模型；DNA编码；删除实验 文献标识码：A 中图分类号：TP301．6 文章编号：1002—8331(2007)06—0004-j93 1 闭环DNA计算与八皇后问题 1．2八皇后问题 1．1 闭环DNA计算模型 八皇后问题p，目为：在8x8的国际象棋棋盘上安放8个皇 闭环DNA计算模型【l-6／是一种新的DNA计算模型(“，闭环后，要求没有任何两个皇后占据棋盘上的同一行、同一列或