《浅谈用极大化思想解决最大子矩形问题》由会员分享，可在线阅读，更多相关《浅谈用极大化思想解决最大子矩形问题（45页珍藏版）》请在金锄头文库上搜索。
1、浅谈用极大化思想解决最大子矩形问题浅谈用极大化思想解决最大子矩形问题浅谈用极大化思想解决最大子矩形问题浅谈用极大化思想解决最大子矩形问题福州第三中学福州第三中学福州第三中学 王知昆王知昆王知昆题意简述题意简述题意简述题意简述： John John要在牛场中建造一个大型浴场，但要在牛场中建造一个大型浴场，但是这个大型浴场不能覆盖任何一个奶牛的产是这个大型浴场不能覆盖任何一个奶牛的产奶点。奶点。JohnJohn的牛场和规划的浴场都是矩形，的牛场和规划的浴场都是矩形，浴场要完全位于牛场之内，并且浴场的轮廓浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。要求所求浴要与牛场的轮廓平行或
2、者重合。要求所求浴场的面积尽可能大。场的面积尽可能大。参数约定：产奶点的个数参数约定：产奶点的个数S S不超过不超过5000,5000,牛场牛场的范围的范围NMNM不超过不超过30000300003000030000。问题：奶牛浴场问题：奶牛浴场最大子矩形问题： 在一个给定的矩形中有一些障碍点，要找出内部不包含任何障碍点的，轮廓与整个矩形平行或重合的最大子矩形。问题的模型问题的模型定义和说明定义和说明定义有效子矩形有效子矩形为内部不包含任何障碍点的，边界与坐标轴平行的子矩形。 如下图所示，第一个是有效子矩形，第二个不是。定义和说明定义和说明定义极大子矩形极大子矩形为每条边都不能向外扩展的有效子
3、矩形。定义最大子矩形最大子矩形为所有有效子矩形中最大的一个（或多个）。极大化思想极大化思想在一个有障碍点的矩形中的最大子矩形一定是一个极大子矩形。 设计算法的思路：通过枚举所有的极大子矩形，找出最大子矩形。两个不同的算法两个不同的算法针对问题的性质，可以设计出两个不同的算法。针对问题的性质，可以设计出两个不同的算法。他们分别适用于不同的情况。他们分别适用于不同的情况。约定：约定：约定：约定：为了叙述方便，设整个矩形的大小为为了叙述方便，设整个矩形的大小为NMNM，其中障碍点个数为，其中障碍点个数为S S。算法算法1 1时间复杂度：时间复杂度：O(SO(S2 2) )空间复杂度：空间复杂度：O(
4、S)O(S)算法算法2 2时间复杂度：时间复杂度：O(NM)O(NM)空间复杂度：空间复杂度：O(S)O(S)算法算法1 思路思路从极大子矩形的性质入手。从极大子矩形的性质入手。极大子矩形的性质：极大子矩形的性质： 一个极大子矩形的每条边一定都不能向外扩展。更进一步地说，一个有效子矩形是极大子矩形的条件是这个子矩形的每条边要么覆盖了障碍点，要么与整个矩形的边界重合。一个极大子矩形的每条边一定都不能向外扩展。更进一步地说，一个有效子矩形是极大子矩形的条件是这个子矩形的每条边要么覆盖了障碍点，要么与整个矩形的边界重合。算法设计算法设计 基本算法基本算法算法：枚举上下左算法：枚举上下左右四个边界，然
5、后右四个边界，然后判断组成的矩形是判断组成的矩形是否是有效子矩形。否是有效子矩形。复杂度：复杂度：O(SO(S5 5) )可以改进的地方：可以改进的地方： 产生了大量的无效产生了大量的无效子矩形子矩形 初步改进算法初步改进算法算法：枚举左右边界，算法：枚举左右边界，然后对处在边界内的然后对处在边界内的点排序。每两个相邻点排序。每两个相邻的点和左右边界一起的点和左右边界一起组成一个矩形。组成一个矩形。复杂度：复杂度：O(SO(S3 3) )可以改进的地方：可以改进的地方： 枚举了部分不是极大枚举了部分不是极大子矩形的情况子矩形的情况算法改进算法改进设计算法的方向：设计算法的方向： 1 1、保证每
6、一个枚举的子矩形都是有效的、保证每一个枚举的子矩形都是有效的 2 2、保证每一个枚举的子矩形都是极大的、保证每一个枚举的子矩形都是极大的 算法的过程：算法的过程： 枚举极大子矩形的左边界枚举极大子矩形的左边界 根据确定的左边界，找出相关的极根据确定的左边界，找出相关的极 大子矩形大子矩形 检查和处理遗漏的情况检查和处理遗漏的情况算法算法1 1首先，将所有障碍点按横坐标从小到大的顺序将点标为1号点，2号点1234算法算法1 1为了处理方便，在矩形的四个顶点上各增加1个障碍点。算法算法1 1第一次取1号点作为所要枚举的极大子矩形的左边界设定上下边界为矩形的上下边界 左边界上边界下边界1算法算法1
7、1从左向右扫描，第一次遇到2号点，可以得到一个有效的极大子矩形，如图所示 左边界上边界下边界12算法算法1 1因为左边界覆盖因为左边界覆盖1 1号点且右边界在号点且右边界在2 2号点右边号点右边的有效子矩形都不能包含的有效子矩形都不能包含2 2号点，所以需要号点，所以需要修改上下边界修改上下边界2 2号点在号点在1 1号点上方，因此要修改上边界号点上方，因此要修改上边界 左边界上边界下边界12算法算法1 1继续扫描到3号点，又得到一个极大有效子矩形，如图所示 左边界上边界下边界13算法算法1 1因为3号点在1号点下方，所以要修改下边界。 左边界上边界下边界13算法算法1 1以此类推，可以得到所
8、有以以此类推，可以得到所有以1 1号点为左边界号点为左边界的极大有效子矩形。的极大有效子矩形。然后将左边界移动到然后将左边界移动到2 2号点、号点、3 3号点号点横坐横坐标的位置。开始扫描以标的位置。开始扫描以2 2号点、号点、3 3号点号点为为左边界的极大子矩形。左边界的极大子矩形。 左边界上边界下边界23算法算法1 1 遗漏的情况遗漏的情况前面的做法可以找出所有左边界覆盖了一个障碍点的极大子矩形，此外，还有两类遗漏的情况。算法算法1 1 遗漏的情况遗漏的情况一类是左边界与整个矩形的左边界重合，右一类是左边界与整个矩形的左边界重合，右边界覆盖一个障碍点的情况。边界覆盖一个障碍点的情况。解决方
9、法：用类似的方法从右向左扫描一次。解决方法：用类似的方法从右向左扫描一次。算法算法1 1 遗漏的情况遗漏的情况另一类是左边界与整个矩形的左边界重合，另一类是左边界与整个矩形的左边界重合，且右边界也与整个矩形的右边界重合的情况。且右边界也与整个矩形的右边界重合的情况。解决方法：预处理时增加特殊判断。解决方法：预处理时增加特殊判断。算法算法1 1 优劣分析优劣分析 算法1的时间复杂度为O(S2)，空间复杂度为O(S)。优点：利用了极大化思想，复杂度可以接受，编程实现简单。缺点：使用有一定的局限性，不适合障碍点较密集的情况。算法算法2 2 设计的目的和思路设计的目的和思路因为算法1有使用的局限性，所
10、以我们需要一种在障碍点很密集的时候仍能奏效的算法。设计一种复杂度依赖于整个矩形面积的算法 说明：如果整个矩形面积很大，可以通过离散化处理来优化。算法算法2 2 悬线悬线有效竖线：除了两个端点外，不覆盖任何障有效竖线：除了两个端点外，不覆盖任何障碍点的竖直线段。碍点的竖直线段。悬线：上端点覆盖了一个障碍点或达到整个悬线：上端点覆盖了一个障碍点或达到整个矩形上端的有效竖线。矩形上端的有效竖线。图中所示的线段均为悬线。图中所示的线段均为悬线。算法算法2 2 悬线悬线每个悬线都与它底部的点一一对应。 矩形中的每一个点（矩形顶部的点除外）都对应了一个悬线。悬线的个数(N1)M算法算法2 2 悬线与极大子
11、矩形悬线与极大子矩形如果把一个极大子矩形按x坐标不同切割成多个与y轴平行的线段，则其中至少存在一个悬线。YX算法算法2 2 悬线与极大子矩形悬线与极大子矩形如果把一个悬线向左右两个方向尽可能移动，如果把一个悬线向左右两个方向尽可能移动，就能得到一个矩形，不妨称为这个悬线对应就能得到一个矩形，不妨称为这个悬线对应的矩形。的矩形。悬线对应的矩形不一定是极大子矩形，因为悬线对应的矩形不一定是极大子矩形，因为下边界可能还可以向下扩展。下边界可能还可以向下扩展。设计算法设计算法原理：所有悬线对应矩形的集合一定包含了极大子矩形的集合。通过枚举所有的悬线，找出所有的极大子矩形。算法规模： 悬线个数(N1)M
12、 极大子矩形个数悬线个数算法算法2 2 关键点关键点解决问题的关键： 对每个悬线的处理时间。解决方法： 充分利用前面得到的信息。算法算法2 2 处理方法处理方法具体方法：具体方法： 设设 Hi,j Hi,j为点为点(i,j)(i,j)对应的悬线的长度。对应的悬线的长度。 Li,j Li,j为点为点(i,j)(i,j)对应的悬线向左最多能对应的悬线向左最多能够移动到的够移动到的位置位置位置位置。 Ri,j Ri,j为点为点(i,j)(i,j)对应的悬线向右最多能对应的悬线向右最多能够移动到的够移动到的位置位置位置位置。图示图示Li,jRi,jHi,j点(i,j)考虑点(i,j)对应的悬线与点(i
13、-1,j)对应的悬线的关系。算法算法2 2 递推关系递推关系如果如果(i (i1,j)1,j)为障碍点，那么，如图所示，为障碍点，那么，如图所示，(i,j)(i,j)对应的悬线长度对应的悬线长度1 1，左右能移动到的位，左右能移动到的位置是整个矩形的左右边界。置是整个矩形的左右边界。即即 Hi,j Hi,j1,1, Li,j=0,Ri,j=m Li,j=0,Ri,j=m(i-1,j):障碍点(i,j):当前点Ri,jLi,jHi,j=1算法算法2 2 递推关系递推关系如果(i1,j)不是障碍点，那么，如图所示，(i,j)对应的悬线长度为(i-1,j)对应的悬线长度1。即 Hi,jHi-1,j+
14、1(i-1,j):非障碍点(i,j):当前点某个障碍算法算法2 2 递推关系递推关系 如果如果(i (i1,j)1,j)不是障碍点，那么，如图所示，不是障碍点，那么，如图所示，(i,j)(i,j)对应的悬对应的悬线左右能移动的位置要在线左右能移动的位置要在(i-1,j)(i-1,j)的基础上变化。的基础上变化。 Li-1,j Li-1,jLi,j=maxLi,j=max (i-1,j) (i-1,j)左边第一个障碍点的位置左边第一个障碍点的位置 (i,j):当前点某个障碍Li-1,jLi,j(i-1,j)算法算法2 2 递推关系递推关系同理，也可以得到同理，也可以得到Ri,jRi,j的递推式的
15、递推式 Ri-1,j Ri-1,j Ri,j=min Ri,j=min (i-1,j) (i-1,j)右边第一个障碍点的位置右边第一个障碍点的位置 Li,jRi,jHi,j点(i,j)算法算法2 2 优劣分析优劣分析 算法2的时间复杂度为O(NM)，空间复杂度为O(S)。优点： 复杂度与障碍点个数没有直接关系。缺点：障碍点少时处理较复杂，不如算法1两个不同的算法两个不同的算法算法算法1 1时间复杂度：时间复杂度：O(SO(S2 2) )空间复杂度：空间复杂度：O(S)O(S)优点：复杂度可以接受，优点：复杂度可以接受，编程实现简单编程实现简单缺点：使用有一定的局缺点：使用有一定的局限性，不适合
16、障碍点较限性，不适合障碍点较密集的情况。密集的情况。算法算法2 2时间复杂度：时间复杂度：O(NM)O(NM)空间复杂度：空间复杂度：O(S) O(S) 优点：复杂度与障碍点优点：复杂度与障碍点个数没有直接关系。个数没有直接关系。缺点：障碍点少时因为缺点：障碍点少时因为要离散化处理，实际复要离散化处理，实际复杂度较高。杂度较高。推广推广1 1 最大权值子矩形问题最大权值子矩形问题最大权值子矩形问题模型：在一个带权（正权）矩形中有一些障碍点，找出一个不包含障碍点的最大权值子矩形。分析：在一个正权值的矩形中的最大权值子分析：在一个正权值的矩形中的最大权值子矩形一定是极大子矩形。所以，问题实际上矩形
17、一定是极大子矩形。所以，问题实际上可以依据极大化的思想，利用前面的方法解可以依据极大化的思想，利用前面的方法解决。决。推广推广2 2 最大子正方形问题最大子正方形问题最大子正方形问题模型：在一个矩形中存在S个障碍点，要求找出最大的不包含障碍点的正方形。分析：分析：在一个有障碍点的矩形中的最大有效在一个有障碍点的矩形中的最大有效子正方形一定是一个极大有效子正方形。子正方形一定是一个极大有效子正方形。推广推广2 2 最大子正方形问题最大子正方形问题极大子正方形的性质： 每一个极大子正方形都至少被一个极大子矩形包含，且这个极大子正方形一定有两条不相邻的边与包含它的极大子矩形的边重合。 推广推广2 2
18、 最大子正方形问题最大子正方形问题解决方法:通过枚举每一个极大子矩形找出所有的极大子正方形。每个极大子矩形对应的极大子正方形可能有多个，但大小都一样。推广推广2 2 最大子正方形问题最大子正方形问题解决方法:通过枚举每一个极大子矩形找出所有的极大子正方形。每个极大子矩形对应的极大子正方形可能有多个，但大小都一样。推广推广2 2 最大子正方形问题最大子正方形问题解决方法:通过枚举每一个极大子矩形找出所有的极大子正方形。每个极大子矩形对应的极大子正方形可能有多个，但大小都一样。矩形类型变换矩形类型变换类型类型1 1矩形中的点都是两条垂矩形中的点都是两条垂直线段的交点，有效子直线段的交点，有效子矩形可以在边界包含障矩形可以在边界包含障碍点。碍点。类型类型2 2矩形中的点是单位方格，矩形中的点是单位方格，有效子矩形不能包含任有效子矩形不能包含任何障碍点。何障碍点。处理方法与类型处理方法与类型1 1基本相基本相同同要点回顾要点回顾极大化思想最大子矩形问题算法2算法1最大子正方形问题最大权值子矩形问题
