论文部分内容阅读
本文主要研究了N皇后问题(NQP)解的构造及等价性分析。迄今为止，八皇后问题以及N皇后问题已经被讨论和研究了近160年时间。主要的研究范围是在给定的正整数N的条件下：求N皇后问题的一个解；求N皇后问题的所有解；求N皇后问题的一组基础解。已有多位研究者使用公式方法直接构造出N皇后问题的一个解，不需要对其解空间进行搜索。但求解所有解和基础解目前还只能依靠回溯算法对其解空间进行搜索，已求得NQP所有解的有记载的最大N值仅为25，但其解的总数已经多达2207893435808352，所耗费的时间相当于约共53年CPU时间。NQP没有获得重大的突破性进展。近年来，NQP主要被用于人工智能领域测试各种智能搜索算法。
本文首先回顾了关于NQP的一些主要文献，介绍了NQP几种不同角度的定义、构造NQP的部分解的多种构造算法以及搜索NQP所有解和基础解的算法。
本文通过对NQP解的特点进行分析，以NQP的函数定义为工具，论证了NQP解的二维旋转变换和三维旋转变换等几何变换及其复合变换，提出确立基础几何变换的方法，分析给出几何变换的时间复杂度为O(N)，并论述了几何等价关系。
本文进一步研究并提出NQP解的线性变换和线性等价关系，以滑动窗口为工具论证了Xu滑动变换、Yu滑动变换、Wu,v滑动变换及其之间的关系，分析给出了最坏情况下线性变换的时间复杂度为O(N3)，提出并论述了线性基础解。
本文构造了与已有研究成果不等价的NQP的部分解，设计给出时间复杂度为O(N2)的从N-1问题域到N问题域的递推算法，最后综合了几何变换、线性变换以及递推算法设计并实现一个推导算法可以从NQP解的集合Fm推导出基于Fm的一簇解Fn。