摘要
通过对N皇后问题棋盘矩阵的旋转,改进了回溯算法,并通过计算机集群并行实现了N皇后的计数问题。考虑了棋盘矩阵顺时针旋转90°、180°和270°部分解存在重复的特性,改进了回溯方法,单机能够在15s内对16皇后问题进行计数。改进回溯算法的运算效率是顺序回溯法的4.69倍。然后通过固定前三行皇后的位置,可以把N皇后问题分成多个任务,实现了并行计算。在7个节点28个CPU的计算机集群上进行了实验,能够在8min内实现对20皇后的计数,能够在1小时零8分钟内实现21皇后的计数。N皇后计数这个经典问题,通过实现程序的标准化,可以成为检验计算机集群运算性能的基准。
Traditional backtracking algorithm has been improved by rotating the chessboard matrix and put into solving N-queens counting problem in computer cluster.In order to improve the backtracking algorithm,the chessboard matrix can be rotated clockwise 90°,180° and 270°.The improved backtracking algorithm can solve the 16-queens counting problem in 15 s by only one CPU.The efficiency is 4.69 time faster.By locating the queens in the first three lines,the N-queens counting problem can be distributed into thousands of tasks and computed by a computer cluster with 28 CPU.The 20-queens counting problem can be computed in 8 min and the 21-queens counting problem can be computed in 1 hour and 8 minutes.The program can be used as a benchmark program for computer clusters.
出处
《计算机工程与应用》
CSCD
北大核心
2006年第36期1-3,共3页
Computer Engineering and Applications
基金
国家自然科学基金资助项目(60331010
60271018)
北京邮电大学创新基金
国家下一代互联网基金(CNGI-04-15-7A)
关键词
N皇后计数问题
回溯算法
计算机集群
N-queens counting problem
backtracking algorithm
computer cluster
