算法合集之《浅谈用极大化思想解决最大子矩形问题》.ppt

《算法合集之《浅谈用极大化思想解决最大子矩形问题》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅谈用极大化思想解决最大子矩形问题福州第三中学王知昆题意简述：John要在牛场中建造一个大型浴场，但是这个大型浴场不能覆盖任何一个奶牛的产奶点。John的牛场和规划的浴场都是矩形，浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。要求所求浴场的面积尽可能大。参数约定：产奶点的个数S不超过5000,牛场的范围N×M不超过30000×30000。问题：奶牛浴场最大子矩形问题：在一个给定的矩形中有一些障碍点，要找出内部不包含任何障碍点的，轮廓与整个矩形平行或重合的最大子矩形。问题的模型定义和说明定义有效

2、子矩形为内部不包含任何障碍点的，边界与坐标轴平行的子矩形。如下图所示，第一个是有效子矩形，第二个不是。定义和说明定义极大子矩形为每条边都不能向外扩展的有效子矩形。定义最大子矩形为所有有效子矩形中最大的一个（或多个）。极大化思想在一个有障碍点的矩形中的最大子矩形一定是一个极大子矩形。设计算法的思路：通过枚举所有的极大子矩形，找出最大子矩形。两个不同的算法针对问题的性质，可以设计出两个不同的算法。他们分别适用于不同的情况。约定：为了叙述方便，设整个矩形的大小为N×M，其中障碍点个数为S。算法1时间复杂度：O(S2)空

3、间复杂度：O(S)算法2时间复杂度：O(NM)空间复杂度：O(S)算法1思路从极大子矩形的性质入手。极大子矩形的性质：一个极大子矩形的每条边一定都不能向外扩展。更进一步地说，一个有效子矩形是极大子矩形的条件是这个子矩形的每条边要么覆盖了障碍点，要么与整个矩形的边界重合。算法设计基本算法算法：枚举上下左右四个边界，然后判断组成的矩形是否是有效子矩形。复杂度：O(S5)可以改进的地方：产生了大量的无效子矩形初步改进算法算法：枚举左右边界，然后对处在边界内的点排序。每两个相邻的点和左右边界一起组成一个矩形。复杂度：O(

4、S3)可以改进的地方：枚举了部分不是极大子矩形的情况算法改进设计算法的方向：1、保证每一个枚举的子矩形都是有效的2、保证每一个枚举的子矩形都是极大的算法的过程：枚举极大子矩形的左边界→根据确定的左边界，找出相关的极大子矩形→检查和处理遗漏的情况算法1首先，将所有障碍点按横坐标从小到大的顺序将点标为1号点，2号点……1234算法1为了处理方便，在矩形的四个顶点上各增加1个障碍点。算法1第一次取1号点作为所要枚举的极大子矩形的左边界设定上下边界为矩形的上下边界左边界上边界下边界1算法1从左向右扫描，第一次遇到2号点，

5、可以得到一个有效的极大子矩形，如图所示左边界上边界下边界12算法1因为左边界覆盖1号点且右边界在2号点右边的有效子矩形都不能包含2号点，所以需要修改上下边界2号点在1号点上方，因此要修改上边界左边界上边界下边界12算法1继续扫描到3号点，又得到一个极大有效子矩形，如图所示左边界上边界下边界13算法1因为3号点在1号点下方，所以要修改下边界。左边界上边界下边界13算法1以此类推，可以得到所有以1号点为左边界的极大有效子矩形。然后将左边界移动到2号点、3号点……横坐标的位置。开始扫描以2号点、3号点……为左边界的极大

6、子矩形。左边界上边界下边界23算法1遗漏的情况前面的做法可以找出所有左边界覆盖了一个障碍点的极大子矩形，此外，还有两类遗漏的情况。算法1遗漏的情况一类是左边界与整个矩形的左边界重合，右边界覆盖一个障碍点的情况。解决方法：用类似的方法从右向左扫描一次。算法1遗漏的情况另一类是左边界与整个矩形的左边界重合，且右边界也与整个矩形的右边界重合的情况。解决方法：预处理时增加特殊判断。算法1优劣分析算法1的时间复杂度为O(S2)，空间复杂度为O(S)。优点：利用了极大化思想，复杂度可以接受，编程实现简单。缺点：使用有一定的局

7、限性，不适合障碍点较密集的情况。算法2设计的目的和思路因为算法1有使用的局限性，所以我们需要一种在障碍点很密集的时候仍能奏效的算法。设计一种复杂度依赖于整个矩形面积的算法说明：如果整个矩形面积很大，可以通过离散化处理来优化。算法2悬线有效竖线：除了两个端点外，不覆盖任何障碍点的竖直线段。悬线：上端点覆盖了一个障碍点或达到整个矩形上端的有效竖线。图中所示的线段均为悬线。算法2悬线每个悬线都与它底部的点一一对应。矩形中的每一个点（矩形顶部的点除外）都对应了一个悬线。悬线的个数＝(N－1)×M算法2悬线与极大子矩形如果

8、把一个极大子矩形按x坐标不同切割成多个与y轴平行的线段，则其中至少存在一个悬线。……YX算法2悬线与极大子矩形如果把一个悬线向左右两个方向尽可能移动，就能得到一个矩形，不妨称为这个悬线对应的矩形。悬线对应的矩形不一定是极大子矩形，因为下边界可能还可以向下扩展。设计算法原理：所有悬线对应矩形的集合一定包含了极大子矩形的集合。通过枚举所有的悬线，找出所有的极大子矩形。算法规模