N皇后問題解的構(gòu)造及等價性分析.pdf

1、本文主要研究了N皇后問題(NQP)解的構(gòu)造及等價性分析。迄今為止，八皇后問題以及N皇后問題已經(jīng)被討論和研究了近160年時間。主要的研究范圍是在給定的正整數(shù)N的條件下：求N皇后問題的一個解；求N皇后問題的所有解；求N皇后問題的一組基礎(chǔ)解。已有多位研究者使用公式方法直接構(gòu)造出N皇后問題的一個解，不需要對其解空間進行搜索。但求解所有解和基礎(chǔ)解目前還只能依靠回溯算法對其解空間進行搜索，已求得NQP所有解的有記載的最大N值僅為25，但其解的總數(shù)已

2、經(jīng)多達(dá)2207893435808352，所耗費的時間相當(dāng)于約共53年CPU時間。NQP沒有獲得重大的突破性進展。近年來，NQP主要被用于人工智能領(lǐng)域測試各種智能搜索算法。 本文首先回顧了關(guān)于NQP的一些主要文獻(xiàn)，介紹了NQP幾種不同角度的定義、構(gòu)造NQP的部分解的多種構(gòu)造算法以及搜索NQP所有解和基礎(chǔ)解的算法。 本文通過對NQP解的特點進行分析，以NQP的函數(shù)定義為工具，論證了NQP解的二維旋轉(zhuǎn)變換和三維旋轉(zhuǎn)變換等幾何變

3、換及其復(fù)合變換，提出確立基礎(chǔ)幾何變換的方法，分析給出幾何變換的時間復(fù)雜度為O(N)，并論述了幾何等價關(guān)系。 本文進一步研究并提出NQP解的線性變換和線性等價關(guān)系，以滑動窗口為工具論證了Xu滑動變換、Yu滑動變換、Wu,v滑動變換及其之間的關(guān)系，分析給出了最壞情況下線性變換的時間復(fù)雜度為O(N3)，提出并論述了線性基礎(chǔ)解。 本文構(gòu)造了與已有研究成果不等價的NQP的部分解，設(shè)計給出時間復(fù)雜度為O(N2)的從N-1問題域到N問