《棋盘覆盖问题（精品PPT） .ppt》由会员分享，可在线阅读，更多相关《棋盘覆盖问题（精品PPT） .ppt（19页珍藏版）》请在三一办公上搜索。
1、棋盘覆盖问题,问题描述（一）,在一个（k0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格，显然，特殊方格在棋盘中出现的位置有 中情形，因而有 中不同的棋盘(如图(a)。,(a)k=2时的一种棋盘,问题描述（二）,棋盘覆盖问题要求用如图(b)所示的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。,(b)4种不同形状的L型骨牌,问题分析（一）,用分治策略，可以设计解棋盘覆盖问题的一个简洁算法(1)当k0时,将 棋盘分割为4个 子棋盘(如下图(c)；,2k-12k-1,2k-12k-1,2k-12k-1,2k-12k-1,特殊方格必位于4个子棋盘
2、之一，其余3个子棋盘中无特殊方格。,(c)棋盘分割,问题分析（二）,(2)用一个L型骨牌覆盖这3个较小棋盘的结合处。(如图(d),这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的残缺方格,原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为11棋盘。,(d)构造相同子问题,详细过程图解,如下棋盘中有一个特殊方格,第一次分割,第二次分割,第三次分割,第四次分割为11棋盘,第一次分割后子棋盘的覆盖结果,问题求解,下面介绍棋盘覆盖问题中数据结构的设计：（1）棋盘：用二维数组Boardsizesize表示一个棋盘，Board00是棋盘的左上角方格。其中，size=。为了在递归处
3、理的过程中使用同一个棋盘，将数组Board设为全局变量；（2）子棋盘：在棋盘数组Boardsizesize中，由子棋盘左上角的下标tr、tc和棋盘边长s表示；,（3）特殊方格：用Boarddrdc表示，dr和dc是该特殊方格在棋盘数组Board中的下标；（4）L型骨牌：一个 的棋盘中有一个特殊方格，所以用到L型骨牌的个数为(-1)/3将所有L型骨牌从1开始连续编号，用一个全局整型变量tile表示，其初始值为0。,算法的输入参数是：tr:棋盘左上角方格的行号 tc:棋盘左上角方格的列号 dr:特殊方格所在的行号 dc:特殊方格所在的列号 size:size=,棋盘规格为,算法棋盘覆盖,实现这种分
4、治策略的算法ChessBoard如下：void ChessBoard(int tr,int tc,int dr,int dc,int size)/tr和tc是棋盘左上角的下标，dr和dc是特殊方格的下标，/size是棋盘的大小，t已初始化为0 if(size=1)return;/棋盘只有一个方格且是特殊方格 t+;/L型骨牌号 s=size/2;/划分棋盘/覆盖左上角子棋盘 if(dr tr+s,/覆盖右上角子棋盘 if(dr=tc+s)/特殊方格在右上角子棋盘中 ChessBoard(tr,tc+s,dr,dc,s);/递归处理子棋盘 else/用 t 号L型骨牌覆盖左下角，再递归处理子棋盘 boardtr+s-1tc+s=t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);/覆盖左下角子棋盘 if(dr=tr+s,时间复杂度分析,算法分析:设T(k)为覆盖 棋盘的时间,(1)k=0 覆盖它需要常数时间O(1)(2)k0 测试哪个子棋盘特殊以及形成3个特殊子棋盘需要O(1)覆盖4个特殊子棋盘需四次递归调用,共需时间,算法的时间复杂性递推式为：,解：,谢谢大家!,
