一种求解n皇后问题的概率回溯复合算法  

A Probabilistic Backtracking Compound Algorithm for Solving the N-Queens Problem

作　　者：徐少飞 张立臣[1] 李鹏[1] Xu Shaofei;Zhang Lichen;Li Peng(School of Computer Science,Shanxi Normal University,Xi’an 710119)

机构地区：[1]陕西师范大学计算机科学学院,西安710119

出　　处：《现代计算机》2021年第27期24-30,共7页Modern Computer

基　　金：教育部陕西师范大学基础教育课程研究中心项目(2019-JCJY009);陕西师范大学金课(算法设计与分析)建设项目(2019)。

摘　　要：为了寻求解决n皇后问题的高效算法,首先分别采用递归回溯法、非递归回溯法和概率算法来求解该问题,在此基础上,综合概率算法和回溯算法的优点,提出了概率回溯复合算法。该算法使用概率算法先在棋盘的前若干行放置皇后,然后采用回溯算法在后继行继续放置,直到找到一个满足条件的可行解。通过大量实验深入研究了不同参数对概率回溯复合算法性能的影响,验证了所提算法的高效性。In order to find an efficient algorithm for the n-queen problem,firstly,recursive backtracking,non-recursive backtracking and probabilistic algorithms were used to solve the problem.On this basis,combining the advantages of probabilistic and backtracking algorithms,a composite probabilistic backtracking algorithm was proposed.The algorithm uses the probability algorithm to place the queens in the first several rows of the chessboard,and then uses the backtracking algorithm to continue to place the queens in subsequent rows until it finds a feasible solution that satisfies the conditions.Through a large number of experiments,the influence of different parameters on the performance of the probabilistic backtracking compound algorithm was deeply studied,and the efficiency of the proposed algorithm was verified.

关 键 词：回溯法 概率算法 概率回溯复合算法 分割系数 回溯范围 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]