浅谈用极大化思想解决最大子矩形问题,浅谈用极大化思想解决最大子矩阵问题

一、   问题

最大子矩形问题:在一个加以的矩形网格中有一些障碍点,要找出网格内部不带有其余障碍点,且边界与坐标轴平行的最大子矩形。

 

那是近日平时现身的题材,例如冬令营2002的《奶牛浴场》,就属于最大子矩形问题。

 

Winter 坎普(Camp)2002,奶牛浴场

题意简述:(原题见杂文附件)

John要在矩形牛场中建造一个巨型浴场,但是这几个特大型浴场不可能包涵其余一个奶牛的产奶点,但产奶点可以出在浴池的边界上。约翰(John)的牛场和筹划的浴室都是矩形,浴场要完全位于牛场之内,并且浴场的概貌要与牛场的大致平行或者重合。要求所求浴场的面积尽可能大。

参数约定:产奶点的个数S不超过5000,牛场的限制N×M不领先30000×30000。

 

【摘要】

二、   定义和验证

第一明确一些概念。

 

1、定义有效子矩形为内部不分包其余障碍点且边界与坐标轴平行的子矩形。如图所示,首个是有效子矩形(固然边界上有障碍点),第三个不是有效子矩形(因为中间含有障碍点)。

lovebet体育官网 1

 

