棋盘覆盖问题(精品PPT) .ppt
《棋盘覆盖问题(精品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=。为了在递归处
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 棋盘覆盖问题精品PPT 棋盘 覆盖 问题 精品 PPT
链接地址:https://www.31ppt.com/p-2698137.html