基于Spark平臺的多皇后問題并行求解

摘 要：針對傳統(tǒng)運行于單機上的多皇后問題求解算法計算效率低的問題，本文基于分布式計算平臺Spark，設計了一種集群環(huán)境下的多皇后問題求解并行化方案，實現(xiàn)了利用集群資源求解多皇后問題的并行算法。對回溯法進行了改進，有效的縮小解空間。

關鍵詞：并行計算;Spark;多皇后問題;回溯法

N皇后問題是計算方面的一個經(jīng)典的NP難問題，它的特點是隨著皇后數(shù)目N的增加，計算時間呈指數(shù)增長。對于高位數(shù)的皇后問題求解，傳統(tǒng)的串行求解算法往往無法再可接受的時間內(nèi)完成。然而，單機上的運算資源是有限的，基于單機多核的并行解決方案，并不能從保證能求的高位數(shù)皇后問題的解。本文基于分布式計算平臺Spark，采用經(jīng)典的回溯法，設計了一種集群環(huán)境下的多皇后問題求解并行化方案，實現(xiàn)了利用集群資源求解多皇后問題的并行算法。

1.回溯法求解多皇后問題

回溯法在求解N皇后問題時，以深度優(yōu)先的順序對各個棋盤節(jié)點進行選擇判斷。用基本的經(jīng)典回溯法算法得到多皇后問題的全部有效解，需要對整個解空間進行搜索。當皇后問題的皇后個數(shù)n增大時，整個解空間的規(guī)模大約是n*n！，搜索的效率非常低。若把N*N的棋盤放置到一個二維數(shù)組時，n皇后問題有效解數(shù)的指數(shù)遞增性質(zhì)，隨著皇后個數(shù)的增加，需要的比較時間也會大規(guī)模增長。所以需要對基本回溯法進行改進，對其進行一定的改進和剪枝，減小回溯的解空間，減少比較次數(shù)。

2.1對基礎回溯法的改進

由于N皇后問題在使用基礎回溯算法時，會有比較次數(shù)和計算量過大的問題，特別是隨著皇后個數(shù)的增加，一絲微小的差別可能就會被無限放大。針對這些問題，本文在參考了文獻[2，3，4]中的改進方法后，對多皇后問題的基礎回溯算法進行了一些改進的探討。

2.2.1儲存數(shù)據(jù)結構的改變

文章將采取用一個一維數(shù)組來存放一個有效解空間樹分支，也就是說用一個一維的數(shù)組儲存一個有效解。主要優(yōu)點有

第一：可以減少儲存空間，顯而易見一個一維N位長的數(shù)組只有一個N*N二維數(shù)組N分之一的存儲空間;

第二：可以省去行沖突，多皇后問題一共有三種沖突：行、列、斜線。

第三：可以減少比較的次數(shù)。

2.2.2減少需要探測的放置點

對于回溯法解決多皇后問題，隨著N的個數(shù)的增長，需要探測的位置放大，且隨著解空間樹的增加，這一探測比較被明顯放大且隨著解空間樹的增加，這一探測比較被明顯放大，如四皇后問題一個解需要探測16個位置，有4的4次方個比較次數(shù)，而八皇后問題便需要探測64個位置，有8的8次方個比較次數(shù)，采用的是避免行列的沖突比較，即如果一個皇后成功放置以后，它所在的行和列即鎖定，不再進行探測。通過比可以發(fā)現(xiàn)，完全可以避免一些不必要的探測，如放置一個皇后后，它所在的行和列完全可以不再進行探測，即縮小了它的棋盤放置空間。這里我采用的是避免行列的沖突比較，即如果一個皇后成功放置以后，它所在的行和列即鎖定，不再進行探測。如圖1所示，放置第一個皇后后，進行行和列的消除后，便成了7*7的范圍。

放置第二個皇后后如圖2，第三個皇后的放置便成了6*6的范圍，比原來又少了一行和一列的探測范圍。

2.2.3利用棋盤對稱性減小解空間

棋盤是對稱的，對任意有效解的多皇后放置圖進行合理的旋轉也會得到一個有效解。結合分枝限界法對解空間進行一個大幅度的剪枝操作，可以極大的縮小解空間范圍。

由此特征，在多皇后問題上，可以得到以下兩個特征：

（1）對于多皇后問題，棋盤上的每一種合理放置，經(jīng)過有限次的水平，順時針，逆時針翻轉，仍然是一個有效的放置解法。

（2）對于多皇后問題，如果用result[i]表示合理布局中以i為第一個位置的布局的數(shù)量，則有這樣的一個等式：result[i]=result[n-i+1]。

在對多皇后問題的布局搜索時，可以利用對稱性的原理來減少一半的解空間狀態(tài)樹分支。利用布局的水平翻轉，對解空間進行優(yōu)化，大概能提升一倍左右的效率（也就是減少50%左右的分支）。下面將對改進方法進行具體的解釋。

以6皇后問題為例，6皇后問題共有4個有效解，布局圖如下：

通過圖可以發(fā)現(xiàn)，圖4（a）和圖4（b），圖4（c）與4（d）是左右對稱的，相當于旋轉了180度。進過分析，偶數(shù)個數(shù)的多皇后的放置問題，僅僅可以搜索以前2/n列為起始位置的解空間，若搜索到有效解，直接進行水平翻轉，得到后面的解，且不發(fā)生沖突。如果是奇數(shù)個數(shù)的多皇后的放置問題，對于最中間一列為起始位置有效解來說，直接進行翻轉，會造成重復解的問題。

因此，對多皇后問題的個數(shù)進行判斷，如果皇后個數(shù)n為偶數(shù)，則直接只搜索以第一行前n/2列為初始位置的解空間，然后對搜索到的合理布局進行水平翻轉，得到對稱布局。如果n為奇數(shù)，則搜索前2/（n+1）列，但是如果是第2/（n+1）列，則不對其搜索到的合理布局進行翻轉。

3多皇后問題并行化設計

為了并行實現(xiàn)多皇后問題的回溯解法，需要的是對該任務進行分解，將其分解成多個任務，然后，再將小的任務劃分到各個分節(jié)點上面，當分節(jié)點計算完畢后，再將計算結果整合在主節(jié)點中。采取平均劃分法，根據(jù)用戶輸入的需要求解的多皇后問題的皇后個數(shù)而分配任務。對于每一個分任務，會根據(jù)其首位置放置，對該分支的解空間進行回溯法搜索，然后對相應合理進行水平翻轉處理并記錄，最后返回結果給主節(jié)點，完成自己部分的計算。

在數(shù)據(jù)結構方面采用了一個N*N的二維數(shù)組表示（N代表皇后個數(shù)），但這個二維數(shù)組是N個任務共用的，每個任務用一個N維數(shù)組。此外，采用集合列表這種數(shù)據(jù)結構來與數(shù)組進行對比，并解決一些并行輸出順序可能混亂的問題。

4實驗結果與分析

實驗需要的Spark集群環(huán)境在虛擬機中搭建，集群中共3臺虛擬機（其中主節(jié)點1臺，從節(jié)點2臺），各虛擬機配置信息見表1。集群節(jié)點操作系統(tǒng)為CentOS 6.6，安裝有JDK 1.8，本文算法的實現(xiàn)基于Spark-2.1.1版本。

本文實驗分別在啟用了集群的1個工作節(jié)點（Spark集群單節(jié)點）和2個工作節(jié)點情況下進行，并與采用回溯法的傳統(tǒng)求解算法進行對比。實驗結果如表2所示。

從運行時間對比圖7可以看出：（1）在皇后數(shù)目較少時，多皇后問題并行求解算法與傳統(tǒng)的方法在計算效率上差別不明顯，因為集群內(nèi)部節(jié)點間通信需要消耗一定的時間。（2）隨著皇后數(shù)目的增多，基于Spark平臺的并行求解方法的優(yōu)勢會更突出。

5結論

文章基于分布式計算平臺Spark，設計了一種集群環(huán)境下的多皇后問題求解并行化方案，實現(xiàn)了利用集群資源求解多皇后問題的并行算法。對多皇后問題求解選取出可求出全部解的回溯法，并對該方法進行了改進，從而有效的縮小解空間。最后，通過實驗驗證了設計的多皇后問題并行求解算法的正確性，同時該方法具有高效的計算能力和較好的擴展特性。

參考文獻：

[1]鄭光勇 徐雨明 羅振庭. 基于混合化學反應優(yōu)化算法的N皇后問題研究 [J]. 數(shù)字技術與應用，2019，37（9）：116.

[2]鮑康勝. 從八皇后問題引發(fā)遞歸回溯算法的思考[J]. 電腦編程技巧與維護.2019， （5）： 32-34.

[3]原慧芳，于慧敏.改進回溯算法實現(xiàn)N皇后問題求解[J].電腦編程技巧與維護，2016（12）：15-16+34.

[4]王寧. 應用蟻群算法求解N皇后問題[J]. 現(xiàn)代交際：學術版.2016， （5）：245-246.

[5]葉均隆 葉均明 余偉紅.? 圖像思維解釋八皇后算法及其拓展問題[J]. 無線互聯(lián)科技. 2018， 15（22）： 106-107.

[6]姜學軍.武楓.黃海新.Spark大數(shù)據(jù)計算平臺[J]. 電子世界. 2018， （15）：82-84.

作者簡介：

代新曉（1986年3月）， 女，遼寧省東港市 ，碩士研究生 ，講師 ，研究方向：計算機網(wǎng)絡、大數(shù)據(jù).