计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2006年
36期
1-3
,共3页
N皇后计数问题%回溯算法%计算机集群
N皇後計數問題%迴溯算法%計算機集群
N황후계수문제%회소산법%계산궤집군
通过对N皇后问题棋盘矩阵的旋转,改进了回溯算法,并通过计算机集群并行实现了N皇后的计数问题.考虑了棋盘矩阵顺时针旋转90°、180°和270°部分解存在重复的特性,改进了回溯方法,单机能够在15s内对16皇后问题进行计数.改进回溯算法的运算效率是顺序回溯法的4.69倍.然后通过固定前三行皇后的位置,可以把N皇后问题分成多个任务,实现了并行计算.在7个节点28个CPU的计算机集群上进行了实验,能够在8 min内实现对20皇后的计数,能够在1小时零8分钟内实现21皇后的计数.N皇后计数这个经典问题,通过实现程序的标准化,可以成为检验计算机集群运算性能的基准.
通過對N皇後問題棋盤矩陣的鏇轉,改進瞭迴溯算法,併通過計算機集群併行實現瞭N皇後的計數問題.攷慮瞭棋盤矩陣順時針鏇轉90°、180°和270°部分解存在重複的特性,改進瞭迴溯方法,單機能夠在15s內對16皇後問題進行計數.改進迴溯算法的運算效率是順序迴溯法的4.69倍.然後通過固定前三行皇後的位置,可以把N皇後問題分成多箇任務,實現瞭併行計算.在7箇節點28箇CPU的計算機集群上進行瞭實驗,能夠在8 min內實現對20皇後的計數,能夠在1小時零8分鐘內實現21皇後的計數.N皇後計數這箇經典問題,通過實現程序的標準化,可以成為檢驗計算機集群運算性能的基準.
통과대N황후문제기반구진적선전,개진료회소산법,병통과계산궤집군병행실현료N황후적계수문제.고필료기반구진순시침선전90°、180°화270°부분해존재중복적특성,개진료회소방법,단궤능구재15s내대16황후문제진행계수.개진회소산법적운산효솔시순서회소법적4.69배.연후통과고정전삼행황후적위치,가이파N황후문제분성다개임무,실현료병행계산.재7개절점28개CPU적계산궤집군상진행료실험,능구재8 min내실현대20황후적계수,능구재1소시령8분종내실현21황후적계수.N황후계수저개경전문제,통과실현정서적표준화,가이성위검험계산궤집군운산성능적기준.
