基于貪心算法的棋盤覆蓋著色技術(shù)

王利民 石晨陽

（河北建筑工程學(xué)院 河北省張家口市 075000）

1 引言

棋盤覆蓋問題是一種常見的編程問題，它主要是指在一個(gè)2k×2k個(gè)方格組成的棋盤中，選取一個(gè)方格與其他方格不同，稱為特殊方格，用4 種朝向各不相同的L 型骨牌（由3 個(gè)方格組成）對(duì)棋盤上除特殊方格以外的區(qū)域進(jìn)行覆蓋，且任何兩個(gè)L 型骨牌不得重疊覆蓋[1]。棋盤覆蓋著色是通過對(duì)棋盤方格賦予不同的顏色，以增加視覺表現(xiàn)力的效果。

其中在教學(xué)實(shí)踐中，為了形象的描述棋盤覆蓋問題，通常采取的方案是對(duì)L 型骨牌賦予不同的顏色。但是該算法存在著下列弊端：

（1）當(dāng)棋盤方格眾多時(shí)，對(duì)顏色數(shù)量的需求較多，導(dǎo)致界面整潔度較差。

（2）兩個(gè)相鄰的L 型骨牌的顏色接近導(dǎo)致界面的顯示效果不直觀。

為了有效的解決棋盤覆蓋著色問題存在的上述弊端，需要對(duì)棋盤覆蓋著色算法進(jìn)行研究。為此，本文提出了基于貪心算法的棋盤覆蓋著色技術(shù)，將其與現(xiàn)有的算法結(jié)合起來，利用3 種顏色實(shí)現(xiàn)棋盤覆蓋的著色，以達(dá)到直觀簡(jiǎn)潔的顯示效果，并使該問題在教學(xué)實(shí)踐中能夠更加直觀的展示可視化界面。其獨(dú)創(chuàng)性主要表現(xiàn)在利用有限的顏色清晰的展示棋盤覆蓋的問題。

2 實(shí)現(xiàn)原理

2.1 棋盤覆蓋技術(shù)的基本設(shè)計(jì)思想

棋盤覆蓋問題是《算法設(shè)計(jì)與分析》課程中講解分治法的重要案例[1]，具體過程如下：

當(dāng)k>0 時(shí)，將2k×2k棋盤分割為4 個(gè)2k-1×2k-1子棋盤，如圖1所示。特殊方格必位于4 個(gè)較小子棋盤之一中，其余3 個(gè)子棋盤中無特殊方格。為了將這3 個(gè)無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè)L 型骨牌覆蓋這3 個(gè)較小棋盤的會(huì)合處，如圖2所示，從而將原問題轉(zhuǎn)化為4 個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割方法，直至棋盤簡(jiǎn)化為1×1 棋盤[1]。

2.2 現(xiàn)有的棋盤覆蓋著色技術(shù)

針對(duì)棋盤覆蓋問題的著色技術(shù)一般情況下采取的解決方案是對(duì)每個(gè)L 型骨牌賦予不同的顏色，并利用當(dāng)前L 型骨牌的顏色對(duì)代表棋盤方格進(jìn)行著色，當(dāng)k=2 時(shí)，即棋盤由22×22=4×4 個(gè)方格組成時(shí)，除特殊方格以外，還需（22×22-1）/3=5 種顏色對(duì)代表棋盤的棋盤方格進(jìn)行著色，如圖3，但當(dāng)k ＞2 時(shí)，隨著k 的增加，需要的顏色種類以冪次方增長(zhǎng)，當(dāng)k=3,除特殊方格以外還需（23×23-1）/3=21種顏色如圖4，也就是說代表棋盤方格被覆蓋的顏色也越來越多，且相鄰的L 型方格之間的顏色也越來越相近。

盡管該解決方案能實(shí)現(xiàn)棋盤覆蓋著色的有效性，同時(shí)也解決了圖5 相鄰L 型棋盤賦予相似（標(biāo)注2 與3 方格）顏色的問題，但是當(dāng) k 值較大時(shí)，所需顏色眾多、顏色相似等問題越發(fā)明顯，也就是說棋盤覆蓋的顯示特性和展示效果并不明了，因此該方案需要進(jìn)一步改進(jìn)。

2.3 基于貪心算法的棋盤覆蓋著色技術(shù)的思路

貪心算法總是做出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。貪心算法的基本思路是從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo),以盡可能快地求得更好的解[1]。

根據(jù)貪心算法的定義及基本思路，基于貪心算法的棋盤覆蓋著色技術(shù)主要通過以下原理：

