欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
通过对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.
同期刊论文项目
同项目期刊论文
期刊信息
位置：