徐少飛，張立臣，李鵬

（陜西師范大學(xué)計算機科學(xué)學(xué)院，西安 710119）

0 引言

八皇后問題是指在一個8×8的國際象棋棋盤上隨機擺放八個皇后［1］，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，要求求出所有的可行解。一個八皇后問題的可行解如圖1所示。

圖1 八皇后問題的一個可行解

n皇后問題是八皇后問題的推廣，是指在一個n×n的棋盤上放置n個皇后，使任意兩個皇后不能相互攻擊。我們知道，傳統(tǒng)的回溯算法可以求解n皇后問題，但其時間復(fù)雜度是指數(shù)型的，算法效率較低。目前不少學(xué)者對傳統(tǒng)回溯算法進行改進，文獻［2］利用了n皇后問題解的對稱性質(zhì)對回溯法進行了改進，但優(yōu)化效果并不明顯；文獻［3］和文獻［4］利用基于位運算的回溯算法進行求解，在整個解空間中搜索，仍沒有降低算法的時間復(fù)雜性。為了研究更高效、簡潔求解n皇后問題一組可行解的算法，本文將傳統(tǒng)的回溯算法與概率算法相結(jié)合，將棋盤分割為兩部分，前半部分使用概率算法求解，后半部分采用回溯算法求解，并合理設(shè)置影響算法性能的分割系數(shù)和回溯方式。實驗結(jié)果表明，相比于傳統(tǒng)的回溯算法，該算法能夠有效地縮短求解時間，因而可以極大拓展在規(guī)定時間內(nèi)可求解問題的規(guī)模。

1 n皇后問題求解模型的建立

約定第i個皇后放在棋盤的第i行，設(shè)其所在的列為xi(i=1,2,3,…,n)，這樣問題的解就是n個皇后所在列的序號組成的一個n元一維向量(x1,x2,x3,…,xn)，解空間是從1到n的全排列。約束條件是這n個皇后在棋盤上的位置(1,x1),(2,x2),(3,x3),…,(n,xn)不在同一列和同一對角線上。

即對于任意兩行i和j上的皇后，需要滿足的約束條件有兩個：①不在同一列：xi≠xj;②不在同一對角線上：abs(xi-xj)≠abs(i-j)。

2 回溯法求解n皇后問題

2.1 算法思想

回溯法的基本思想是，按照順序依次確定每個皇后的位置，首先將第一個皇后放置在滿足約束條件的第1個位置，即x1=1,然后再為下一個皇后確定合適的位置，以此類推，直到確定了所有皇后的位置。在這一過程中，可能會出現(xiàn)這樣的情況：即無法為第n個皇后找到滿足約束條件的位置。這說明其前面已放置皇后的位置需要進行調(diào)整,因此可以先考慮將第n-1個皇后移至下一個滿足約束條件的位置，如果第n-1個皇后無法尋找到下一個滿足約束條件的位置，則可以進一步向前調(diào)整第n-2個皇后的位置，以此類推。之后再為第n個皇后尋找滿足約束條件的位置。以這樣的方式進行下去，最終可以保證所有皇后在互不攻擊的情況下放置在棋盤中。

2.2 算法求解

2.2.1 遞歸回溯算法

遞歸回溯算法的思想是基于深度優(yōu)先搜索策略［5］。對于n皇后問題，遞歸的回溯算法采用遞歸的方式依次確定每個皇后的位置，若一個皇后的所有位置都不滿足約束條件，算法將回溯至前一個皇后。

算法1運用遞歸回溯法解決n皇后問題偽代碼描述

2.2.2 非遞歸回溯算法

求解n皇后問題的非遞歸回溯的算法同樣采用深度優(yōu)先搜索策略，并在不符合約束條件時及時回溯［6-7］。相比于遞歸的回溯算法，非遞歸回溯算法不需要頻繁地調(diào)用系統(tǒng)堆棧，而是在一個數(shù)組中進行回溯的，從而節(jié)省了系統(tǒng)資源。

