计算机工程与应用 ›› 2006, Vol. 42 ›› Issue (36): 1-.

• 博士论坛 •    下一篇

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

韩宇南、吕英华、黄小红

  

  1. 北京邮电大学
  • 收稿日期:2006-07-20 修回日期:1900-01-01 出版日期:2006-12-21 发布日期:2006-12-21
  • 通讯作者: 黄小红 gigi_huang

Solving N-Queens Counting Problem by Using Improved Parallelized Backtracking Algorithm

Xiaohong Huang,Yunan Han,Yinghua Lu   

  1. 北京邮电大学
  • Received:2006-07-20 Revised:1900-01-01 Online:2006-12-21 Published:2006-12-21
  • Contact: Xiaohong Huang

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

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

Abstract: 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 degree, 180 degree and 270 degree. The improved backtracking algorithm can solve the 16-queens counting problem in 15 seconds 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 minutes 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.

Key words: N-queens counting problem, Backtracking algorithm, Computer cluster

京ICP备13024262号-1
Copyright © 《计算机工程与应用》编辑部
技术支持：北京玛格泰克科技发展有限公司
总访问量
今日访问
在线人数