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

• 作者: 吕英华 韩宇南 黄小红
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: N皇后计数问题 回溯算法 计算机集群
• 年，卷（期）: 2006,（36）
• 所属期刊栏目: 博士论坛
• 页码范围: 1-3
• 页数: 3页
• 分类号: TP301.6
• 字数: 3484字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2006.36.001

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吕英华	北京邮电大学通信网络综合技术研究所	118	924	15.0	23.0
2	黄小红	北京邮电大学通信网络综合技术研究所	35	124	6.0	9.0
3	韩宇南	北京邮电大学通信网络综合技术研究所	7	44	4.0	6.0