算法2運用非遞歸回溯法解決n皇后問題偽代碼描述

2.3 算法分析

回溯法基于深度優(yōu)先搜索的策略在整個解空間中進行搜索，并在不滿足條件時及時進行剪枝操作。在解決n皇后問題的過程中，若不進行任何的剪枝操作，最壞情況下，其時間復(fù)雜度可達O(nn)，屬于指數(shù)級別。相比于一般的窮舉法，回溯算法雖然避免了一些不必要的搜索，并可將最壞情況下的時間復(fù)雜度優(yōu)化至O(n!)，但其時間復(fù)雜度仍然較大，性能不好。

3 拉斯維加斯概率算法求解n皇后問題

3.1 算法思想

拉斯維加斯（Las Vegas）概率算法的基本思想是用生成的隨機序列代替有次序的窮舉，然后判斷基于該隨機序列所產(chǎn)生的結(jié)果是否為符合問題約束條件的正確解［8］。拉斯維加斯概率算法非常適合于在一個問題解空間中尋找一個可行解的場景。但是，該算法同時具有一定的缺點，即存在無法找到可行解的情形。事實上，出現(xiàn)這種情況的可能性不大，而且我們可以通過增加算法執(zhí)行次數(shù)的方式進一步提高找到可行解的概率。

我們知道，當(dāng)程序重復(fù)執(zhí)行的次數(shù)越多，運行時間越長時，利用拉斯維加斯概率算法求得問題的一個可行解的概率也就越大［9-10］。因此，如果要使求解問題失敗的概率降至任意小，可以足夠多次地重復(fù)調(diào)用拉斯維加斯概率算法進行求解。

3.2 算法分類

為了表述方便，本文將拉斯維加斯概率算法分為拉斯維加斯循環(huán)算法和拉斯維加斯一般算法。

拉斯維加斯循環(huán)算法的成功率是100%，它將循環(huán)執(zhí)行，直到找到一組可行解時退出程序。

拉斯維加斯一般算法的成功率不是100%，它將設(shè)定一個最大循環(huán)次數(shù)k，然后再進行有限次數(shù)的循環(huán)，直到找到一組可行解或當(dāng)循環(huán)次數(shù)>k時，結(jié)束程序。

3.3 算法求解

對于n皇后問題，我們目前無法確定每個皇后放置的具體規(guī)律，因而無法快速地放置這些皇后，這使得我們可以采用隨機放置的方式。這種隨機放置的思想與拉斯維加斯概率算法相同。該算法依次隨機地放置每一個皇后，直到所有的皇后均已在滿足約束條件的情況下放置好。在放置當(dāng)前皇后的過程中，需要保證：新放置的皇后與前面已放置好的所有皇后不沖突。

本文將選擇拉斯維加斯循環(huán)算法來解決n皇后問題，確保其正確率達到100%，方便后續(xù)進行各種算法運行時間的比較分析。

算法3運用拉斯維加斯概率算法解決n皇后問題偽代碼描述

Input:開始進行概率算法的行序號star（t0

3.4 算法分析

對于拉斯維加斯概率算法，假設(shè)一共要排列n個皇后，每一行的皇后平均要進行k次測試才能找到合適位置，LV函數(shù)的算法時間復(fù)雜度為O(n)，在Probability函數(shù)中，LV函數(shù)將被執(zhí)行k次，因此，最終該算法的時間復(fù)雜度應(yīng)為O(n×k)。

4 概率回溯復(fù)合算法求解n皇后問題

4.1 算法思路

分析上文中概率算法和回溯算法的特性可知，概率算法在問題規(guī)模較小時可以快速得到一個可行解；而回溯算法則可以利用其回溯的特性保證能夠求得問題的一個可行解［11-12］。因此，我們可以將二者的優(yōu)勢相結(jié)合，提出一種概率回溯復(fù)合算法。該算法具體為：先將整個棋盤分為兩部分，然后在前一部分采用拉斯維加斯概率算法隨機地放置皇后，在后半部分使用回溯算法放置剩余的皇后，直到所有皇后都被放置完畢，如圖2所示。

