覆盖问题解决技巧的深入探讨
纪 政,宋海岸
【摘 要】摘 要:覆盖问题是一种常见的问题,由于其状态复杂,数据规模大,直接的搜索往往效率过低,复杂度难以承受。从解决覆盖问题的一般方法出发,深入探讨了动态规划、数学归纳法,以及Dancing links算法的转化在覆盖问题中的应用,充分弥补了现今大多数书籍和文献中解决覆盖问题时忽视算法设计技巧的缺点。 【期刊名称】软件导刊 【年(卷),期】2010(009)009 【总页数】3
【关键词】精确覆盖;Dancing links;数独
0 引言
在理论和实际应用中,会遇见很多的覆盖问题,像走道铺砖,骨牌拼图,六形组和四条形。关于覆盖问题,一般会有3种解决思路:①状态形式简单时,可以对状态进行压缩,用动态规划解决;②转化为数学问题,用数学归纳法猜想答案,继而验证其正确性;③用深度搜索和回溯,遍历搜索树。以下针对以上3种方法进行举例讨论。
1 动态规划的运用
地砖只有1*2一种规格,而一个N*M(N*M为偶数)的走道,用N*M/2块1*2的地砖将其铺满,可以有多少种不同的设计方案,具体如图1、图2、图3所示。
由于只有一种砖,状态比较单一,转化过程中满足无后效性和局部最优性,因
而考虑运用动态规划解决之。用横线来划分阶段,对于图1,虽然划分后很整齐,但把某些砖分成了两半,于是将它们也添加进来,变成了图2,其显得参差不齐,但最多也是向下突出一格;在图3中,我们将图2的空隙填满,则又转移到了下一种状态。定义添砖小块状态为1,否则为0,则每行状态可以映射到一个数(0,2^h})。于是可建立这样的状态a[i:j]:表示第 i行填满,第 i+1 行对应状态为 j时的不同方案数,a[I,j]=∑a[i-1,k],其中,状态 k 可导出状态 j,初始化条件a[0,0]=1,最后 a[w,0]即为所求。 行数我们默认是从 0 开始。
图1:第3行填满了,第3行的第1个格子是一个竖形格子,这个竖形格子的上格子在第3行,下格子在第4行,于是在第4行需要补格子故置为1,第3行的第2个、第3个格子是个横条,我们都置为0,紧接着又是一个竖形格子的上半个格子,同样是0,下面两个都是竖形格子的下半个置为1,同理将分别对第4行第5行赋值。这样一来,我们以行为阶段,每个阶段维护2^N个当前的状态,一直计算到第N行,得到答案。
2 数学归纳法
已知一个等边三角形,每条边均被N等分,求可以组成的不同的凸六边形的数目。等分后的等边三角形状如图5所示。
如N=4时,有7个不同的凸六边形,如图6所示。
这个问题的突破口是要意识到每个凸六边形都可以包含在一个正三角形之中,且那个正三角形的每个角都被剪掉了且每个边都至少剩下了些。因为对于一个N等分的三角形来说,不同边长的三角形是可以直接得到的。可以很容易发现规律:
边长为 3 的三角一共会 sigm(1+2+3+…+(N-3))(N>2);边长为 4 的三角形有 sigm(1+2+3+…+(N-4))(N>3)个。
现在的问题回到原来的问题上来,还有一个难题没有被解决,那就是边长为N的三角形剪掉不同且在每边上都留下一段没剪掉的边的角会有多少个不同的凸六边形呢?假设剪去的三个角的边长依次是a,b,c,如图7所示。
它们要满足的约束条件很简单:a+b<N;b+c<N;c+a<N;我们要求满足这些条件的三元组个数。我们设a不大于b同时 b 不大于 c,那它们之间的关系就只剩下 4 种:a=b=c;a=b<c;a<b=c;a<b<c。 它们的系数分别是 1,3,3,6,这是由于它们是在3个角上的组合关系决定的。那么对于这4种情况,我们考察是不是对于边长为N的三角形都可以直接进行求解: 第一种情况:a=b=c,上面那个等式就可以化为一个2*a<N,那么个数就是a<N/2,由于N/2可能是小数,故修改后就是(N-1)/2 个;
第二种情况:a=b<c,等式可以化为 b+c<N 且 c>b,由于 c>b,故可以求两上值的上限。可以转化为b的上限为[(N-2)/2],当然根据b的上限很容易得到c的上限。我们列举出一些情况来进行分析,看看有什么规律: 可以发现:由偶数变奇数的时候(N->N+1),总共增加了[(N-2)/2],由奇数变偶数的时候(N->N+1),总共增加了[(N-1)/2]种。 所以由 N 变为 N+1 种的时候,增加了(N-1)/2 种。 故有递推式 f(x+1)=f(x)+(x-1)/2(x>3)且 f(t)=0,t<4。 用数学归纳法证明之,成立。 第三种情况:a<b=c,等式可化为 b+c<N 且 b>a。 由于这种情况,故对b求上限,转化为第一种,上限为(N-1)/2。同样我们列举出一些情况看看有什么规律: