棋盤覆蓋問題

棋盤覆蓋問題

棋盤覆蓋問題,是一種編程問題。 如何套用分治法求解棋盤覆蓋問題呢?分治的技巧在於如何劃分棋盤,使劃分後的子棋盤的大小相同,並且每個子棋盤均包含一個特殊方格,從而將原問題分解為規模較小的棋盤覆蓋問題。k>0時,可將2^k×2^k的棋盤劃分為4個2^(k-1)×2^(k-1)的子棋盤,如圖4.11(a)所示。這樣劃分後,由於原棋盤只有一個特殊方格,所以,這4個子棋盤中只有一個子棋盤包含該特殊方格,其餘3個子棋盤中沒有特殊方格。為了將這3個沒有特殊方格的子棋盤轉化為特殊棋盤,以便採用遞歸方法求解,可以用一個L型骨牌覆蓋這3個較小棋盤的會合處,如圖4.11(b)所示,從而將原問題轉化為4個較小規模的棋盤覆蓋問題。遞歸地使用這種劃分策略,直至將棋盤分割為1×1的子棋盤。

基本信息

問題

在一個2^k×2^k (k≥0)個方格組成的棋盤中,恰有一個方格與其他方格不同,稱該方格為特殊方格。顯然,特殊方格在棋盤中可能出現的位置有4^k種,因而有4^k種不同的棋盤,圖4.10(a)所示是k=2時16種棋盤中的一個。棋盤覆蓋問題(chess cover problem)要求用圖4.10(b)所示的4種不同形狀的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格,且任何2個L型骨牌不得重疊覆蓋。

棋盤覆蓋問題 棋盤覆蓋問題

想法

如何套用分治法求解棋盤覆蓋問題呢?分治的技巧在於如何劃分棋盤,使劃分後的子棋盤的大小相同,並且每個子棋盤均包含一個特殊方格,從而將原問題分解為規模較小的棋盤覆蓋問題。k>0時,可將2^k×2^k的棋盤劃分為4個2^(k-1)×2^(k-1)的子棋盤,如圖4.11(a)所示。這樣劃分後,由於原棋盤只有一個特殊方格,所以,這4個子棋盤中只有一個子棋盤包含該特殊方格,其餘3個子棋盤中沒有特殊方格。為了將這3個沒有特殊方格的子棋盤轉化為特殊棋盤,以便採用遞歸方法求解,可以用一個L型骨牌覆蓋這3個較小棋盤的會合處,如圖4.11(b)所示,從而將原問題轉化為4個較小規模的棋盤覆蓋問題。遞歸地使用這種劃分策略,直至將棋盤分割為1×1的子棋盤。

棋盤覆蓋問題 棋盤覆蓋問題

算法實現

下面討論棋盤覆蓋問題中數據結構的設計。

(1)棋盤:可以用一個二維數組board[size][size]表示一個棋盤,其中,size=2^k。為了在遞歸處理的過程中使用同一個棋盤,將數組board設為全局變數;

(2)子棋盤:整個棋盤用二維數組board[size][size]表示,其中的子棋盤由棋盤左上角的下標tr、tc和棋盤大小s表示;

(3)特殊方格:用board[dr][dc]表示特殊方格,dr和dc是該特殊方格在二維數組board中的下標;

(4) L型骨牌:一個2^k×2^k的棋盤中有一個特殊方格,所以,用到L型骨牌的個數為(4^k-1)/3,將所有L型骨牌從1開始連續編號,用一個全局變數t表示。

設全局變數t已初始化為0,分治法求解棋盤覆蓋問題的算法用C++語言描述如下:

void ChessBoard(int tr, int tc, int dr, int dc, int size)

{

int s, t1; //t1表示本次覆蓋所用L型骨牌的編號

if (size == 1) return; //棋盤只有一個方格且是特殊方格

t1 = ++t; // L型骨牌編號

s = size/2; // 劃分棋盤

if (dr < tr + s && dc < tc + s) //特殊方格在左上角子棋盤中

ChessBoard(tr, tc, dr, dc, s); //遞歸處理子棋盤

else{ //用 t1號L型骨牌覆蓋右下角,再遞歸處理子棋盤

board[tr + s - 1][tc + s - 1] = t1;

ChessBoard(tr, tc, tr+s-1, tc+s-1, s);

}

if (dr < tr + s && dc >= tc + s) //特殊方格在右上角子棋盤中

ChessBoard(tr, tc+s, dr, dc, s); //遞歸處理子棋盤

else { //用 t1號L型骨牌覆蓋左下角,再遞歸處理子棋盤

board[tr + s - 1][tc + s] = t1;

ChessBoard(tr, tc+s, tr+s-1, tc+s, s);

}

if (dr >= tr + s && dc < tc + s) //特殊方格在左下角子棋盤中

ChessBoard(tr+s, tc, dr, dc, s); //遞歸處理子棋盤

else { //用 t1號L型骨牌覆蓋右上角,再遞歸處理子棋盤

board[tr + s][tc + s - 1] = t1;

ChessBoard(tr+s, tc, tr+s, tc+s-1, s);

}

if (dr >= tr + s && dc >= tc + s) //特殊方格在右下角子棋盤中

ChessBoard(tr+s, tc+s, dr, dc, s); //遞歸處理子棋盤

else { //用 t1號L型骨牌覆蓋左上角,再遞歸處理子棋盤

board[tr + s][tc + s] = t1;

ChessBoard(tr+s, tc+s, tr+s, tc+s, s);

}

}

算法分析

設T(k)是算法ChessBoard覆蓋一個2^k×2^k棋盤所需時間,從算法的劃分

策略可知,T(k)滿足如下遞推式:

T(k) = 1 當k=0時

T(k) = 4T(k-1) 當k>0時

解此遞推式可得T(k)=O(4^k)。

相關詞條

相關搜尋

熱門詞條

聯絡我們