棋盘覆盖问题.ppt

棋盘覆盖问题;分治法;分治法的三个步骤;它的一般算法设计范型如下： DIVIDECONQUER (P) 1 if |P|≤c 2 then return(DSOLVE(P)) 3 else divide P into k into P1, P2, …, Pk subproblems 4 for i ← 1 to k 5 do si ← DIVIDECONQUER(Pi) 6 S←COMBINE(s1, s2, …, sk) 7 return S ; 从分治法的一般设计模式可以看出， 直接用它设计出的算法是一个递归算法。我们可用递归方程描述递归算法的运行时间。 设T(n)表示用分治法求解规模为n的问题所需的计算时间，如果问题规模足够小，比如n≤c，则可直接求解问题，T(n)=Θ(1)。 假定将原问题分为k个子问题，每一个子问题规模是原问题的1/m， 若分解该问题和合并该问题的时间分别为D(n)和C(n)，则算法的计算时间T(n)可表示为如下的递归方程： ;;在一个2k×2k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。 棋盘覆盖问题要求用如图（b）所示的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且骨牌之间不得有重叠。; 残缺棋盘是一个有2k×2k （k≥1）个方格的棋盘，其中恰有一个方格残缺。图4-7给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。 ? ①号 ②号 ③号 ④号 这样的棋盘我们称作“三格板”，残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求： 1）两个三格板不能重叠 2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格 在这种限制条件下，所需要的三格板总数为(2k×2k -1 )/3。 ; 1）问题分解过程如下： 以k=2时的问题为例，用二分法进行分解，得到的是如下图，用双线划分的四个k=1的棋盘。但要注意这四个棋盘，并不都是与原问题相似且独立的子问题。因为当如中的残缺方格在左上部时，第1个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘（也就是图中标识为2、3、4号子棋盘），并不是原问题的相似子问题，自然也就不能独立求解了。当使用一个①号三格板（图中阴影）覆盖2、3、4号三个子棋盘的各一个方格后，如4-8右图所示，我们把覆盖后的方格，也看作是残缺方格（称为“伪”残缺方格），这时的2、3、4号子问题就是独立且与原问题相似的子问题了。 ;从以上例子还可以发现，当残缺方格在第1个子棋盘，用①号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；同样地（如下图所示），当残缺方格在第2个子棋盘时，则首先用②号三格板进行棋盘覆盖，当残缺方格在第3个子棋盘时，则首先用③号三格板进行棋盘覆盖，当残缺方格在第4个子棋盘时，则首先用④号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。如下图：;分治策略;k2时，可将2^k×2^k的棋盘划分为4个2^（k-1）×2^（k-1）的子棋盘，这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。;;;;;;;;;;;2）棋盘的识别 棋盘的规模是一个必要的信息，有了这个信息，只要知道其左上角的左上角方格所在行、列就可以唯一确定一个棋盘了，残缺方格或“伪”残缺方格直接用行、列号记录。 ? tr 棋盘中左上角方格所在行。 ? tc 棋盘中左上角方格所在列。 ? dr 残缺方块所在行。 ? dl 残缺方块所在列。 ? size 棋盘的行数或列数。;下面介绍棋盘覆盖问题中数据结构的设计： （1）棋盘：用二维数组board[size][size]表示一个棋盘，其中，size=2k。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量； （2）子棋盘：在棋盘数组board[size][size]中，由子棋盘左上角的下标tr、tc和棋盘边长s表示； （3）特殊方格：用board[dr][dc]表示，dr和dc是该特殊方格在棋盘数组board中的下标;