棋盘覆盖问题.pptx

《棋盘覆盖问题.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Tromino谜题分治法分治法的基本思想对于一个规模为n的问题，若该问题可以容易地解决(比如说规模n较小)，则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并，得到原问题的解。这种算法设计策略叫做分治法(divideandconquer)。分治法的三个步骤分治法在每一层递归上由三个步骤组成：(1)划分(divide)：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。(2)解决(conquer)：若子问题规模较小，则直接求解；否则递归求解各子问题。(3)合并(combine)：将各子问

2、题的解合并为原问题的解。它的一般算法设计范型如下：DIVIDE&CONQUER(P)1if

3、P

4、≤c2thenreturn(DSOLVE(P))3elsedividePintokintoP1,P2,…,Pksubproblems4fori←1tok5dosi←DIVIDE&CONQUER(Pi)6S←COMBINE(s1,s2,…,sk)7returnS从分治法的一般设计模式可以看出，直接用它设计出的算法是一个递归算法。我们可用递归方程描述递归算法的运行时间。设T(n)表示用分治法求解规模为n的问题所需的计算时间，如果问题规模足够小，比如n≤c，则可直接求解问题，T(n)=Θ

5、(1)。假定将原问题分为k个子问题，每一个子问题规模是原问题的1/m，若分解该问题和合并该问题的时间分别为D(n)和C(n)，则算法的计算时间T(n)可表示为如下的递归方程：n≤cn>c如果n为m的幂，分解该问题和合并该问题的时间为f(n)，则该递归方程的解为子问题2的解子问题2的解原始问题的解原始问题的规模是n子问题1的规模是n/2子问题2的规模是n/2图解在一个2k×2k（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。棋盘覆盖问题要求用如图（b）所示的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且骨牌之间不得有重叠。(a)k=2时的一种棋

6、盘(b)4种不同形状的L型骨牌棋盘覆盖问题残缺棋盘是一个有2k×2k（k≥1）个方格的棋盘，其中恰有一个方格残缺。图4-7给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。①号②号③号④号这样的棋盘我们称作“三格板”，残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：1）两个三格板不能重叠2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格在这种限制条件下，所需要的三格板总数为(2k×2k-1)/3。棋盘覆盖问题1）问题分解过程如下：以k=2时的问题为例，用二分法进行分解，得到的是如下图，用双线划分的四个k=1的棋盘。但要注意这四个棋盘，并不都是与原

7、问题相似且独立的子问题。因为当如中的残缺方格在左上部时，第1个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘（也就是图中标识为2、3、4号子棋盘），并不是原问题的相似子问题，自然也就不能独立求解了。当使用一个①号三格板（图中阴影）覆盖2、3、4号三个子棋盘的各一个方格后，如4-8右图所示，我们把覆盖后的方格，也看作是残缺方格（称为“伪”残缺方格），这时的2、3、4号子问题就是独立且与原问题相似的子问题了。图一个4*4的残缺棋盘从以上例子还可以发现，当残缺方格在第1个子棋盘，用①号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；同样地（如下图所

8、示），当残缺方格在第2个子棋盘时，则首先用②号三格板进行棋盘覆盖，当残缺方格在第3个子棋盘时，则首先用③号三格板进行棋盘覆盖，当残缺方格在第4个子棋盘时，则首先用④号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。如下图：同样地k=1，2，3，4……都是如此，k=1为停止条件。图其它4*4的残缺棋盘分治策略2k-1×2k-12k-1×2k-12k-1×2k-12k-1×2k-1(a)棋盘分割(b)构造相同子问题技巧在于划分棋盘，使每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题k>2时，可将2^k×2^k的棋盘划分为4个2^（k-1）×2^（

9、k-1）的子棋盘，这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。分治策略2）棋盘的识别棋盘的规模是一个必要的信息，有了这个信息，只要知道其左上角的左上角方格所在行、列就可以唯一确定一个棋盘了，残缺方格或“伪”残缺方格