基于0-1規(guī)劃的五連珠問題求解

吳亞東，肖華勇

?

基于0-1規(guī)劃的五連珠問題求解

吳亞東，肖華勇

（西北工業(yè)大學(xué) 理學(xué)院，陜西 西安 710129）

五連珠問題是五子棋中抽象出來的問題，通過建立0-1規(guī)劃模型，求解得出一維、二維以及三維情況下五子連珠問題的可行解。類比晶體學(xué)中晶體的成核與生長過程，建立了晶胞構(gòu)成模型。相比單純的0-1規(guī)劃模型，晶胞構(gòu)成模型有運算規(guī)模小、運行速度快等優(yōu)點。拓展至高維度情況下的連珠問題，討論不同維數(shù)規(guī)劃模型的約束類型的個數(shù)。該模型對于N子連珠問題以及八皇后的求解有一定的借鑒意義。

五子連珠；晶胞構(gòu)成；0-1規(guī)劃；N維約束

五子連珠問題是基于五子棋演變而來，規(guī)則為在一個棋盤中的每個小方格子的中心點各放一個棋子，如果兩個棋子所在的小方格有公共邊或公共頂點，那么則稱這兩個棋子相連。

針對五連珠問題的規(guī)則要求，我們建立了0-1規(guī)劃模型，通過Lingo軟件編程得到了在一維、二維以及三維空間下的可行解[1]。借鑒晶體學(xué)中晶體生長與晶胞構(gòu)成，建立了晶胞構(gòu)成模型求解連珠問題，討論了在N維空間下的五子連珠問題的約束類型數(shù)目。

1 0-1規(guī)劃模型建立

1.1 二維一般問題

以6×7的長方形棋盤為例，對前5列，每行至少需要去掉1個棋子，則前5列至少需要去掉6個棋子。對后兩列，每列至少需要去掉1個棋子，因此后兩列至少需要去掉2個棋子。則總的至少需要去掉8個棋子。如圖1所示。

圖2是一種去掉8個棋子而能滿足條件的方式。

圖1 6×7長方形棋盤

圖2 6×7情況的一種解法

1.2 二維一般模型

對×的五連珠問題，建0-1決策變量[2-4]，設(shè)

去掉棋子數(shù)最少的目標函數(shù)設(shè)為：

每行連續(xù)5個格子中至少要去掉一個棋子，則有：

每列連續(xù)5個格子中至少要去掉一個棋子，則有：

每條反斜線上連續(xù)5個格子中至少要去掉一個棋子，則有：

每條正斜線上連續(xù)5個格子中至少要去掉一個棋子，則有：

因此總的線性規(guī)劃模型為：

約束總數(shù)：

當=13，=17時，=556，其約束條件如下：

13×17的棋盤需要44個棋子。

圖3 13×17棋盤情況一種解法

1.3 三維一般模型

對××的五連珠問題，建0-1決策變量，設(shè)

去掉棋子數(shù)最少的目標函數(shù)為：

三個方向分別稱為、及軸方向。

圖4 4條空間對角線方向示意圖

（1）只變一個方向的約束：

（2）變兩個方向的約束：

（3）變?nèi)齻€方向的約束

總共約束有3+6+4=13類。

約束總數(shù)：

線性規(guī)劃模型為：

對于6×7×6棋盤，求解結(jié)果為64。

2 晶體生長模型建立

建立的0-1規(guī)劃模型，可以求解小規(guī)模低維度的問題，但對于高維度大規(guī)模的棋盤，其求解速度有待提高。為此我們引入晶體學(xué)中晶胞的概念以簡化問題。

晶胞：構(gòu)成晶體的最基本的幾何單元，是能完整反映晶體內(nèi)部原子或離子在三維空間分布之化學(xué)結(jié)構(gòu)特征的平行六面體最小單元[5]。

2.1 一維晶胞模型

當我們將二維問題降維到一維問題（以=13為例）時，其一般的結(jié)果如圖5所示。

圖5 一維一般問題

從圖5可以發(fā)現(xiàn)，黑棋子總是每隔4個就出現(xiàn)一次，同理，5連續(xù)的5個棋子可以看做是一個循環(huán)單元，如果恰巧就是5的整數(shù)倍，那么只是循環(huán)單元在反復(fù)地、完整地出現(xiàn)，這與晶胞的概念類似。將連續(xù)的5個棋子視為“一維晶胞”，一維棋盤的增長、擴張就類似晶體由晶核生長為晶體的過程?？梢詫栴}簡化如下：首先求解出一個有效的晶胞，然后讓其“生長”為邊長是5的整數(shù)倍的棋盤，最后根據(jù)給定的棋盤大小從中統(tǒng)計出最少的棋子的排列方式。例如，對于邊長為13的棋盤來講，先求解邊長為5棋盤，再將其平移復(fù)制2個成為邊長為15的棋盤，統(tǒng)計連續(xù)13個格子中黑子的數(shù)目，即可找到最少黑子的邊長為13的棋盤分布，此為一個可行解。避免了直接求解大規(guī)模棋盤就可以得到可行解，而且還可能得到多個可行解。

2.2 二維晶胞模型

二維13×17棋盤的一種解如圖6所示。

可以發(fā)現(xiàn)類二維棋盤中的二維晶胞（圖6中虛線內(nèi)部分），其大小為5×5。求解二維晶胞的思路可以用圖7-圖9示意。

一張二維平面，將其上下連接在一起，左右也連接在一起，兩個斜對角線也連接在一起，見圖7。由平面變成圓筒，再變?yōu)閳A環(huán)，見圖8。在每一個點處的橫向、縱向、斜向都滿足五連珠條件，則可得到原平面的二維晶胞，見圖9。

圖7 有效晶胞的約束方式

圖8 二維有效晶胞約束示意圖

圖9 二維有效晶胞

有了二維晶胞以后，對其進行平移復(fù)制為20×25的二維棋盤，從中統(tǒng)計出以13、17為邊長的長方形棋盤內(nèi)最少的黑子數(shù)目（44個），得到圖10中的2種完全不同的解，其中的一種在之前未求解出。若對其進行對稱、旋轉(zhuǎn)變換可得到更多的可行解。