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

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

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

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