N后問題的拉斯維加斯算法研究

王立志

（河南大學計算機與信息工程學院 河南省開封市 475004）

1 引言

隨機化算法是一種將一定程度的隨機性作為其邏輯的一部分的算法。隨機化算法通常使用統(tǒng)一的隨機位作為輔助輸入來指導其行為，以期在所有隨機位的可能選擇的“平均情況”下獲得良好的性能[1]。拉斯維加斯算法的一個顯著特征是它所做的隨機性決策有可能導致算法找不到所需的解[2]。

拉斯維加斯算法是一種永遠給出正確結(jié)果的隨機化算法[3]。拉斯維加斯算法的性質(zhì)使它們適合于可能的解決方案數(shù)量有限的情況，在這種情況下，驗證候選解決方案的正確性相對容易，而尋找解決方案則比較復雜。拉斯維加斯算法的運行時間取決于輸入的規(guī)模。拉斯維加斯算法找到正確解的概率與所使用的計算時間有關(guān)，對于同一問題，使用拉斯維加斯算法反復計算求解足夠多次就可以不斷縮小算法失效的概率[2]。

n后問題等價于在n×n格的棋盤上放置n個皇后，在可行的解棋盤中，同一行、列或者斜線上不會同時出現(xiàn)兩個皇后。N后問題提供了設計高效的拉斯維加斯算法的很好的例子。在使用回溯法解n后問題時，實際上是在系統(tǒng)地搜索整個解空間樹的過程中找出滿足要求的解。對于n后問題的任何一個解來說n個皇后更像是隨機放置的，這符合隨機化算法的性質(zhì)。應用拉斯維加斯算法在棋盤上相繼的各行中隨機地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個皇后均已相容地放好，或已沒有下一個皇后的可放置位置時為止[2]。

2 相關(guān)工作

拉斯維加斯算法是由László Babai 在1979年提出的，最初是為了解決圖同構(gòu)問題。Babai給這種算法命名為“拉斯維加斯算法”，并且使用“拋硬幣”的例子來解釋這個算法[3]。Max Bezzel 于1848年提出了八皇后問題，F(xiàn)ranz Nauck 提出了第一種解決方案，同時他也將這個問題推廣到n皇后的問題，即在n×n的棋盤上放置n個皇后。Edsger Dijkstra發(fā)表了一篇關(guān)于深度優(yōu)先回溯算法的非常詳細的描述[4]。在使用回溯法解決n后問題的研究中，陳曉梅等將位運算運用到回溯法的剪枝函數(shù)中，這一方法能夠加速獲得正確解的效率[5]。劉寒冰等改進了互不攻擊的條件[6]。黃建民等通過使用較好的數(shù)據(jù)類型表示解空間，設計了八皇后問題的非遞歸算法[7]。張萬軍借助矩陣改進了檢測攻擊條件的方法，并且優(yōu)化了算法的循環(huán)結(jié)束條件[8]。 有學者在研究拉斯維加斯算法解n后問題的算法效率后，通過加入隨即策略改進回溯法，并驗證該改進算法具有更好的算法效率[9][10]。

3 算法介紹

棋盤通過一個排列向量來表示，在排列向量中給出了n行中n個皇后的位置，這意味著在水平和垂直的方向上都沒有攻擊，算法只需檢查兩側(cè)對角線方向的攻擊。一個向量標記對角線的常數(shù)（行-列）；另一個標記常數(shù)（行+列）的對角線。

基本邏輯

repeat

將有效值設為真

將當前的排列向量重置

將兩個對角向量都設置為false

標記兩個對角線中的第0行女王

for row = 1 to n–1

set test = row+1

while

if test = n

set valid to false

打破while循環(huán)

else

交換位置行和測試

增量測試

end if/else

end while

如果無效

退出for循環(huán)

在對角線上標記該行的女王

vectors

end for

循環(huán)直到有效

使用類范圍生成器將整個數(shù)組混洗

拉斯維加斯算法針對N皇后問題構(gòu)建一個可能有效的棋盤：隨機排列，然后進行驗證或不做（因此返回的布爾值-僅在發(fā)現(xiàn)的棋盤為有效解決方案時為true）。

在使用拉斯維加斯算法解決N后問題的代碼基礎(chǔ)上，我們加入了線程的思想，使用多線程加快了查找解決方案的速度。計算是在充當計算引擎的線程內(nèi)完成的。線程類是QueenLasVegas的內(nèi)部類，因此其代碼可以完全訪問線程類的所有私有部分。為了確保每個線程使用一個_different_隨機數(shù)序列，每個線程都有自己的生成器，并且該生成器由System.currentTimeMillis（）和this.hashCode（）的乘積作為種子：第一個在連續(xù)運行時生成機會種子，第二個在相同的運行中生成機會種子。ComputeEngine類具有一個靜態(tài)int []解決方案，該解決方案接收對其中一個線程發(fā)現(xiàn)的第一個成功解決方案的引用。當此靜態(tài)數(shù)據(jù)成員變?yōu)榉强諘r，所有線程都會終止處理。

4 實驗及結(jié)果分析

使用安裝Window 10系統(tǒng)，使用3.20GHz AMD Phenom處理器，RAM為4GB的計算機作為測試環(huán)境。表1比較了使用傳統(tǒng)回溯法和使用拉斯維加斯算法，以及多線程拉斯維加斯算法在解決N后問題上使用的時間。

表1：回溯法與拉斯維加斯算法時間效率比較

可以看出，在N后問題中，使用拉斯維加斯算法能夠有效地加快獲取可行解需要的時間，其程序運行時間明顯優(yōu)于傳統(tǒng)回溯法，并且加速效果隨問題規(guī)模的擴大變得更加明顯。通過理論分析及實驗結(jié)果證明，拉斯維加斯算法解決N后問題是可行并且有效的。

5 結(jié)束語

在解決N后問題的方法中大多采用了回溯法，而拉斯維加斯算法解決N后問題時選擇最優(yōu)解需要更少的時間，得益于該算法的隨機性，可以降低求解算法的復雜度。本文使用了拉斯維加斯算法設計并實現(xiàn)了N后問題的解決辦法，并且結(jié)合線程的辦法對實現(xiàn)程序進行了優(yōu)化。拉斯維加斯算法有一定的缺陷，在后續(xù)的研究中，我們將從該算法的缺點著手，對拉斯維加斯算法進行改進，以獲得更好的算法效率。