浅谈用极大化的思想解决最大子矩形问题--王知昆.ppt

算法1 从左向右扫描，第一次遇到2号点，可以得到一个有效的极大子矩形，如图所示 左边界 上边界 下边界 1 2 算法1 因为左边界覆盖1号点且右边界在2号点右边的有效子矩形都不能包含2号点，所以需要修改上下边界 2号点在1号点上方，因此要修改上边界 左边界 上边界 下边界 1 2 算法1 继续扫描到3号点，又得到一个极大有效子矩形，如图所示 左边界 上边界 下边界 1 3 算法1 因为3号点在1号点下方，所以要修改下边界。 左边界 上边界 下边界 1 3 算法1 以此类推，可以得到所有以1号点为左边界的极大有效子矩形。 然后将左边界移动到2号点、3号点……横坐标的位置。开始扫描以2号点、3号点……为左边界的极大子矩形。 左边界 上边界 下边界 2 3 算法1 遗漏的情况 前面的做法可以找出所有左边界覆盖了一个障碍点的极大子矩形，此外，还有两类遗漏的情况。 算法1 遗漏的情况 一类是左边界与整个矩形的左边界重合，右边界覆盖一个障碍点的情况。 解决方法：用类似的方法从右向左扫描一次。 算法1 遗漏的情况 另一类是左边界与整个矩形的左边界重合，且右边界也与整个矩形的右边界重合的情况。 解决方法：预处理时增加特殊判断。 算法1 优劣分析 算法1的时间复杂度为O(S2)，空间复杂度为O(S)。 优点：利用了极大化思想，复杂度可以接受，编程实现简单。 缺点：使用有一定的局限性，不适合障碍点较密集的情况。 算法2 设计的目的和思路 因为算法1有使用的局限性，所以我们需要一种在障碍点很密集的时候仍能奏效的算法。 设计一种复杂度依赖于整个矩形面积的算法 说明：如果整个矩形面积很大，可以通过离散化处理来优化。 算法2 悬线 有效竖线：除了两个端点外，不覆盖任何障碍点的竖直线段。 悬线：上端点覆盖了一个障碍点或达到整个矩形上端的有效竖线。 图中所示的线段均为悬线。 算法2 悬线 每个悬线都与它底部的点一一对应。 矩形中的每一个点（矩形顶部的点除外）都对应了一个悬线。 悬线的个数＝(N－1)×M 算法2 悬线与极大子矩形 如果把一个极大子矩形按x坐标不同切割成多个与y轴平行的线段，则其中至少存在一个悬线。 …… Y X 算法2 悬线与极大子矩形 如果把一个悬线向左右两个方向尽可能移动，就能得到一个矩形，不妨称为这个悬线对应的矩形。 悬线对应的矩形不一定是极大子矩形，因为下边界可能还可以向下扩展。 设计算法 原理：所有悬线对应矩形的集合一定包含了极大子矩形的集合。 通过枚举所有的悬线，找出所有的极大子矩形。 算法规模： 悬线个数＝(N－1)×M 极大子矩形个数≤悬线个数 算法2 关键点 解决问题的关键： 对每个悬线的处理时间。 解决方法： 充分利用前面得到的信息。 算法2 处理方法 具体方法： 设 H[i,j]为点(i,j)对应的悬线的长度。 L[i,j]为点(i,j)对应的悬线向左最多能够移动到的位置。 R[i,j]为点(i,j)对应的悬线向右最多能够移动到的位置。 图示 L[i,j] R[i,j] H[i,j] 点(i,j) 考虑点(i,j)对应的悬线与点(i-1,j)对应的悬线的关系。 算法2 递推关系 如果(i－1,j)为障碍点，那么，如图所示，(i,j)对应的悬线长度1，左右能移动到的位置是整个矩形的左右边界。 即 H[i,j]＝1, L[i,j]=0,R[i,j]=m (i-1,j):障碍点 (i,j):当前点 R[i,j] L[i,j] H[i,j]=1 算法2 递推关系 如果(i－1,j)不是障碍点，那么，如图所示，(i,j)对应的悬线长度为(i-1,j)对应的悬线长度＋1。 即 H[i,j]＝H[i-1,j]+1 (i-1,j):非障碍点 (i,j):当前点 某个障碍 算法2 递推关系 如果(i－1,j)不是障碍点，那么，如图所示，(i,j)对应的悬线左右能移动的位置要在(i-1,j)的基础上变化。 L[i-1,j] L[i,j]=max (i-1,j)左边第一个障碍点的位置 (i,j):当前点 某个障碍 L[i-1,j] L[i,j] (i-1,j) 算法2 递推关系 同理，也可以得到R[i,j]的递推式 R[i-1,j] R[i,j]=min (i-1,j)右边第一个障碍点的位置