八皇后问题所有解的模拟DNA算法.pdfVIP

第37卷 　第6期 华 　中　科 　技 　大 　学 　学 　报 ( 自然科学版) Vol . 37 No . 6 2009年 　6月 　 J . Huazhong U niv . of Sci . Tech . (Nat ural Science Edition) 　J un . 　2009 八皇后问题所有解的模拟 DN A 算法 周 　康 　魏传佳 　刘 　朔 　卢 　军 (武汉工业学院 数理科学系 , 湖北 武汉 430023) 摘要 : 建立了求解八皇后问题所有解的数学模型. 根据八皇后问题解的性质提出了 7 个相关的算子 :主转置 算子 、行翻转算子 、列翻转算子 、倒置算子 、顺旋算子 、逆旋算子和倒转算子. 给出了等价可行解的概念 ,并以这 7 个相关算子为工具研究了等价可行解的性质和八皇后问题解空间的性质. 由此给出了求解八皇后问题所有 解的模拟 DN A 算法 ,并用 Mat hematica 软件进行了实现 ,并得到了所有的可行解 ,进而验证了算法的正确性 和可行性. 关 　键 　词 : 八皇后问题 ; 数学模型 ; 等价可行解 ; 算子 ; 模拟 DN A 算法 中图分类号 : TP30 1. 6 　　文献标识码 : A 　　文章编号 : 167 14512 (2009) Simulation D NA algorithm of all sol utions of Eight Queens Problem Z hou K ang 　Wei Ch uanj i a 　L i u S h uo 　L u J un (Dep art ment of Mat hematics and Phy sics , Wuhan Polyt echnic U niver sit y ,Wuhan 430023 , China) Abstract : Mat hematic s mo del of Eight Queen s Problem i s set up in t hi s p ap er . Accor ding to charact er i stic of Eight Queen s Problem , seven op erator s of Eight Queen s Problem are brought forwar d , w hich are do minant t ran spo sed op erator , rowflip op erator , li stflip op erator , inver sion op erator , or dinal t ur n op erator , cont raryt ur n op erator , rever se op erator . Equip ollence f ea sible solutio n of Eight Queen s Problem i s bro ught forwar d , and charact eri stic of quipollence f ea sible solution and charact eri s tic of solutio n sp ace of Eight Queen s Problem are st udied u sing t he se seven op erator s. Thereby , simu lation DN A algorit hm of all solution s of Eight Queen s Problem i s foun d , w hich i s realized on Mat h ematica soft ware , t hen all f ea sible solution s of Eight Queen s Problem are obt ained . Key words : Eight Que