圖2 概率回溯復(fù)合算法示意

4.2 算法求解

設(shè)皇后數(shù)量為n，d為分割系數(shù)，用于分割棋盤，floor為向下取整函數(shù)。在棋盤的前floor(n×d)行采用拉斯維加斯概率算法隨機放置皇后，后續(xù)的行采用非遞歸回溯的算法放置其余皇后。

為了確保該算法的成功率為100%，本文將在棋盤的前floor(n×d)行采用拉斯維加斯循環(huán)概率算法進行求解，并允許后續(xù)行在使用回溯法時能夠回溯到棋盤首行。

算法4運用概率回溯復(fù)合算法解決n皇后問題偽代碼描述

Input:皇后數(shù)量n，分割系數(shù)d，開始進行概率算法的行序號start（0

4.3 算法分析

當(dāng)皇后數(shù)量為n時，則先在棋盤前floor(n×d)行使用拉斯維加斯概率算法，在后續(xù)行使用非遞歸回溯算法，采用概率算法的時間復(fù)雜度為O(d×n×k)，使用回溯法的 時 間 復(fù) 雜度為O((d×n)!)。

5 仿真實驗與分析

5.1 實驗環(huán)境

本文實驗環(huán)境：CPU，Intel Core i5-8265U；內(nèi)存容量，8.00 GB；硬盤，1 TB；PF使用率，47%～50%；集成開發(fā)工具，Eclipse 4.12.0。

5.2 輸入數(shù)據(jù)

輸入數(shù)據(jù)為皇后的數(shù)量n，這也決定了棋盤是一個n×n大小的。本實驗將n分別取為8、11、14、17、20、23、25、26、27、28、30，概率回溯復(fù)合算法的分割系數(shù)d取為0.5，然后測試四種算法的運行結(jié)果及運行時間。在特定輸入規(guī)模n的情況下，每一種算法運行20次，運行時間取這20次實驗運行時間的平均值。

5.3 實驗結(jié)果分析

分別對n皇后問題遞歸回溯、非遞歸回溯、拉斯維加斯概率、概率回溯復(fù)合算法的算法規(guī)模和執(zhí)行時間進行仿真。四種算法的成功率為100%，其求解時間如表1所示。

表1 四種算法求解時間（單位：ms）

當(dāng)n>11時，拉斯維加斯概率算法的求解時間就已經(jīng)超過了10000 ms，因此不再統(tǒng)計概率算法后期的求解時間。

從表1中可以直觀地看到四種算法的求解時間對比，當(dāng)n從27變到28時，兩種回溯算法的求解時間的增長速度很快，當(dāng)n從28變到30時，其求解時間更是呈指數(shù)形式增長。相比之下，概率回溯復(fù)合算法的求解時間一直都較短，并且隨輸入規(guī)模n增加而增長的速度也十分緩慢。

傳統(tǒng)的回溯算法在n=30的時候求解時間就已經(jīng)很長了，考慮到計算機的算力瓶頸，后面只觀察隨著n值的繼續(xù)增大，概率回溯復(fù)合算法求解時間的增長情況。

圖3 概率回溯復(fù)合算法求解時間（n值：32～50）

圖3是當(dāng)n值從32變化到50的過程中，概率回溯復(fù)合算法求解時間的變化情況。當(dāng)n值達到41后，算法的求解時間就增長的比較快了，當(dāng)n值從47到50的時候，算法的求解時間增長得最快，在n=50時，算法求解時間就已達到了42047 ms。這可能是由于前半部分的概率算法和后半部分的回溯算法需要花更多的時間去尋找每個皇后的合適位置。

6 概率回溯復(fù)合算法的進一步研究

6.1 回溯范圍對算法性能的影響