（1）將所有覆蓋棋盤的L 型骨牌進(jìn)行標(biāo)號(hào)。

（2）判斷當(dāng)前L 型骨牌和周圍L 型骨牌的大小。

（3）對(duì)不同的L 型骨牌依次賦值3 種不同的顏色。

3 關(guān)鍵程序流程圖及實(shí)現(xiàn)

其實(shí)現(xiàn)流程如圖6所示。

其具體實(shí)施方案如下：

（1）利用分治法完成棋盤的L 型骨牌覆蓋算法，并對(duì)每個(gè)棋盤方格進(jìn)行標(biāo)號(hào)；

（2）按照序號(hào)將對(duì)應(yīng)方格的橫縱坐標(biāo)保存在一個(gè)新的數(shù)組boardList[]中；

（3）根據(jù)數(shù)組首列數(shù)值確定該行是否為特殊方格（首列記錄該行保存的特殊方格個(gè)數(shù)，L 型骨牌為3 個(gè)，特殊方格為1 個(gè)）；

（4）橫縱坐標(biāo)依次判斷當(dāng)前骨牌周圍骨牌所存儲(chǔ)的骨牌序號(hào)；

（5）如果周圍骨牌序號(hào)比當(dāng)前骨牌序號(hào)小，則保存在新的數(shù)組boardAround[]中；

（6）從0 序號(hào)骨牌開始，依次判斷周邊是否存在序號(hào)小于當(dāng)前序號(hào)的骨牌；

圖1

圖2

圖3

圖4

圖5

圖6

圖7

圖8

圖9

（7）否，則將當(dāng)前骨牌對(duì)應(yīng)的方格賦值為顏色1；

（8）是，則按照序號(hào)順序依次判斷當(dāng)前骨牌的周圍骨牌是否存在顏色1，若是，按照骨牌序號(hào)順序?qū)?dāng)前骨牌對(duì)應(yīng)的方格賦值為顏色2，依次遍歷，最終找到與小于當(dāng)前骨牌次序的周邊骨牌顏色不沖突的最小顏色。

該方案可以用較少的顏色顯示所有骨牌，因此可以采用對(duì)比鮮明的少數(shù)幾種顏色即可，實(shí)踐證明棋盤覆蓋問題的著色方案只需要的三種顏色即可實(shí)現(xiàn)，故實(shí)際選用了綠、紅、藍(lán)三色，最終圖案色彩艷麗，對(duì)比鮮明。

4 實(shí)現(xiàn)結(jié)果與分析

為了檢驗(yàn)本文算法的有效性，分別對(duì)現(xiàn)有的著色技術(shù)方法和本文提出的著色方法技術(shù)進(jìn)行比較，我們?cè)O(shè)置k=4 的情形，此時(shí)當(dāng)k=4 時(shí)，一共有24×24=256 個(gè)方格，除特殊方格以外還需（24×24-1）/3=85 個(gè)L 型骨牌，標(biāo)號(hào)如圖7所示，針對(duì)現(xiàn)有棋盤覆蓋著色技術(shù)而言也就是除特殊方格以外還需要85 種顏色，其著色后的棋盤顯示如圖8所示,此時(shí)在同樣的條件下，而基于貪心算法的棋盤覆蓋著色方法，其顯示效果如圖9所示（其中為了描述特殊方格在棋盤中所處的位置，將特殊方格由綠色改為黑色，以便觀察棋盤著色后的顯示效果，其目的是使得整體的圖形界面更加清晰）。

從圖8 中我們可以看出該算法雖然能夠展現(xiàn)棋盤覆蓋問題的特性，但是其中所需的顏色數(shù)量極其龐大，同時(shí)顏色的相似性也較高，并未達(dá)到直觀的顯示效果，相反圖9所示的結(jié)果則表明覆蓋棋盤所需的顏色數(shù)量極少、且顏色對(duì)比鮮鮮明，能夠直觀的反應(yīng)棋盤覆蓋問題的特性。

4 結(jié)論

針對(duì)現(xiàn)有棋盤覆蓋著色的技術(shù)在棋盤覆蓋顯示上面臨的問題，深入研究了該算法的特性，并針對(duì)棋盤覆蓋著色所需顏色眾多和顯示效果不直觀的問題了提出了基于貪心算法的棋盤覆蓋著色技術(shù)，最終在實(shí)踐中完成了用三種顏色顯示棋盤覆蓋的效果，為今后研究其他類似相關(guān)著色領(lǐng)域奠定了基礎(chǔ)。