-
题名并行改进回溯算法实现N皇后问题的快速计数
被引量：6
- 1
-
-
作者
韩宇南
吕英华
黄小红
-
机构
北京邮电大学通信网络综合技术研究所
-
出处
《计算机工程与应用》
CSCD
北大核心
2006年第36期1-3,共3页
-
基金
国家自然科学基金资助项目(60331010
60271018)
+1 种基金
北京邮电大学创新基金
国家下一代互联网基金(CNGI-04-15-7A)
-
文摘
通过对N皇后问题棋盘矩阵的旋转,改进了回溯算法,并通过计算机集群并行实现了N皇后的计数问题。考虑了棋盘矩阵顺时针旋转90°、180°和270°部分解存在重复的特性,改进了回溯方法,单机能够在15s内对16皇后问题进行计数。改进回溯算法的运算效率是顺序回溯法的4.69倍。然后通过固定前三行皇后的位置,可以把N皇后问题分成多个任务,实现了并行计算。在7个节点28个CPU的计算机集群上进行了实验,能够在8min内实现对20皇后的计数,能够在1小时零8分钟内实现21皇后的计数。N皇后计数这个经典问题,通过实现程序的标准化,可以成为检验计算机集群运算性能的基准。
-
关键词
n皇后计数问题
回溯算法
计算机集群
-
Keywords
n-queens counting problem
backtracking algorithm
computer cluster
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
