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

浅谈以极大化思想解决最大子矩形问题，福州第三中学王知昆问题：奶牛浴场，题意简单：约翰在牛场建设大型浴场，这个大型浴场不能独占奶牛的奶牛场。 约翰的牛场和计划的浴场都是矩形的，浴场完全在牛场里，浴场的轮廓必须和牛场的轮廓平行或一致。 所要求的浴场面积要尽量大。 参数约定：产奶点的个数s在5000以下，牛场的范围NM在3000030000以下。 问题模型，最大子矩形问题：找到一个矩形有故障点，内部没有故障点，轮廓与整个矩形平行或重叠的最大子矩形。 定义和说明，定义有效的子矩形是内部没有故障点，边界平行于坐标轴的子矩形。 如下图所示，第一个是有效的子矩形，第二个不是。，定义和说明，定义极大子矩形是各边不能向外侧扩展的有效子矩形。 将最大子矩形定义为一个或多个有效子矩形。 思想最大化，故障点矩形中的最大子矩形必定是最大子矩形。 设计算法思路：通过列举所有极大子矩形，找出最大子矩形。 另外，对于两种不同的算法、问题的性质，可以设计两种不同的算法。 他们分别适合不同的情况。 约定：为了便于说明，将矩形整体的大小设为NM，其中故障点的数量设为s。 算法1小时复杂度： O(S2)空间复杂度： O(S )，算法2小时复杂度： O(NM )空间复杂度： O(S )，算法1构想，从极大子矩形的性质开始。 极大子矩形的性质：一个极大子矩形的各边必定不能向外侧扩展。 另外，有效的子矩形是最大的子矩形这一条件是子矩形的每个边缘复盖故障点还是叠加在整个矩形的边界上。 列举、算法设计、基本算法：上下左右边界，判断构成的矩形是否是有效的子矩形。 复杂度： O(S5)可改进的点：生成大量无效子矩形，算法初步改进：枚举左右边界并对边界内的点进行排序。 相邻的两个点和左右边界构成一个矩形。 复杂度： O(S3)可改进的点：如果枚举部分不是最大子矩形，则改进算法，设计算法的方向： 1，确保每个枚举的子矩形有效的2，确保每个枚举的子矩形是最大算法的过程：基于枚举的最大子矩形的左边界确定的左边界， 对于查找相关性最大子矩形检验和处理遗漏的情况，算法1，首先将所有故障点按横轴从小到大的顺序分别添加到第一点、第二点、1、2、3、4、算法1，为了处理方便，将故障点分别添加到矩形的4个顶点。 如果，算法1，作为最初列举第1个点的极大子矩形的左边界，将上下边界设定为矩形的上下边界，则在，左边界，上边界，下边界，1，算法1，从左向右扫描首次遇到第2个点时，有效如图所示，左边界，上边界，下边界，1，2算法1修改上边界，因为左边界复盖了第一点，并且右边界在第二点的右侧的有效子矩形不能包括第二点算法1继续扫描到第三点，得到非常有效的子矩形，左边界，上边界，下边界，1，3，算法1等以第一点为左边界的极有效子矩形然后将左边界移动到2号点，3号点横轴的位置。 开始扫描时，以2号点、3号点为左边界的极大子矩形。如果，左边界，上边界，下边界，2，3，算法1缺失的情况下，用前面的方法除了可以发现所有左边界复盖一个障碍点的极大子矩形以外，也有2种缺失。 如果，算法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的处理方法，具体方法： Hi，j为与点(I，j )对应的悬挂的长度。 Li，j是与点(I，j )对应吊线能够向左最大移动的位置。 Ri，j是与点(I，j )对应的悬架能够向右移动最多的位置。 另外，考虑与图示、Li，j、Ri，j、Hi，j、点(I，j )、点(I，j )对应的悬架和与点(i-1，j )对应的悬架的关系。 此外，算法2的递归关系是：如图所示，如果(i-1，j )是故障点，则能够向左右移动与(I，j )对应的悬挂长度1，位置是矩形整体的左右边界。 即，对应于(I，j )，Hi，j=1，Li，j=0，Ri，j=m，(i-1，j):故障点，Ri，j，Li，j，Hi，j=1，如果算法2不是故障点，则如图所示，对应于(I，j ) 即，Hi，j=Hi-1，j 1，(i-1，j):非故障点，(I，j):当前点，某故障点，算法2递归关系，如果(i-1，j )不是故障点，则如图所示，与(I，j )对应的悬架的能够左右移动的位置为(i-1，j ) Li-1，jLi，j=max(i-1，j )左侧的第一个故障点的位置，(I，j):当前点，Li-1，j，算法2的递归关系，以及类似地，Ri，j的递归方程式Ri-1，jRi，j=min(i-1，j )右侧的第一个故障点的位置、Li，j、Ri，j、Hi，j、点(I，j )、算法2的优劣分析、算法2的时间复杂度为O(NM )、空间复杂度为O(S )。 优点：复杂性与故障点的数量没有直接关系。缺点：故障点少时处理复杂，算法1，两种不同的算法相比，算法1小时的复杂性： O(S2)空间的复杂性： O(S )的优点：复杂性容许，编程简单的缺点：有一定的局限性，不适合故障点密集的情况。 算法2小时复杂度： O(NM )空间复杂度： O(S )优点：复杂度与故障点的数量没有直接关系。 缺点：故障点较少时，需要离散化处理，因此实际复杂度较高。 推进1最大权值子矩形问题，最大权值子矩形问题模型：一个带权(正权)矩形中有一些故障点，找到不包含故障点的最大权值子矩形。 分析：正权重矩形中权重最大的子矩形必定是极大子矩形。 因此，问题实际上可以基于极大的思想，用以前的方法解决。 推进2最大子正方形问题，最大子正方形问题模型：一个矩形中存在s个故障点，要求找到不包含故障点的最大正方形。 分析：故障点矩形中的最大有效子正方形必须是极大有效子正方形。 推进2最大子正方形问题，极大子正方形的性质：每个极大子正方形包含在至少一个极大子矩形中，该极大子正方形必须与两个不相邻的边和包含它的极大子矩形的边一致。 通过列举、推进2最大子正方形问题、解决方法：各极大子矩形，找出所有的极大子正方形。 对应于每一极大子矩形的极大子正方形可以有多个，但其尺寸相同。 推进2通过列举最大子正方形问题、解决方法：各极大子矩形，找到所有的极大子正方形。 对应于每一极大子矩形的极大子正方形可以有多个，但其尺寸相同。 通过列举、推