[摘要]采用分治法解决L型骨牌覆盖问题,给出了逻辑结构清晰的递归算法，并用Java语言加以实现。
　　[关键词]Java 分治 递归 L型骨牌
　　中图分类号：TP309.05 文献标识码：A 文章编号：1671－7597(2008)0910087－01
　　
　　一、引言
　　
　　分治算法是算法设计与分析中用的较多的一种有效算法，它的基本思想是将问题分解成若干子问题，然后求解子问题，子问题较原问题无疑是要容易些，由此得出原问题的解，就是所谓“分而治之”的意思。分治策略还可以递归进行，即子问题仍然可以用分治策略来进行，最后的问题是非常基本且简单的。解决L型骨牌覆盖问题就是分治算法的典型应用。
　　
　　二、问题的提出
　　
　　在一个个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊的棋盘，这种特殊方格的位置有种。如图1就是当时的特殊棋盘。棋盘覆盖问题中，我们要用图2所示4种不同形态的L形骨牌覆盖一个特殊棋盘，且任何2个L型骨牌不得重叠覆盖。
　　
　　图2四种不同形态的L型骨牌
　　
　　三、分治算法及分析
　　
　　当时，将 棋盘分割为4个子棋盘，特殊方格必位于4个子棋盘之一，其余3个子棋盘中无特殊方格，为此将剩余3棋盘转化为特殊棋盘，用一个L型骨牌覆盖这3个较小棋盘的结合处，如图3所示。这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为
　　棋盘。
　　
　　
　　设为覆盖特殊棋盘的时间，当时覆盖它需要常数时间
　　，当时，测试哪个子棋盘特殊以及形成3个特殊子棋盘需要时间，覆盖4个残缺子棋盘需四次递归调用，共需 ，所以
　　
　　四、Java实现
　　
　　二维数组Board表示棋盘；全局变量title初始值为0表示骨牌编号；tr，tc分别表示棋盘左上角的行/列号；dr，dc表示特殊方格所在的行/列号；size表示棋盘的大小。
　　（一）源代码
　　private void ChessBoard(int tr, int tc, int dr, int dc, int size) {
　　if (size > 1) {
　　int s = size / 2, t = ++tile;
　　//涂第一象限
　　 if (dr < tr + s && dc < tc + s) {// 特殊方塊就在第一象限
　　ChessBoard(tr, tc, dr, dc, s);
　　}
　　else {//特殊方块不在第一象限
　　// 第一象限的右下角方块赋值为t(tile)
　　Board[tr + s - 1][tc + s - 1] = t;
　　// 涂第一象限其余的方块
　　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 {//第二象限的左下角方块赋值为t(tile)
　　Board[tr + s - 1][tc + s] = t;
　　//涂第二象限其余的方块
　　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 {// 第三象限的右上角方块赋值为t(tile)
　　Board[tr + s][tc + s - 1] = t;
　　//涂第三象限其余的方块
　　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 {// 第四象限的左上角方块赋值为t(tile)
　　Board[tr + s][tc + s] = t;
　　//涂第四象限其余的方块
　　ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
　　
　　}
　　}
　　}
　　（二）运行结果
　　本文选取时L型骨牌覆盖问题的运行结果，分别如图4，图5，图6所示。
　　
　　五、结束语
　　
　　本文给出了L型骨牌覆盖问题的分治算法的详细设计过程，并给出源代码和运行结果图。由此我们可以总结出分治法所能解决的问题一般具有以下几个特征：①该问题的规模缩小到一定的程度就可以容易的解决；②该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；③利用该问题分解出的子问题的解可以合并为该问题的解；④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
　　
　　参考文献：
　　[1][美]Adam Drozdek. 数据结构与算法(Java 语言版)[M]. 周翔, 王建芬, 黄小青等译，北京:机械工业出版社，2003.
　　[2]电子科技大学数学实验精品课程：图论实验三个案例.http://202.115.
　　21.138/wlxt/ncourse/mathlab/web/jp2/3B.asp.
　　
　　作者简介：
　　崔建弘，女，河北石家庄人，教师，硕士，主要研究领域为系统优化。
　　
　　注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”