2、粗大有效子矩形:一个有效子矩形,如若不存在包含它且比它大的有效子矩形,就称那个有效子矩形为巨大有效子矩形。(为了叙述方便,以下称为极大子矩形

 

3、定义最大有效子矩形为所有有效子矩形中最大的一个(或三个)。以下简称为最大子矩形。

  

本文针对一类近期经常出现的有关最大(或最优)子矩形及相关变形问题,介绍了极大化思想在这类问题中的应用。分析了两个具有一定通用性的算法。并通过一些例题讲述了这些算法选择和使用时的一些技巧。

三、   极大化思想

【定理1】在一个有障碍点的矩形中的最大子矩形一定是一个极大子矩形。

申明:若是最大子矩形A不是一个极大子矩形,那么按照极大子矩形的概念,存在一个涵盖A且比A更大的有效子矩形,那与“A是最大子矩形”顶牛,所以【定理1】创设。

 

lovebet体育官网 2

【关键字】 矩形,障碍点,极大子矩形

四、   从问题的表征出手,获得二种常用的算法

定理1固然很分明,但却是很要紧的。依据定理1,我们得以获取如此一个解题思路:

通过枚举所有的极大子矩形,就足以找到最大子矩形。上面遵照那一个思路来统筹算法。

约定:为了叙述方便,设任何矩形的大小为n×m,其中障碍点个数为s。

【正文】
一、 问题

算法1

算法的笔触是透过枚举所有的极大子矩形找出最大子矩形。根据这么些思路可以发现,如果算法中有五遍枚举的子矩形不是有效子矩形、或者不是极大子矩形,那么可以肯定这些算法做了“无用功”,那也就是内需优化的地点。怎么着保障每一回枚举的都是极大子矩形呢,我们先从极大子矩形的特性入手。

lovebet体育官网 3

定理2】:一个极大子矩形的四条边一定都不可能向外伸张。更进一步地说,一个有效子矩形是极大子矩形的充要条件是其一子矩形的每条边要么覆盖了一个障碍点,要么与任何矩形的境界重合。 

 

定理2的正确很明确,假设一个有效子矩形的某一条边既没有覆盖一个障碍点,又没有与任何矩形的疆界重合

,那么一定存在一个分包它的有效子矩形。依据定理2,大家可以收获一个枚举极大子矩形的算法。为了处理方便,首先在障碍点的汇聚中添加整个矩形四角上的点。每趟枚举子矩形的内外左右境界(枚举覆盖的障碍点),然后判断是还是不是合法(内部是不是有隐含障碍点)。那样的算法时间复杂度为O(S5),显著太高了。考虑到极大子矩形不可能包涵障碍点,因而那样枚举4个边界显著会时有暴发多量的无效子矩形。

设想只枚举左左边界的境况。对于早已确定的左右境界,可以将兼具处在这些界限内的点按从上到下排序,如图1中所示,每一格就代表一个有效子矩形。那样做时间复杂度为O(S3)。由于保障每一次得到的矩形都是官方的,所以枚举量比前一种算法小了不以为奇。但须要专注的是,那样做枚举的子矩形尽管是合法的,然则不自然是特大

lovebet体育官网 4

的。所以那几个算法还有优化的余地。通过对那个算法不足之处的优化,大家得以得到一个疾速的算法。

追忆下面的算法,我们简单发现,所枚举的矩形的上上边界都掩盖了障碍点或者与成套矩形的边界重合,问题就在于左左边界上。只有那个左右侧际也覆盖了障碍点或者与一切矩形的分界重合的有效子矩形才是大家需求考察的极大子矩形,所在此往日边的算法做了无数“无用功”。怎么减弱“无用功”呢,那里介绍一种算法(算法1),它可以用在不可胜计此类问题上。

算法的思绪是那般的,先枚举极大子矩形的右边界,然后从左到右依次扫描每一个障碍点,并频频修改可行的内外边界,从而枚举出所有以这么些原则性为左侧界的极大子矩形。考虑如图2中的四个点,现在大家要规定所有以1号点为右侧界的石破天惊矩形。先将1号点左侧的点按横坐标排序。然后按从左到右的相继依次扫描1号点右侧的点,同时记录下当前的实用的左左边界。

发端时令当前的左右侧界分别为任何矩形的光景边界。然后先导扫描。第一遍遇上2号点,以2号点作为左侧界,结合当下的内外边界,就获得一个极大子矩形(如图3)。同时,由于所求矩形不可能包涵2号点,且2号点在1号点的人间,所以需求修改当前的上面界,即以2号点的纵坐标作为新的上面界。第二次相遇3号点,那时以3号点的横坐标作为左边界又有什么不可拿走一个满意性质1的矩形(如图4)。类似的,须求相应地修改上面界。以此类推,假如这些点是在当前点(确定右边界的点)上方,则修改上面界;若是在下方,则修改上边际;假诺处lovebet体育官网 5在同一行,则可暂停搜索(因为背后的矩形面积都是0了)。由于已经在障碍点集合中增

如此那般做是或不是将富有的极大子矩形都枚举过了吧?可以发现,那样做只考虑到了左侧界覆盖一个点的矩形,因而大家还须要枚举右边界与一切矩形的左边界重合的情形。那还足以分成两类景况。一种是左边界与整个进行的左侧界重合,而左侧界覆盖了一个障碍点的情景,对于那种情景,可以用接近的法子从右到左扫描每一个点作为右侧界的场所。另一种是反正境界均与一切矩形的左左边界重合的气象,对于那类景况我们可以在预处理中成功:先将所有点按纵坐标排序,然后可以得到以相邻三个点的纵坐标为上上面界,左右侧界与任何矩形的左左边际重合的矩形,明显那样的矩形也是极大子矩形,由此也亟需被枚举到。加了整个矩形右上角和右下角的五个点,所以不会遗漏左边界与成套矩形的左边重合的极大子矩形(如图5)。必要注意的是,如若扫描到的点不在当前的光景边界内,那么就不必要对那么些点进

行处理。

由在此以前面两步,可以枚举出所有的极大子矩形。算法1的岁月复杂度是O(S2)。那样,可以解决一大半最大子矩形和血脉相通题材了。

lovebet体育官网 6

 

虽说上述的算法(算法1)看起来是相比较火速的,但也有采用的局限性。可以窥见,那些算法的复杂度只与障碍点的个数s有关。但对此某些问题,s最大有可能落成n×m,当s较大时,这一个算法就不至于能满意时间上的渴求了。能不能设计出一种依赖于n和m的算法呢?那样在算法1不可以卓有效率的时候我们还有其余采取。大家再重新从最中央的题材初始研商。

 

 

最大子矩形问题:在一个加以的矩形网格中有一对障碍点,要找出网格内部不包蕴其余障碍点,且边界与坐标轴平行的最大子矩形。

算法2

     
首先,根据定理1:最大有效子矩形一定是一个极大子矩形。不过与前一种算法分化的是,大家不再须要每一次枚举的早晚是极大子矩形而只要求具备的极大子矩形都被枚举到。看起来那种算法可能比前一种差,其实不然,因为前一种算法并不是圆满的:尽管每一趟考察的都是极大子矩形,但它依然做了零星的“无用功”。可以窥见,当障碍点很密集的时候,前一种算法会做多量没用的对比工作。要解决这么些题材,大家务必跳出前边的思绪,重新考虑一个新的算法。注意到极大子矩形的个数不会当先矩形内单位方格的个数,因而大家有可能找出一种时光复杂度是O(N×M)的算法。

 

 定义:

有效竖线:除了八个端点外,不掩盖任何障碍点的竖直线段。

lovebet体育官网 7

悬线:上端点覆盖了一个障碍点或达到任何矩形上端的有效竖线。如图所示的三个有效竖线都是悬线。

 

     
对于其他一个极大子矩形,它的下边界上或者有一个障碍点,要么和全路矩形的上面界重合。那么一旦把一个极大子矩形按x坐标分歧切割成多个(实际上是不少个)与y轴垂直的线条,则其中自然存在一条悬线。而且一条悬线通过尽可能地向左右平移恰好能取得一个子矩形(未必是极大子矩形,但只可能向下扩充)。通过上述的辨析,大家能够获得一个要害的定律。

 

定理3】:尽管将一个悬线向左右多个趋势尽可能活动所取得的有效子矩形称为那个悬线所对应的子矩形,那么具有悬线所对应的有效子矩形的汇集一定带有了具有极大子矩形的会聚。

 

定理3中的“尽可能”移动指的是移动到一个障碍点或者矩形边界的职责。

按照【定理3】可以发现,通过枚举所有的悬线,就能够枚举出所有的极大子矩形。由于每个悬线都与它底部的可怜点一一对应,所以悬线的个数=(n-1)×m(以矩形中除去顶部的点以外的种种点为底部,都足以博得一个悬线,且并未遗漏)。即使能成功对各样悬线的操作时间都为O(1),那么所有算法的复杂度就是O(NM)。这样,大家见到了然决问题的期望。

     
现在的题目是,如何在O(1)的岁月内成功对每个悬线的操作。大家明白,每个极大子矩形都得以通过一个悬线左右运动获得。所以,对于每个确定了底部的悬线,大家要求了解有关于它的多少个量:顶部、左右最多能移动到的职位。对于尾部为(i,j)的悬线,设它的高为hight[i,j],左右最多能移动到的地点为left[i,j],right[i,j]。为了丰富利用在此之前得到的音信,大家将那三个函数用递推的款型提交。

 

  对于以点(i,j)为底部的悬线:

倘若点(i-1,j)为障碍点,那么,显明以(i,j)为底的悬线中度为1,而且左右均可以移动到全方位矩形的左左侧界,即

 

 height[i,j]=l

left[i,j]=0

right[i,j]=m

即使点(i-1,j)不是障碍点,那么,以(i,j)为底的悬线就等于以(i-1,j)为底的悬线+点(i,j)到点(i-1,j)的线条。因而,height[i,j]=height[i-1,j]+1。比较费心的是左右境界,先考虑left[i,j]。如下图所示,(i,j)对应的悬线左右能活动的职分要在(i-1,j)的根基上转移。

即left[i,j]=max( left[i-1,j] , (i-1,j)左侧第四个障碍点位置 ) 如图

   lovebet体育官网 8

 right[i,j]的求法类似。综合起来,可以得到这四个参数的递推式:

 

height[i,j]=height[i-1,j]+1

left[i,j]=max( left[i-1,j] ,
(i-1,j)左侧第三个障碍点地方,边界0也是阻碍点 )

right[i,j]=min( right[i-1,j] ,
(i-1,j)左侧第三个障碍点地点,边界m也是障碍点 )

  
那样做充裕利用了之前获得的音讯,使每个悬线的处理时间复杂度为O(1)。对于以点(i,j)为底的悬线对应的子矩形,它的面积为(right[i,j]-left[i,j])*height[i,j]。

这么结尾问题的解就是:

Result=max(right[i,j]-left[i,j])*height[i,j] (l<=i<n,
l<=j<=m)

任何算法的时光复杂度为O(NM),空间复杂度是O(NM)。

 

  多少个算法的比较:

上述说了两种具有一定通用性的处理算法,时间复杂度分别为O(S2)和O(NM)。二种算法分别适用于差其余情形。从时间复杂度上来看,第一种算法对于障碍点稀疏的情事相比较实惠,第三种算法则与障碍点个数的多少并未一向的涉嫌(当然,障碍点较少时方可通过对障碍点坐标的离散化来减小拍卖矩形的面积,不过如此相比坚苦,不如第一种算法好),适用于障碍点密集的场馆。

 

这是近些年经常出现的题材,例如冬令营2002的《奶牛浴场》,就属于最大子矩形问题。

五、   例题

将前方提出的二种算法运用于现实的题目。

Winter 坎普(Camp)2002,奶牛浴场

1、    Winter Camp2002,奶牛浴场

分析

题目标数学模型就是给出一个矩形和矩形中的一些障碍点,须求出矩形内的最大有效子矩形。那多亏大家眼前所研商的最大子矩形问题,因而前三种算法都适用于那么些题材。

下边分析三种算法运用在主旨上的优略:

对于第一种算法,不用加任何的改动就足以向来运用在那道题上,时间复杂度为O(S2),S为障碍点个数;空间复杂度为O(S)。

对于第二种算法,要求先做一定的预处理。由于第两种算法复杂度与牛场的面积有关,而问题中牛场的面积很大(30000×30000),因而要求对数码举行离散化处理。离散化后矩形的大大小小降为S×S,所以时间复杂度为O(S2),空间复杂度为O(S)。表达:必要留意的是,为了保证算法能正确执行,在离散化的时候必要加上S个点,因而实际必要的年华和空中较大,而且编程较复杂。

从上述的解析来看,无论从时空功能如故编程复杂度的角度来看,那道题利用第一种算法都更美好。

题意简述:

2、    OIBH模拟赛1,提高组,Candy

题意简述:(原题见杂文附件)

一个被分成 n*m 个格子的糖果盒,第 i 行第 j 列地点的格子里面有 a[i,j]
颗糖。但糖果盒的有的格子被老鼠洗劫。现在内需尽快从这几个糖果盒里面切割出一个矩形糖果盒,新的糖果盒不可能有洞,并且期望保留在新糖果盒内的糖的总额尽量多。

参数约定:1 ≤ n,m ≤ 1000

 

分析

第一必要专注的是:本题的模子是一个矩阵,而不是矩形。在矩阵的情事下,由于点的个数是简单的,所以又发出了一个新的题材:最大权值子矩阵

 

   定义:

   有效子矩阵为其中不包蕴其他障碍点的子矩形。与有效子矩形不一样,有效子矩阵地边界上也不可能包涵障碍点。

有效子矩阵的权值(只有有效子矩形才有权值)为那个子矩阵包罗的所有点的权值和。

最大权值有效子矩阵为所有有效子矩阵中权值最大的一个。以下简称为最大权值子矩阵

 

宗旨的数学模型就是正权值条件下的最大权值子矩阵问题。再两回选拔极大化思想,因为矩阵中的权值都是正的,所以最大权值子矩阵一定是一个极大子矩阵。所以大家只须要枚举所有的极大子矩阵,就能从中找到最大权值子矩阵。同样,二种算法只需稍加修改就足以缓解本题。上边分析二种算法应用在主旨上的优略:

对此第一种算法,由于矩形中障碍点的个数是不确定的,而且最大有可能高达N×M,那样时间复杂度有可能达到O(N2M2),空间复杂度为O(NM)。其它,由于矩形与矩阵的不相同,所以在拍卖上会有局地小麻烦。

对此第两种算法,稍加变换就可以直接接纳,时间复杂度为O(NM),空间复杂度为O(NM)。

 

可以看到,第一种算法并不吻合那道题,由此最好依然采用第三种算法。

John要在矩形牛场中建造一个巨型浴场,不过这么些特大型浴场不可能包蕴其他一个奶牛的产奶点,但产奶点可以出在浴室的边界上。约翰的牛场和设计的浴池都是矩形,浴场要完全位于牛场以内,并且浴场的大约要与牛场的概略平行或者重合。要求所求浴场的面积尽可能大。

3、    Usaco Training, Section 1.5.4, BigBarn

题意简述(原题见论文附件)

      Farmer
约翰(John)想在她的正方形农场上建一个正方形谷仓。由于农场上有一些树,而且Farmer
约翰又不想砍那些树,由此要找出最大的一个不含有任何树的一块正方形场合。每棵树都得以当做一个点。

参数约定:牛场为N×N的,树的棵数为T。N≤1000,T≤10000。

分析

    那题是矩形上的问题,但须求的是最大子正方形。首先,明确一些定义。

1、定义有效子正方形为内部不分包其余障碍点的子正方形

2、定义巨大有效子正方形为无法再向外扩展的有效子正方形,一下简称极大子正方形

3、定义最大有效子正方形为所有有效子正方形中最大的一个(或八个),以下简称最大子正方形

 

大旨的模型有部分非凡,要在一个带有一些障碍点的矩形中求最大子正方形。那与前两题的模子是或不是有相似之处呢?照旧从最大子正方形的面目初叶分析。

与前边的情况类似,利用极大化思想,大家可以赢得一个定律:

定理4】:在一个有障碍点的矩形中的最大有效子正方形一定是一个高大有效子正方形。

     

            
根据【定理4】,大家只需求枚举出所有的极大子正方形,就足以从中找出最大子正方形。极大子正方形有啥样特点呢?所谓极大,就是不可以再向外伸张。假若是极大子矩形,那么无法再向外扩大的充要条件是四条边上都掩盖了障碍点(【定理2】)。类似的,大家得以驾驭,一个有效子正方形是极大子正方形的充要条件是它任何两条相邻的一旁都覆盖了最少一个障碍点。根据那点,可以得到一个最主要的定律。

定理5】:每一个极大子正方形都至少被一个极大子矩形包罗。且那几个极大子正方形一定有两条不相邻的边与那些带有它的极大子矩形的边重合。

 

按照【定理5】,大家只要求枚举所有的极大子矩形,并检讨它所富含的极大子正方形(一个极大子矩形包蕴的极大子正方形都是均等大的)是还是不是是最大的就可以了。那样,问题的精神和后边所说的最大子矩形问题是同一的,同样的,所选拔的算法也是一样的。

因为算法1和算法2都枚举出了装有的极大子矩形,因而,算法1和算法2都足以用在焦点上。具体的拍卖方法如下:对于每一个枚举出的极大子矩形,如图所示,假若它的边长为a、b,那么它涵盖的极大子正方形的边长即为min(a,b)。

设想到N和T的轻重缓急不一,所以差其余算法会有两样的机能。下边分析三种算法应用在主旨上的优略。lovebet体育官网 9

对此第一种算法,时间复杂度为O(T2),对于第二种算法,时间复杂度为O(N2)。因为N<T,所以从时间复杂度的角度看,第两种算法要比第一种算法好。考虑到三个算法的上空复杂度都足以接受,所以选拔第两种算法较好些。

以下是率先种和第三种算法编程已毕后在USACO Training Program
Gateway上的运作时刻。可以看来,在数据较大时,算法2的频率比算法1高。

 

算法1:

Test  1:  0.009375

Test  2:  0.009375

Test  3:  0.009375

Test  4:  0.009375

Test  5:  0.009375

Test  6:  0.009375

Test  7:  0.021875

Test  8:     0.025

Test  9:  0.084375

Test 10:    0.3875

Test 11:     0.525

Test 12:    0.5625

Test 13:  0.690625

Test 14:   0.71875

Test 15:      0.75

算法2:

Test  1:  0.009375

Test  2:  0.009375

Test  3:  0.009375

Test  4:  0.009375

Test  5:  0.009375

Test  6:   0.00625

Test  7:  0.009375

Test  8:  0.009375

Test  9:    0.0125

Test 10:  0.021875

Test 11:  0.028125

Test 12:   0.03125

Test 13:   0.03125

Test 14:   0.03125

Test 15:  0.034375

 

上述,利用极大化思想和前边设计的五个算法,通过更换模型,解决了四个颇具一定代表性的例题。解题的重大就是怎么样行使极大化思想举行模型转换和哪些选用算法。

参数约定:产奶点的个数S不超越5000,牛场的范围N×M不超过30000×30000。

 六、小结

   
 设总结法要从问题的基本特征出手,找出解题的突破口。本文介绍了三种适用于多数最大子矩形问题及相关变更问题的算法,它们设计的突破口就是选用了极大化思想,找到了枚举极大子矩形那种艺术。

在功效上,二种算法对于不一致的图景各有千秋。一个是针对障碍点来统筹的,由此复杂度与障碍点有关;另一个是对准任何矩形来布置的,因而复杂度与矩形的面积有关。纵然五个算法看起来有着巨大的反差,但他俩的原形是相通的,都是行使极大化思想,从枚举所有的庞然大物有效子矩形下手,找出解决问题的方法。

        

 必要小心的是,在化解实际问题是仅靠套用一些存世算法是不够的,还必要对题目举办完善、透彻的辨析,找出解题的突破口。

除此以外,如若选用极大化思想,前边提到的三种算法的复杂度已经无法再下滑了,因为极大有效子矩形的个数就是O(NM)或O(S2)的。要是应用任何算法,理论上是有可能进一步提升算法作用,下跌复杂度的。 

二、 定义和认证

七、 附录:

      1、多少个例题的原题。       
杂文附件.doc

      2、例题的先后。           
杂文附件.doc

表达:所有程序均在Free Pascal IDE for Dos, Version  0.9.2上编译运行

第一肯定一些概念。

参考书目

1、     新闻学奥林匹克竞技指点

                         —-1997~1998交锋试题分析

            吴文虎 王建德 著

2、     IOI99中国集训队卓绝随笔集

3、     音讯学奥林匹克(季刊)

4、     《金牌之路 比赛指引》 

江文哉主编  山东师范学院出版社出版

 

初稿: 塔那那利佛第三中学  王知昆

1、定义有效子矩形为内部不分包其余障碍点且边界与坐标轴平行的子矩形。如图所示,第二个是有效子矩形(即便边界上有障碍点),第一个不是有效子矩形(因为里面含有障碍点)。

2、极大有效子矩形:一个有效子矩形,倘若不设有包罗它且比它大的有效子矩形,就称那一个有效子矩形为巨大有效子矩形。(为了叙述方便,以下称为极大子矩形)

3、定义最大有效子矩形为所有有效子矩形中最大的一个(或两个)。以下简称为最大子矩形。

三、 极大化思想

【定理1】在一个有障碍点的矩形中的最大子矩形一定是一个极大子矩形。

表明:倘若最大子矩形A不是一个极大子矩形,那么依照极大子矩形的概念,存在一个带有A且比A更大的有效子矩形,那与“A是最大子矩形”争执,所以【定理1】创制。

四、 从问题的特色出手,获得三种常用的算法
定理1纵然很明确,但却是很首要的。根据定理1,大家得以博得如此一个解题思路:

由此枚举所有的极大子矩形,就足以找到最大子矩形。下边依据那么些思路来安排算法。

约定:为了叙述方便,设任何矩形的高低为n×m,其中障碍点个数为s。

算法1

算法的思路是经过枚举所有的极大子矩形找出最大子矩形。根据这一个思路可以窥见,假诺算法中有一回枚举的子矩形不是有效子矩形、或者不是极大子矩形,那么能够一定那些算法做了“无用功”,那也就是内需优化的地点。怎么样有限支撑每回枚举的都是极大子矩形呢,大家先从极大子矩形的特征入手。

【定理2】:一个极大子矩形的四条边一定都不可以向外增添。更进一步地说,一个有效子矩形是极大子矩形的充要条件是以此子矩形的每条边要么覆盖了一个障碍点,要么与所有矩形的界限重合。

定理2的不利很明确,假设一个有效子矩形的某一条边既没有掩盖一个障碍点,又尚未与任何矩形的边界重合,那么必然存在一个富含它的有效子矩形。根据定理2,我们得以获取一个枚举极大子矩形的算法。为了处理方便,首先在障碍点的成团中添加整个矩形四角上的点。每便枚举子矩形的内外左左边界(枚举覆盖的障碍点),然后判断是或不是合法(内部是不是有隐含障碍点)。那样的算法时间复杂度为O(S5),明显太高了。考虑到极大子矩形无法包罗障碍点,由此那样枚举4个境界明显会暴发大批量的无效子矩形。

考虑只枚举左左侧际的动静。对于已经规定的左右侧界,能够将富有处在那个境界内的点按从上到下排序,如图1中所示,每一格就象征一个有效子矩形。那样做时间复杂度为O(S3)。由于保管每回获得的矩形都是官方的,所以枚举量比前一种算法小了过多。但须求注意的是,那样做枚举的子矩形即使是法定的,可是不自然是大幅度的。所以那几个算法还有优化的退路。通过对那个算法不足之处的优化,大家得以取得一个连忙的算法。

遥想上边的算法,大家简单窥见,所枚举的矩形的左左侧界都掩盖了障碍点或者与所有矩形的分界重合,问题就在于左右侧际上。只有那多少个左左边际也覆盖了障碍点或者与成套矩形的疆界重合的有效子矩形才是我们须要考察的极大子矩形,所此前边的算法做了好多“无用功”。怎么减弱“无用功”呢,那里介绍一种算法(算法1),它能够用在层见迭出此类题材上。

算法的思路是那样的,先枚举极大子矩形的左边界,然后从左到右依次扫描每一个障碍点,并连发修改可行的内外边界,从而枚举出所有以这么些定位为左侧界的极大子矩形。考虑如图2中的两个点,现在大家要规定所有以1号点为左侧界的偌大矩形。先将1号点左侧的点按横坐标排序。然后按从左到右的各样依次扫描1号点左边的点,同时记录下当前的有用的上上面界。

初叶时令当前的左左侧界分别为整个矩形的光景边界。然后初始扫描。第四遍遇上2号点,以2号点作为左边界,结合当前的内外边界,就获取一个极大子矩形(如图3)。同时,由于所求矩形不可以包括2号点,且2号点在1号点的下方,所以需求修改当前的上边界,即以2号点的纵坐标作为新的下面界。第二次相遇3号点,那时以3号点的横坐标作为左边界又有啥不可赢得一个满足性质1的矩形(如图4)。类似的,必要相应地修改上面界。以此类推,假若那几个点是在现阶段点(确定右边界的点)上方,则修改上面界;如若在人世,则修改上面际;假设处在同一行,则可间歇搜索(因为前边的矩形面积都是0了)。由于已经在障碍点集合中增

那般做是还是不是将装有的极大子矩形都枚举过了吧?可以发现,那样做只考虑到了左侧界覆盖一个点的矩形,因而大家还亟需枚举左侧界与成套矩形的右侧界重合的图景。那还是可以分成两类景况。一种是左侧界与任何进行的左侧界重合,而左侧界覆盖了一个障碍点的景况,对于这种情状,能够用类似的章程从右到左扫描每一个点作为左边界的事态。另一种是反正边际均与成套矩形的左右境界重合的景况,对于这类情状大家可以在预处理中形成:先将所有点按纵坐标排序,然后可以获取以相邻五个点的纵坐标为上下面界,左右境界与所有矩形的左左侧界重合的矩形,鲜明那样的矩形也是极大子矩形,因而也须要被枚举到。加了所有矩形右上角和右下角的八个点,所以不会遗漏左边界与任何矩形的左侧重合的极大子矩形(如图5)。须求注意的是,就算扫描到的点不在当前的左左边界内,那么就不要求对那一个点进

行处理。

因之前边两步,可以枚举出所有的极大子矩形。算法1的光阴复杂度是O(S2)。那样,可以解决大部分最大子矩形和连锁题材了。

虽说上述的算法(算法1)看起来是比较高效的,但也有利用的局限性。可以窥见,这些算法的复杂度只与障碍点的个数s有关。但对于一些问题,s最大有可能达到n×m,当s较大时,这些算法就不一定能满意时间上的渴求了。能不能设计出一种看重于n和m的算法呢?这样在算法1不可能奏效的时候大家还有其他选用。大家再重新从最要旨的题目起头商讨。

算法2

先是,按照定理1:最大有效子矩形一定是一个极大子矩形。可是与前一种算法不一致的是,我们不再需求每四次枚举的肯定是极大子矩形而只需要具备的极大子矩形都被枚举到。看起来那种算法可能比前一种差,其实不然,因为前一种算法并不是两全的:即使每一遍考察的都是极大子矩形,但它仍旧做了点儿的“无用功”。可以发现,当障碍点很密集的时候,前一种算法会做多量没用的相比工作。要解决这么些题目,大家亟须跳出后面的思绪,重新考虑一个新的算法。注意到极大子矩形的个数不会超过矩形内单位方格的个数,因此大家有可能找出一种时光复杂度是O(N×M)的算法。

定义:

使得竖线:除了四个端点外,不掩盖任何障碍点的竖直线段。

悬线:上端点覆盖了一个障碍点或达到全部矩形上端的有效竖线。如图所示的五个有效竖线都是悬线。

对此其余一个极大子矩形,它的上边界上依然有一个障碍点,要么和总体矩形的上面界重合。那么一旦把一个极大子矩形按x坐标分歧切割成七个(实际上是诸八个)与y轴垂直的线条,则其中肯定存在一条悬线。而且一条悬线通过尽可能地向左右活动恰好能博取一个子矩形(未必是极大子矩形,但只可能向下扩充)。通过以上的分析,我们可以得到一个主要的定律。

【定理3】:如若将一个悬线向左右多个方向尽可能移动所得到的有效子矩形称为那一个悬线所对应的子矩形,那么所有悬线所对应的有效子矩形的聚合一定带有了具备极大子矩形的见面。

定理3中的“尽可能”移动指的是活动到一个障碍点或者矩形边界的任务。

依照【定理3】可以窥见,通过枚举所有的悬线,就能够枚举出所有的极大子矩形。由于每个悬线都与它底部的那些点一一对应,所以悬线的个数=(n-1)×m(以矩形中除去顶部的点以外的各样点为尾部,都足以获得一个悬线,且并未遗漏)。若是能到位对各种悬线的操作时间都为O(1),那么万事算法的复杂度就是O(NM)。那样,大家见到明白决问题的希望。

近来的题目是,如何在O(1)的胎元内形成对各种悬线的操作。大家清楚,每个极大子矩形都能够由此一个悬线左右移动得到。所以,对于每个确定了底层的悬线,大家需求驾驭关于于它的多少个量:顶部、左右最多能移动到的任务。对于底部为(i,j)的悬线,设它的高为hight[i,j],左右最多能移动到的义务为left[i,j],right[i,j]。为了丰富利用此前得到的音信,我们将那多少个函数用递推的样式提交。

对于以点(i,j)为尾部的悬线:

比方点(i-1,j)为障碍点,那么,显明以(i,j)为底的悬线高度为1,而且左右均可以运动到全方位矩形的左左侧际,即

height[i,j]=l

left[i,j]=0

right[i,j]=m

若是点(i-1,j)不是障碍点,那么,以(i,j)为底的悬线就等于以(i-1,j)为底的悬线+点(i,j)到点(i-1,j)的线条。由此,height[i,j]=height[i-1,j]+1。比较费心的是反正境界,先考虑left[i,j]。如下图所示,(i,j)对应的悬线左右能移动的职位要在(i-1,j)的功底上转移。

即left[i,j]=max( left[i-1,j] , (i-1,j)左侧第四个障碍点地方 ) 如图

right[i,j]的求法类似。综合起来,能够拿走那三个参数的递推式:

height[i,j]=height[i-1,j]+1

left[i,j]=max( left[i-1,j] ,
(i-1,j)左侧第三个障碍点地点,边界0也是障碍点 )

right[i,j]=max( right[i-1,j] ,
(i-1,j)左边第三个障碍点地方,边界m也是阻碍点 )

这样做丰硕利用了此前得到的音讯,使每个悬线的拍卖时间复杂度为O(1)。对于以点(i,j)为底的悬线对应的子矩形,它的面积为(right[i,j]-left[i,j])*height[i,j]。

那般结尾问题的解就是:

Result=max(right[i,j]-left[i,j])*height[i,j] (l<=i<n,
l<=j<=m)

方方面面算法的时刻复杂度为O(NM),空间复杂度是O(NM)。

多个算法的自查自纠:

如上说了三种具有自然通用性的处理算法,时间复杂度分别为O(S2)和O(NM)。二种算法分别适用于分化的气象。从岁月复杂度上来看,第一种算法对于障碍点稀疏的景色比较实用,第二种算法则与障碍点个数的多少并未一向的涉及(当然,障碍点较少时得以经过对障碍点坐标的离散化来减小拍卖矩形的面积,不过尔尔相比较麻烦,不如第一种算法好),适用于障碍点密集的事态。

五、 例题

将眼前提出的两种算法运用于实际的题材。
1、 Winter Camp2002,奶牛浴场

分析:

问题的数学模型就是给出一个矩形和矩形中的一些障碍点,要求出矩形内的最大有效子矩形。那多亏大家面前所研讨的最大子矩形问题,因而前二种算法都适用于那些题目。

上边分析三种算法运用在大旨上的优略:

对于第一种算法,不用加任何的改动就足以间接使用在那道题上,时间复杂度为O(S2),S为障碍点个数;空间复杂度为O(S)。

对此第三种算法,须要先做肯定的预处理。由于第三种算法复杂度与牛场的面积有关,而题材中牛场的面积很大(30000×30000),由此须要对数据开展离散化处理。离散化后矩形的轻重缓急降为S×S,所以时间复杂度为O(S2),空间复杂度为O(S)。表达:要求专注的是,为了确保算法能正确实施,在离散化的时候须要足够S个点,因而实际必要的时日和空中较大,而且编程较复杂。

从以上的剖析来看,无论从时空成效如故编程复杂度的角度来看,那道题利用第一种算法都更可以。
2、 OIBH模拟赛1,提高组,Candy

题意简述:(原题见故事集附件)

一个被分为 n*m 个格子的糖果盒,第 i 行第 j 列地方的格子里面有 a[i,j]
颗糖。但糖果盒的局地格子被老鼠洗劫。现在急需赶紧从这些糖果盒里面切割出一个矩形糖果盒,新的糖果盒不可能有洞,并且期待保留在新糖果盒内的糖的总额尽量多。

参数约定:1 ≤ n,m ≤ 1000

分析

率先须要留意的是:本题的模型是一个矩阵,而不是矩形。在矩阵的情状下,由于点的个数是简单的,所以又发生了一个新的问题:最大权值子矩阵。

定义:

有效子矩阵为内部不带有其余障碍点的子矩形。与有效子矩形不一样,有效子矩阵地边界上也无法包罗障碍点。

有效子矩阵的权值(唯有有效子矩形才有权值)为这几个子矩阵包括的所有点的权值和。

最大权值有效子矩阵为所有有效子矩阵中权值最大的一个。以下简称为最大权值子矩阵。

宗旨的数学模型就是正权值条件下的最大权值子矩阵问题。再一回利用极大化思想,因为矩阵中的权值都是正的,所以最大权值子矩阵一定是一个极大子矩阵。所以我们只要求枚举所有的极大子矩阵,就能从中找到最大权值子矩阵。同样,三种算法只需稍加修改就可以解决本题。下边分析二种算法应用在焦点上的优略:

对于第一种算法,由于矩形中障碍点的个数是不确定的,而且最大有可能高达N×M,那样时间复杂度有可能达到O(N2M2),空间复杂度为O(NM)。其余,由于矩形与矩阵的不一致,所以在处理上会有局地小麻烦。

对此第两种算法,稍加变换就可以直接行使,时间复杂度为O(NM),空间复杂度为O(NM)。

可以见见,第一种算法并不切合那道题,因而最好仍旧采用第三种算法。
3、 Usaco Training, Section 1.5.4, BigBarn

题意简述(原题见随想附件)

  Farmer John想在他的正方形农场上建一个正方形谷仓。由于农场上有一些树,而且Farmer John又不想砍这些树,因此要找出最大的一个不包含任何树的一块正方形场地。每棵树都可以看成一个点。

参数约定:牛场为N×N的,树的棵数为T。N≤1000,T≤10000。

分析:

那题是矩形上的题目,但要求的是最大子正方形。首先,明确一些定义。

1、定义有效子正方形为其中不含有其他障碍点的子正方形

2、定义极大有效子正方形为无法再向外增添的有效子正方形,一下简称极大子正方形

3、定义最大有效子正方形为所有有效子正方形中最大的一个(或五个),以下简称最大子正方形。

大旨的模型有一部分与众分化,要在一个分包一些障碍点的矩形中求最大子正方形。那与前两题的模子是不是有相似之处呢?仍旧从最大子正方形的面目开端分析。

lovebet体育官网,与眼前的情事相近,利用极大化思想,大家能够收获一个定律:

【定理4】:在一个有障碍点的矩形中的最大有效子正方形一定是一个极大有效子正方形。

基于【定理4】,我们只须要枚举出所有的极大子正方形,就足以从中找出最大子正方形。极大子正方形有如何特色呢?所谓极大,就是无法再向外增添。如果是极大子矩形,那么不可能再向外扩充的充要条件是四条边上都掩盖了障碍点(【定理2】)。类似的,大家得以知道,一个有效子正方形是极大子正方形的充要条件是它任何两条相邻的一旁都覆盖了足足一个障碍点。根据那或多或少,可以赢得一个至关紧要的定律。

【定理5】:每一个极大子正方形都至少被一个极大子矩形包蕴。且这些极大子正方形一定有两条不相邻的边与那一个带有它的极大子矩形的边重合。

基于【定理5】,大家只须求枚举所有的极大子矩形,并检查它所涵盖的极大子正方形(一个极大子矩形包蕴的极大子正方形都是千篇一律大的)是不是是最大的就足以了。那样,问题的实质和前边所说的最大子矩形问题是均等的,同样的,所选用的算法也是同样的。

因为算法1和算法2都枚举出了具有的极大子矩形,由此,算法1和算法2都得以用在主旨上。具体的拍卖形式如下:对于每一个枚举出的极大子矩形,如图所示,如若它的边长为a、b,那么它包涵的极大子正方形的边长即为min(a,b)。

设想到N和T的轻重差别,所以不一致的算法会有例外的作用。上边分析三种算法应用在主题上的优略。

对于第一种算法,时间复杂度为O(T2),对于第三种算法,时间复杂度为O(N2)。因为N<T,所以从岁月复杂度的角度看,第两种算法要比第一种算法好。考虑到四个算法的长空复杂度都足以承受,所以拔取第三种算法较好些。

以下是第一种和第三种算法编程完毕后在USACO Training Program
Gateway上的运行时刻。可以看看,在数额较大时,算法2的功用比算法1高。

算法1:

Test 1: 0.009375

Test 2: 0.009375

Test 3: 0.009375

Test 4: 0.009375

Test 5: 0.009375

Test 6: 0.009375

Test 7: 0.021875

Test 8: 0.025

Test 9: 0.084375

Test 10: 0.3875

Test 11: 0.525

Test 12: 0.5625

Test 13: 0.690625

Test 14: 0.71875

Test 15: 0.75

算法2:

Test 1: 0.009375

Test 2: 0.009375

Test 3: 0.009375

Test 4: 0.009375

Test 5: 0.009375

Test 6: 0.00625

Test 7: 0.009375

Test 8: 0.009375

Test 9: 0.0125

Test 10: 0.021875

Test 11: 0.028125

Test 12: 0.03125

Test 13: 0.03125

Test 14: 0.03125

Test 15: 0.034375

如上,利用极大化思想和眼前设计的七个算法,通过转移模型,解决了多少个有着自然代表性的例题。解题的显要就是什么利用极大化思想举行模型转换和什么挑选算法。
六、小结

 设计算法要从问题的基本特征入手,找出解题的突破口。本文介绍了两种适用于大部分最大子矩形问题及相关变型问题的算法,它们设计的突破口就是利用了极大化思想,找到了枚举极大子矩形这种方法。

在成效上,三种算法对于分歧的情状各有千秋。一个是针对障碍点来布署的,因而复杂度与障碍点有关;另一个是对准所有矩形来统筹的,因而复杂度与矩形的面积有关。固然五个算法看起来有着光辉的差异,但他们的真相是相通的,都是使用极大化思想,从枚举所有的极大有效子矩形下手,找出解决问题的点子。

亟需专注的是,在化解实际问题是仅靠套用一些共处算法是不够的,还需求对问题进行完善、透彻的剖析,找出解题的突破口。

除此以外,假如接纳极大化思想,前面提到的二种算法的复杂度已经不可以再下滑了,因为极大有效子矩形的个数就是O(NM)或O(S2)的。假若使用任何算法,理论上是有可能进一步提升算法作用,下落复杂度的。
七、 附录:

1、多少个例题的原题。 见杂谈附件.doc

2、例题的顺序。 见随想附件.doc

表达:所有程序均在Free Pascal IDE for Dos, Version 0.9.2上编译运行
参考书目

1、 新闻学奥林匹克竞技辅导

—-1997~1998竞赛试题分析

吴文虎 王建德 著

2、 IOI99中国集训队出色随想集

3、 音讯学奥林匹克(季刊)

4、 《金牌之路 竞技指导》

江文哉主编 河南中医药学院出版社出版

初稿: 华雷斯第三中学 王知昆

相关文章