N皇后问题的快速搜索算法  

A Fast Search Algorithm for N-Queens Problem

作　　者：王哲[1] 栾英姿[1] 

机构地区：[1]西安电子科技大学,陕西西安710071

出　　处：《计算机技术与发展》2009年第6期72-75,共4页Computer Technology and Development

基　　金：国家自然科学基金重大项目(60496316)

摘　　要：回溯算法是解决N皇后问题的经典算法,最坏情况下,它的搜索时间和皇后维数N成指数关系,无法满足基于Q-矩阵的LDPC码这种编码方案对码长的要求。介绍了一种解决皇后问题的快速搜索算法,它是使碰撞数最小化的本地搜索算法,这种算法的性能和回溯算法相比有极大的提高,搜索时间和皇后维数N基本成线性关系,并且有较强的灵活性,因而对于Q-矩阵LDPC码这种编码方案而言,快速搜索算法更为合适。The backtracking algorithm is the classieal algorithm for solving N queens problem. In the worst ease, a backtracking algorithm is exponential with N, so it is not able to meet the requirements of the encoding scheme for Q- matrix LDPC code. In this paper, a fast search algorithm, whieh is pmbahilistie local search with conflict minimization is presented, the performance of this algorithm is more better than baektracking algorithm, it runs almost in linear time with N, and it is very flexible, so it＇s more appropriate for the encoding scheme for Q- matrix LDPC code.

关 键 词：Q-矩阵 回溯算法 快速搜索算法 LDPC码 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]