L型骨牌覆盖问题(分治思想)

阅读数: 次 2020-05-08

概述

本文承接上文《求n个元素的全排序(从分治思想超详细解析)》)，将再用一个详细的案例来带我们更深入的理解分治思想在解决实际问题中的体现。

同时，在后文我会把将前文的知识整合起来写成《算法分析与设计实验》的实验报告2—递归与分治策略应用基础，分享给大家。同为大学狗的可以借鉴一下👴的微薄之作

L型骨牌覆盖问题

1.问题说明

在一个 2^k 2^k 方格组成的棋盘中，若恰有一个方格与其他方格不同，称该方格为特殊方格，且称该棋盘为特殊棋盘(Defective Chessboard)。下图的特殊棋盘是当k=2 时16个特殊棋盘中的一个，在棋盘覆盖问题中，要求用图示所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何俩个L型骨牌方格不得重叠。在任何一个2k2k 的覆盖棋盘中，用到的L型骨牌个数为(4^k-1)/3。

2.算法分析

同样，我们可以把这个问题利用分治思想拆分成一个一个的小问题。

分治的技巧在于如何划分棋盘，使划分后的子棋盘大小相同，并且每一个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。

当k>0时，将2k 2k的棋盘划分为4个2(k-1)2(k-1)子棋盘，我们可以推断出原棋盘只有一个特殊方格，则其余三个子棋盘中没有特殊方格。

由于我们是L型骨牌，所以这三个没有特殊方格的子棋盘的结合处我们可以正好用L型骨牌覆盖，一旦覆盖，他们在各自的子棋盘中又会变成棋盘覆盖问题，不过规模变小了，之后我们就可以逐步递归求解，直至将棋盘分割为1*1 的子棋盘。

这里解释一下结合处，比如左上棋盘的结合处就是右下角，右上棋盘的结合处就是左下角，反正就是对立的

由此，我们得出核心的算法思路：

把大棋盘先分成4个小棋盘
依次判断每个小棋盘里有没有特殊方格，如果没有，将结合处用L型骨牌覆盖上，注意这时候一旦覆盖说明在这个小棋盘中有了一个特殊方格(就是刚刚被覆盖掉的那一个格子)，我们需要递归。如果有，我们直接递归寻解。
一旦棋盘分割为1*1 的子棋盘表明递归终止。

3.代码实现

//L型骨牌从1开始连续编号
public static int number = 1;
public static int[][] board;//整形数组保存棋盘
public LshapeCover(int size) {
	this.board = new int[size][size];//size--棋盘的规格
}
/**
 * 棋盘覆盖函数
 * @param tr	标示当前所在棋盘的左上角行位置
 * @param tc	标示当前所在棋盘的左上角列位置
 * @param dr	标示特殊方格的行位置
 * @param dc	标示特殊方格的列位置
 * @param size
 */
public static void chessBorad(int tr,int tc,int dr,int dc,int size) {
	if(size==1)return;//递归终止条件
	int t = number++;
	int s = size/2;//分割棋盘
	//覆盖左上角棋盘
	if(dr<tr+s&&dc<tc+s) {
		//特殊方格在此子棋盘中
		chessBorad(tr, tc, dr, dc, s);
	}else {
		//此棋盘中无特殊方格，用t号L型骨牌覆盖右下角
		board[tr+s-1][tc+s-1]=t;
		//覆盖其余方格(也就是将刚刚的t号当作此子棋盘中的特殊方格去递归)
		chessBorad(tr, tc, tr+s-1, tc+s-1, s);
	}
	//覆盖右上角棋盘
	if(dr<tr+s&&dc>=tc+s) {
		//特殊方格在此子棋盘中
		chessBorad(tr, tc+s, dr, dc, s);
	}else {
		//此棋盘中无特殊方格，用t号L型骨牌覆盖左下角
		board[tr+s-1][tc+s]=t;
		//覆盖其余方格(也就是将刚刚的t号当作此子棋盘中的特殊方格去递归)
		chessBorad(tr, tc+s, tr+s-1, tc+s, s);	
	}
	//覆盖左下角棋盘
	if(dr>=tr+s&&dc<tc+s) {
		//特殊方格在此子棋盘中
		chessBorad(tr+s, tc, dr, dc, s);
	}else {
		//此棋盘中无特殊方格，用t号L型骨牌覆盖右上角
		board[tr+s][tc+s-1]=t;
		//覆盖其余方格(也就是将刚刚的t号当作此子棋盘中的特殊方格去递归)
		chessBorad(tr+s, tc, tr+s, tc+s-1, s);
	}
	//覆盖右下角棋盘
	if(dr>=tr+s&&dc>=tc+s) {
		//特殊方格在此子棋盘中
		chessBorad(tr+s, tc+s, dr, dc, s);
	}else {
		//此棋盘中无特殊方格，用t号L型骨牌覆盖左上角
		board[tr+s][tc+s]=t;
		//覆盖其余方格(也就是将刚刚的t号当作此子棋盘中的特殊方格去递归)
		chessBorad(tr+s, tc+s, tr+s, tc+s, s);
	}
}

测试代码

public static void main(String[] args) {
	LshapeCover lshapeCover = new LshapeCover(16);
	lshapeCover.chessBorad(0, 0, 2, 3, 16);
	for(int i=0; i<lshapeCover.board.length; i++) {
		for(int j=0; j<lshapeCover.board.length; j++) {
			System.out.print(String.format("%5d", lshapeCover.board[i][j]));
		}
		System.out.println();
	}
}

测试结果

 4    4    5    5    9    9   10   10   25   25   26   26   30   30   31   31
 4    3    3    5    9    8    8   10   25   24   24   26   30   29   29   31
 6    3    7    0   11   11    8   12   27   24   28   28   32   32   29   33
 6    6    7    7    2   11   12   12   27   27   28   23   23   32   33   33
14   14   15    2    2   19   20   20   35   35   36   36   23   40   41   41
14   13   15   15   19   19   18   20   35   34   34   36   40   40   39   41
16   13   13   17   21   18   18   22   37   37   34   38   42   39   39   43
16   16   17   17   21   21   22   22    1   37   38   38   42   42   43   43
46   46   47   47   51   51   52    1    1   67   68   68   72   72   73   73
46   45   45   47   51   50   52   52   67   67   66   68   72   71   71   73
48   45   49   49   53   50   50   54   69   66   66   70   74   74   71   75
48   48   49   44   53   53   54   54   69   69   70   70   65   74   75   75
56   56   57   44   44   61   62   62   77   77   78   65   65   82   83   83
56   55   57   57   61   61   60   62   77   76   78   78   82   82   81   83
58   55   55   59   63   60   60   64   79   76   76   80   84   81   81   85
58   58   59   59   63   63   64   64   79   79   80   80   84   84   85   85

结语

没想到吧，👴没分享实验报告，主要是我想了想，这两篇博文基本都涵盖了实验报告的全部内容，就不套娃了，基本上想白嫖一个实验报告的直接看一遍大概内容复制粘贴就完事了。

还有一个主要原因是👴也想复制粘贴去完成实验报告，直接复制markdown文字到doc上还得改字体大小，👴嫌麻烦，就委屈你们了。

一人之下3的片头曲真不错，爱了爱了。