對于概率回溯復(fù)合算法，當(dāng)在前若干行使用完拉斯維加斯概率算法之后，后續(xù)行會使用回溯法繼續(xù)放置剩余皇后。當(dāng)回溯法需要進行回溯操作時，回溯范圍有兩種，一種是截止到開始使用回溯算法的那一行；另一種是截止到首行?？赏ㄟ^實驗驗證的方式對比這兩種范圍對算法性能的影響?；屎髷?shù)量n將分別取為7、10、15、18、20、23、25、26、27、28，其概率算法部分采用成功率非100%的拉斯維加斯一般概率算法，最大循環(huán)次數(shù)k選為10000，這樣便于研究不同參數(shù)分別對概率算法部分和回溯算法部分的影響情況。

表2 回溯截止到首行的求解情況

表3 回溯截止到開始回溯的那一行的求解情況

表2和表3分別是回溯截止到首行的求解情況和回溯截止到開始回溯的那一行的求解情況。通過兩種回溯方式的對比實驗，可以知道，采用回溯到首行的方式，算法整體求解的正確率要更高一些。

6.2 分割系數(shù)對算法性能的影響

概率回溯復(fù)合算法中的分割系數(shù)d表示前floor(n×d)行使用拉斯維加斯概率算法，其中，floor()函數(shù)是下取整函數(shù)。因此，分割系數(shù)d的選取對該算法的性能有重要影響。本次實驗，規(guī)定采用回溯至首行的策略，概率算法部分采用成功率非100%的拉斯維加斯一般概率算法，設(shè)置分割系數(shù)分別為0、0.2、0.4、0.6、0.8、1，測試其在n=30的情況下算法連續(xù)運行50次能成功求解的概率，圖4是求解正確率隨分割系數(shù)d變化的折線圖，測試結(jié)果如圖4所示。

圖4 求解成功率隨分割系數(shù)d的變化情況

分析圖4可知，當(dāng)分割系數(shù)d增大時，算法的求解成功率明顯下降。當(dāng)d=1時，概率回溯復(fù)合算法退化為回溯算法，當(dāng)d=0時，概率回溯復(fù)合算法變?yōu)槔咕S加斯概率算法。

分割系數(shù)除了對算法成功率有很大影響外，還影響算法的求解時間。圖5測試在n=30時，算法求解時間隨分割系數(shù)的變化情況。分割系數(shù)d分別取0.2、0.3、0.4、0.5、0.6、0.7、0.8，采用回溯到首行的方式，概率算法部分采用成功率為100%的拉斯維加斯循環(huán)概率算法，這樣能更合理地統(tǒng)計算法求解時間。

圖5 求解時間隨分割系數(shù)d的變化情況

從圖5可知，在分割系數(shù)從0.2增加到0.8的過程中，算法的求解時間是一個先減少后增加的過程，在d=0.4時，算法的求解時間最短。在分割系數(shù)為0.7和0.8時，程序的運行時間已超過規(guī)定的最大時限5 min，因此不再進行計算。

由此可見，選取合適的參數(shù)可以使概率回溯復(fù)合算法的性能得到很大提升。

7 結(jié)語

本文通過對比實驗,發(fā)現(xiàn)傳統(tǒng)的回溯算法在n=30的時候就需要兩萬多毫秒才能得到結(jié)果，而相比之下，分割系數(shù)為0.5的概率回溯復(fù)合算法在n值接近50的時候才會消耗相同的時間，這極大地拓展了規(guī)定時間內(nèi)算法可計算和求解的范圍。此外，本文還深入研究和分析了回溯方式、分割系數(shù)等參數(shù)條件對概率回溯復(fù)合算法成功率及求解時間的影響，得出了在合理設(shè)置這些參數(shù)的條件下，概率回溯復(fù)合算法在求解n皇后問題一組解上的表現(xiàn)要優(yōu)于其他算法的結(jié)論。這對今后研究與應(yīng)用該算法以及分析和研究其他NP問題具有較好的指導(dǎo)意義和參考價值。