并行改进回溯算法实现N皇后问题的快速计数

摘要：

通过对N皇后问题棋盘矩阵的旋转,改进了回溯算法,并通过计算机集群并行实现了N皇后的计数问题.考虑了棋盘矩阵顺时针旋转90°、180°和270°部分解存在重复的特性,改进了回溯方法,单机能够在15s内对16皇后问题进行计数.改进回溯算法的运算效率是顺序回溯法的4.69倍.然后通过固定前三行皇后的位置,可以把N皇后问题分成多个任务,实现了并行计算.在7个节点28个CPU的计算机集群上进行了实验,能够在8 min内实现对20皇后的计数,能够在1小时零8分钟内实现21皇后的计数.N皇后计数这个经典问题,通过实现程序的标准化,可以成为检验计算机集群运算性能的基准.

关键词：N皇后计数问题、回溯算法、计算机集群

所属期刊栏目：42

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金60331010;60271018;北京邮电大学校科研和教改项目;国家下一代互联网基金CNGI-04-15-7A

在线出版日期：2007-01-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：1-3