棋盘覆盖问题

在一个 2^k * 2^k 个方格组成的棋盘中,若恰有一个方格与其它方格不同,则称该方格为一特殊方格,称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有 4^k 种情形。因而对任何 k>=0 ,有 4^k 种不同的特殊棋盘。下图所示的特殊棋盘为 k=2 时 16 个特殊棋盘中的一个。

棋盘覆盖问题

在棋盘覆盖问题中,要用下图中 4 中不同形态的 L 型骨牌覆盖一个给定的特殊棋牌上除特殊方格以外的所有方格,且任何 2 个 L 型骨牌不得重叠覆盖。易知,在任何一个 2^k * 2^k 的棋盘中,用到的 L 型骨牌个数恰为 (4^k-1)/3 。

棋盘覆盖问题

用分治策略,可以设计解棋盘问题的一个简捷的算法。
当 k>0 时,将 2^k * 2^k 棋盘分割为 4 个 2^(k-1) * 2^(k-1) 子棋盘,如下图所示。

棋盘覆盖问题

特殊方格必位于 4 个较小子棋盘之一中,其余 3 个子棋盘中无特殊方格。为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘,我们可以用一个 L 型骨牌覆盖这 3 个较小的棋盘的汇合处,如下图所示,这 3 个子棋盘上被 L 型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而将原问题化为 4 个较小规模的棋盘覆盖问题。递归的使用 这种分割,直至棋盘简化为 1x1 棋盘。

棋盘覆盖问题

对于上面图一的示例,棋盘覆盖效果如下:

棋盘覆盖问题

 

c++代码如下:

L型

对应程序效果如下:

棋盘覆盖问题

参考文献:

1.       《算法设计与分析》 ------------------------------------------------------------------------- 王红梅编著   清华大学出版社
2.       棋盘覆盖算法                                                                                       http://riddickbryant.javaeye.com/blog/559388
3.       棋盘覆盖问题原理及演示程序                     http://www.cnblogs.com/lsxqw2004/archive/2008/10/16/1313086.html

再分享一下我老师大神的人工智能教程吧。零基础!通俗易懂!风趣幽默!还带黄段子!希望你也加入到我们人工智能的队伍中来!http://www.captainbed.net

上一篇:Fescar分布式事务实现原理解析探秘


下一篇:linux下使用tc流量控制命令模拟网络延迟和丢包