算法分析与设计PPT03-递归与分治 - 6 棋盘覆盖.ppt

1、3.2.5 棋盘覆盖棋盘覆盖问题问题在一个在一个 2k2k个方格组成的棋盘中，若恰有一个方格与其他方格不个方格组成的棋盘中，若恰有一个方格与其他方格不同，称该方格为特殊方格，且称该棋盘为特殊棋盘（同，称该方格为特殊方格，且称该棋盘为特殊棋盘（Defective Chessboard）。）。l 特殊方格在棋盘中出现的位置有特殊方格在棋盘中出现的位置有 4k种情形，种情形，就就有有4k种不同的棋盘。种不同的棋盘。图中的特殊棋盘是当图中的特殊棋盘是当 k2时时16个特殊棋盘中一个。在棋盘覆盖问题个特殊棋盘中一个。在棋盘覆盖问题中，要求用图所示的中，要求用图所示的4种不同形状的种不同形状的L型骨牌覆盖

2、给定棋盘上除特殊型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何两个方格以外的所有方格，且任何两个L型骨牌不得重叠覆盖。在任何一型骨牌不得重叠覆盖。在任何一个个个个 2k2k的棋盘覆盖中，用到的的棋盘覆盖中，用到的L型骨牌个数为型骨牌个数为（4k-1)/3。13.2.5 棋盘覆盖棋盘覆盖问题问题用分治策略，可以设计解棋盘覆盖问题的一个简捷算法。用分治策略，可以设计解棋盘覆盖问题的一个简捷算法。分治的技巧在于如何划分棋盘，使划分后的子棋盘大小相分治的技巧在于如何划分棋盘，使划分后的子棋盘大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题同，并且每个子棋盘均包含一个特殊方格，从而将原问题

3、分解为规模较小的棋盘覆盖问题。分解为规模较小的棋盘覆盖问题。l 当当k0时，将时，将2k2k的棋盘划分为的棋盘划分为4个个2k-12k-1子棋盘。子棋盘。l 原棋盘只有一个特殊方格，原棋盘只有一个特殊方格，则则其余其余3个子棋盘中没有特殊方格。个子棋盘中没有特殊方格。l 用一个用一个L型骨牌覆盖这型骨牌覆盖这3个较小棋盘的会合处。从而将原问题转化个较小棋盘的会合处。从而将原问题转化为为4个较小规模的棋盘覆盖问题个较小规模的棋盘覆盖问题，以便采用递归方法求解。以便采用递归方法求解。l 递归地使用这种划分策略，直至将棋盘分割为递归地使用这种划分策略，直至将棋盘分割为11的子棋盘。的子棋盘。2采用分

4、治算法解决棋盘覆盖问题的数据结构采用分治算法解决棋盘覆盖问题的数据结构令令size=2k，表示棋盘的规格。，表示棋盘的规格。1.棋盘棋盘：使用二维数组表示：使用二维数组表示：l int board10251025;l 为了方便递归调用，将数组为了方便递归调用，将数组board设为全局变量。设为全局变量。board00是棋是棋盘的左上角方格。盘的左上角方格。2.子子棋盘：由棋盘左上角的坐标棋盘：由棋盘左上角的坐标tr，tc和棋盘大小和棋盘大小s表示。表示。3.特殊特殊方格：在二维数组中的坐标位置是（方格：在二维数组中的坐标位置是（dr，dc）。）。4.L型骨牌：用到的型骨牌：用到的L型骨牌个数型骨牌个数为为（4k-1)/3，将所有，将所有L型骨牌从型骨牌从1开始连续编号，用一个全局变量表示：开始连续编号，用一个全局变量表示：static int tile=1;3棋盘覆盖问题的分治算法棋盘覆盖问题的分治算法