淺談?dòng)脴O大化思想解決最大子矩形問題

1、淺談?dòng)脴O大化思想解決最大子矩形問題福州第三中學(xué) 王知昆【摘要】 本文針對(duì)一類近期經(jīng)常出現(xiàn)的有關(guān)最大（或最優(yōu)）子矩形及相關(guān)變形問題，介紹了極大化思想在這類問題中的應(yīng)用。分析了兩個(gè)具有一定通用性的算法。并通過一些例題講述了這些算法選擇和使用時(shí)的一些技巧?！娟P(guān)鍵字】 矩形，障礙點(diǎn)，極大子矩形【正文】一、 問題最大子矩形問題：在一個(gè)給定的矩形網(wǎng)格中有一些障礙點(diǎn)，要找出網(wǎng)格內(nèi)部不包含任何障礙點(diǎn)，且邊界與坐標(biāo)軸平行的最大子矩形。這是近期經(jīng)常出現(xiàn)的問題，例如冬令營(yíng)2002的奶牛浴場(chǎng)，就屬于最大子矩形問題。Winter Camp2002,奶牛浴場(chǎng)題意簡(jiǎn)述：（原題見論文附件）John要在矩形牛場(chǎng)中建造一個(gè)大型浴

2、場(chǎng)，但是這個(gè)大型浴場(chǎng)不能包含任何一個(gè)奶牛的產(chǎn)奶點(diǎn)，但產(chǎn)奶點(diǎn)可以出在浴場(chǎng)的邊界上。John的牛場(chǎng)和規(guī)劃的浴場(chǎng)都是矩形，浴場(chǎng)要完全位于牛場(chǎng)之內(nèi)，并且浴場(chǎng)的輪廓要與牛場(chǎng)的輪廓平行或者重合。要求所求浴場(chǎng)的面積盡可能大。參數(shù)約定：產(chǎn)奶點(diǎn)的個(gè)數(shù)S不超過5000,牛場(chǎng)的范圍N×M不超過30000×30000。二、 定義和說明首先明確一些概念。1、 定義有效子矩形為內(nèi)部不包含任何障礙點(diǎn)且邊界與坐標(biāo)軸平行的子矩形。如圖所示，第一個(gè)是有效子矩形（盡管邊界上有障礙點(diǎn)），第二個(gè)不是有效子矩形（因?yàn)閮?nèi)部含有障礙點(diǎn)）。2、 極大有效子矩形：一個(gè)有效子矩形，如果不存在包含它且比它大的有效子矩形，就稱這個(gè)

3、有效子矩形為極大有效子矩形。（為了敘述方便，以下稱為極大子矩形）3、 定義最大有效子矩形為所有有效子矩形中最大的一個(gè)（或多個(gè)）。以下簡(jiǎn)稱為最大子矩形。三、 極大化思想【定理1】在一個(gè)有障礙點(diǎn)的矩形中的最大子矩形一定是一個(gè)極大子矩形。證明：如果最大子矩形A不是一個(gè)極大子矩形，那么根據(jù)極大子矩形的定義，存在一個(gè)包含A且比A更大的有效子矩形，這與“A是最大子矩形”矛盾，所以【定理1】成立。四、 從問題的特征入手，得到兩種常用的算法定理1雖然很顯然，但卻是很重要的。根據(jù)定理1，我們可以得到這樣一個(gè)解題思路：通過枚舉所有的極大子矩形，就可以找到最大子矩形。下面根據(jù)這個(gè)思路來設(shè)計(jì)算法。約定：為了敘述方便，

4、設(shè)整個(gè)矩形的大小為n×m，其中障礙點(diǎn)個(gè)數(shù)為s。 算法1算法的思路是通過枚舉所有的極大子矩形找出最大子矩形。根據(jù)這個(gè)思路可以發(fā)現(xiàn)，如果算法中有一次枚舉的子矩形不是有效子矩形、或者不是極大子矩形，那么可以肯定這個(gè)算法做了“無用功”，這也就是需要優(yōu)化的地方。怎樣保證每次枚舉的都是極大子矩形呢，我們先從極大子矩形的特征入手?！径ɡ?】：一個(gè)極大子矩形的四條邊一定都不能向外擴(kuò)展。更進(jìn)一步地說，一個(gè)有效子矩形是極大子矩形的充要條件是這個(gè)子矩形的每條邊要么覆蓋了一個(gè)障礙點(diǎn)，要么與整個(gè)矩形的邊界重合。定理2的正確性很顯然，如果一個(gè)有效子矩形的某一條邊既沒有覆蓋一個(gè)障礙點(diǎn)，又沒有與整個(gè)矩形的邊界重合，

5、那么肯定存在一個(gè)包含它的有效子矩形。根據(jù)定理2，我們可以得到一個(gè)枚舉極大子矩形的算法。為了處理方便，首先在障礙點(diǎn)的集合中加上整個(gè)矩形四角上的點(diǎn)。每次枚舉子矩形的上下左右邊界（枚舉覆蓋的障礙點(diǎn)），然后判斷是否合法（內(nèi)部是否有包含障礙點(diǎn)）。這樣的算法時(shí)間復(fù)雜度為O(S5)，顯然太高了。考慮到極大子矩形不能包含障礙點(diǎn)，因此這樣枚舉4個(gè)邊界顯然會(huì)產(chǎn)生大量的無效子矩形?？紤]只枚舉左右邊界的情況。對(duì)于已經(jīng)確定的左右邊界，可以將所有處在這個(gè)邊界內(nèi)的點(diǎn)按從上到下排序，如圖1中所示，每一格就代表一個(gè)有效子矩形。這樣做時(shí)間復(fù)雜度為O(S3)。由于確保每次得到的矩形都是合法的，所以枚舉量比前一種算法小了很多。但需要

6、注意的是，這樣做枚舉的子矩形雖然是合法的，然而不一定是極大的。所以這個(gè)算法還有優(yōu)化的余地。通過對(duì)這個(gè)算法不足之處的優(yōu)化，我們可以得到一個(gè)高效的算法?；仡櫳厦娴乃惴ǎ覀儾浑y發(fā)現(xiàn)，所枚舉的矩形的上下邊界都覆蓋了障礙點(diǎn)或者與整個(gè)矩形的邊界重合，問題就在于左右邊界上。只有那些左右邊界也覆蓋了障礙點(diǎn)或者與整個(gè)矩形的邊界重合的有效子矩形才是我們需要考察的極大子矩形，所以前面的算法做了不少“無用功”。怎么減少“無用功”呢，這里介紹一種算法（算法1），它可以用在不少此類題目上。算法的思路是這樣的，先枚舉極大子矩形的左邊界，然后從左到右依次掃描每一個(gè)障礙點(diǎn)，并不斷修改可行的上下邊界，從而枚舉出所有以這個(gè)定點(diǎn)為

7、左邊界的極大子矩形。考慮如圖2中的三個(gè)點(diǎn)，現(xiàn)在我們要確定所有以1號(hào)點(diǎn)為左邊界的極大矩形。先將1號(hào)點(diǎn)右邊的點(diǎn)按橫坐標(biāo)排序。然后按從左到右的順序依次掃描1號(hào)點(diǎn)右邊的點(diǎn)，同時(shí)記錄下當(dāng)前的可行的上下邊界。開始時(shí)令當(dāng)前的上下邊界分別為整個(gè)矩形的上下邊界。然后開始掃描。第一次遇到2號(hào)點(diǎn)，以2號(hào)點(diǎn)作為右邊界，結(jié)合當(dāng)前的上下邊界，就得到一個(gè)極大子矩形（如圖3）。同時(shí)，由于所求矩形不能包含2號(hào)點(diǎn)，且2號(hào)點(diǎn)在1號(hào)點(diǎn)的下方，所以需要修改當(dāng)前的下邊界，即以2號(hào)點(diǎn)的縱坐標(biāo)作為新的下邊界。第二次遇到3號(hào)點(diǎn)，這時(shí)以3號(hào)點(diǎn)的橫坐標(biāo)作為右邊界又可以得到一個(gè)滿足性質(zhì)1的矩形（如圖4）。類似的，需要相應(yīng)地修改上邊界。以此類推，如果

8、這個(gè)點(diǎn)是在當(dāng)前點(diǎn)（確定左邊界的點(diǎn)）上方，則修改上邊界；如果在下方，則修改下邊界；如果處在同一行，則可中止搜索（因?yàn)楹竺娴木匦蚊娣e都是0了）。由于已經(jīng)在障礙點(diǎn)集合中增加了整個(gè)矩形右上角和右下角的兩個(gè)點(diǎn)，所以不會(huì)遺漏右邊界與整個(gè)矩形的右邊重合的極大子矩形（如圖5）。需要注意的是，如果掃描到的點(diǎn)不在當(dāng)前的上下邊界內(nèi)，那么就不需要對(duì)這個(gè)點(diǎn)進(jìn)行處理。這樣做是否將所有的極大子矩形都枚舉過了呢？可以發(fā)現(xiàn)，這樣做只考慮到了左邊界覆蓋一個(gè)點(diǎn)的矩形，因此我們還需要枚舉左邊界與整個(gè)矩形的左邊界重合的情況。這還可以分為兩類情況。一種是左邊界與整個(gè)舉行的左邊界重合，而右邊界覆蓋了一個(gè)障礙點(diǎn)的情況，對(duì)于這種情況，可以用類

9、似的方法從右到左掃描每一個(gè)點(diǎn)作為右邊界的情況。另一種是左右邊界均與整個(gè)矩形的左右邊界重合的情況，對(duì)于這類情況我們可以在預(yù)處理中完成：先將所有點(diǎn)按縱坐標(biāo)排序，然后可以得到以相鄰兩個(gè)點(diǎn)的縱坐標(biāo)為上下邊界，左右邊界與整個(gè)矩形的左右邊界重合的矩形，顯然這樣的矩形也是極大子矩形，因此也需要被枚舉到。通過前面兩步，可以枚舉出所有的極大子矩形。算法1的時(shí)間復(fù)雜度是O(S2)。這樣，可以解決大多數(shù)最大子矩形和相關(guān)問題了。雖然以上的算法（算法1）看起來是比較高效的，但也有使用的局限性?？梢园l(fā)現(xiàn)，這個(gè)算法的復(fù)雜度只與障礙點(diǎn)的個(gè)數(shù)s有關(guān)。但對(duì)于某些問題，s最大有可能達(dá)到n×m，當(dāng)s較大時(shí)，這個(gè)算法就未必能

10、滿足時(shí)間上的要求了。能否設(shè)計(jì)出一種依賴于n和m的算法呢？這樣在算法1不能奏效的時(shí)候我們還有別的選擇。我們?cè)僦匦聫淖罨镜膯栴}開始研究。算法2 首先，根據(jù)定理1：最大有效子矩形一定是一個(gè)極大子矩形。不過與前一種算法不同的是，我們不再要求每一次枚舉的一定是極大子矩形而只要求所有的極大子矩形都被枚舉到?？雌饋磉@種算法可能比前一種差，其實(shí)不然，因?yàn)榍耙环N算法并不是完美的：雖然每次考察的都是極大子矩形，但它還是做了一定量的“無用功”。可以發(fā)現(xiàn)，當(dāng)障礙點(diǎn)很密集的時(shí)候，前一種算法會(huì)做大量沒用的比較工作。要解決這個(gè)問題，我們必須跳出前面的思路，重新考慮一個(gè)新的算法。注意到極大子矩形的個(gè)數(shù)不會(huì)超過矩形內(nèi)單位方格

11、的個(gè)數(shù)，因此我們有可能找出一種時(shí)間復(fù)雜度是O(N×M)的算法。 定義：有效豎線：除了兩個(gè)端點(diǎn)外，不覆蓋任何障礙點(diǎn)的豎直線段。懸線：上端點(diǎn)覆蓋了一個(gè)障礙點(diǎn)或達(dá)到整個(gè)矩形上端的有效豎線。如圖所示的三個(gè)有效豎線都是懸線。 對(duì)于任何一個(gè)極大子矩形，它的上邊界上要么有一個(gè)障礙點(diǎn)，要么和整個(gè)矩形的上邊界重合。那么如果把一個(gè)極大子矩形按x坐標(biāo)不同切割成多個(gè)（實(shí)際上是無數(shù)個(gè)）與y軸垂直的線段，則其中一定存在一條懸線。而且一條懸線通過盡可能地向左右移動(dòng)恰好能得到一個(gè)子矩形（未必是極大子矩形，但只可能向下擴(kuò)展）。通過以上的分析，我們可以得到一個(gè)重要的定理。【定理3】：如果將一個(gè)懸線向左右兩個(gè)方向盡可能移

12、動(dòng)所得到的有效子矩形稱為這個(gè)懸線所對(duì)應(yīng)的子矩形，那么所有懸線所對(duì)應(yīng)的有效子矩形的集合一定包含了所有極大子矩形的集合。定理3中的“盡可能”移動(dòng)指的是移動(dòng)到一個(gè)障礙點(diǎn)或者矩形邊界的位置。根據(jù)【定理3】可以發(fā)現(xiàn)，通過枚舉所有的懸線，就可以枚舉出所有的極大子矩形。由于每個(gè)懸線都與它底部的那個(gè)點(diǎn)一一對(duì)應(yīng)，所以懸線的個(gè)數(shù)(n-1)×m（以矩形中除了頂部的點(diǎn)以外的每個(gè)點(diǎn)為底部，都可以得到一個(gè)懸線，且沒有遺漏）。如果能做到對(duì)每個(gè)懸線的操作時(shí)間都為O(1)，那么整個(gè)算法的復(fù)雜度就是O(NM)。這樣，我們看到了解決問題的希望。 現(xiàn)在的問題是，怎樣在O(1)的時(shí)間內(nèi)完成對(duì)每個(gè)懸線的操作。我們知道，每個(gè)極大

13、子矩形都可以通過一個(gè)懸線左右平移得到。所以，對(duì)于每個(gè)確定了底部的懸線，我們需要知道有關(guān)于它的三個(gè)量：頂部、左右最多能移動(dòng)到的位置。對(duì)于底部為(i,j)的懸線，設(shè)它的高為highti,j,左右最多能移動(dòng)到的位置為lefti,j,righti,j。為了充分利用以前得到的信息，我們將這三個(gè)函數(shù)用遞推的形式給出。 對(duì)于以點(diǎn)(i,j)為底部的懸線：如果點(diǎn)(i1,j)為障礙點(diǎn)，那么，顯然以(i,j)為底的懸線高度為1，而且左右均可以移動(dòng)到整個(gè)矩形的左右邊界，即如果點(diǎn)(i1,j)不是障礙點(diǎn)，那么，以(i,j)為底的懸線就等于以(i-1,j)為底的懸線點(diǎn)(i,j)到點(diǎn)(i-1,j)的線段。因此，heighti

14、,j=heighti-1,j+1。比較麻煩的是左右邊界，先考慮lefti,j。如下圖所示，(i,j)對(duì)應(yīng)的懸線左右能移動(dòng)的位置要在(i-1,j)的基礎(chǔ)上變化。即lefti,j=max (i,j):當(dāng)前點(diǎn)某個(gè)障礙lefti-1,jlefti,j(i-1,j)righti,j的求法類似。綜合起來，可以得到這三個(gè)參數(shù)的遞推式： 這樣做充分利用了以前得到的信息，使每個(gè)懸線的處理時(shí)間復(fù)雜度為O(1)。對(duì)于以點(diǎn)(i,j)為底的懸線對(duì)應(yīng)的子矩形，它的面積為(righti,j-lefti,j)*heighti,j。這樣最后問題的解就是：Resultmax整個(gè)算法的時(shí)間復(fù)雜度為O(NM)，空間復(fù)雜度是O(NM)

15、。 兩個(gè)算法的對(duì)比：以上說了兩種具有一定通用性的處理算法，時(shí)間復(fù)雜度分別為O(S2)和O(NM)。兩種算法分別適用于不同的情況。從時(shí)間復(fù)雜度上來看，第一種算法對(duì)于障礙點(diǎn)稀疏的情況比較有效，第二種算法則與障礙點(diǎn)個(gè)數(shù)的多少?zèng)]有直接的關(guān)系（當(dāng)然，障礙點(diǎn)較少時(shí)可以通過對(duì)障礙點(diǎn)坐標(biāo)的離散化來減小處理矩形的面積，不過這樣比較麻煩，不如第一種算法好），適用于障礙點(diǎn)密集的情況。五、 例題將前面提出的兩種算法運(yùn)用于具體的問題。1、 Winter Camp2002,奶牛浴場(chǎng)分析：題目的數(shù)學(xué)模型就是給出一個(gè)矩形和矩形中的一些障礙點(diǎn)，要求出矩形內(nèi)的最大有效子矩形。這正是我們前面所討論的最大子矩形問題，因此前兩種算法都

16、適用于這個(gè)問題。下面分析兩種算法運(yùn)用在本題上的優(yōu)略：對(duì)于第一種算法，不用加任何的修改就可以直接應(yīng)用在這道題上，時(shí)間復(fù)雜度為O(S2)，S為障礙點(diǎn)個(gè)數(shù)；空間復(fù)雜度為O(S)。對(duì)于第二種算法，需要先做一定的預(yù)處理。由于第二種算法復(fù)雜度與牛場(chǎng)的面積有關(guān)，而題目中牛場(chǎng)的面積很大（30000×30000），因此需要對(duì)數(shù)據(jù)進(jìn)行離散化處理。離散化后矩形的大小降為S×S，所以時(shí)間復(fù)雜度為O(S2)，空間復(fù)雜度為O(S)。說明：需要注意的是，為了保證算法能正確執(zhí)行，在離散化的時(shí)候需要加上S個(gè)點(diǎn)，因此實(shí)際需要的時(shí)間和空間較大，而且編程較復(fù)雜。從以上的分析來看，無論從時(shí)空效率還是編程復(fù)雜度的角度

17、來看，這道題采用第一種算法都更優(yōu)秀。2、 OIBH模擬賽1,提高組，Candy題意簡(jiǎn)述：（原題見論文附件）一個(gè)被分為 n*m個(gè)格子的糖果盒，第 i 行第 j 列位置的格子里面有 a i,j 顆糖。但糖果盒的一些格子被老鼠洗劫?，F(xiàn)在需要盡快從這個(gè)糖果盒里面切割出一個(gè)矩形糖果盒，新的糖果盒不能有洞，并且希望保留在新糖果盒內(nèi)的糖的總數(shù)盡量多。參數(shù)約定：1 n，m 1000分析首先需要注意的是：本題的模型是一個(gè)矩陣，而不是矩形。在矩陣的情況下，由于點(diǎn)的個(gè)數(shù)是有限的，所以又產(chǎn)生了一個(gè)新的問題：最大權(quán)值子矩陣。 定義： 有效子矩陣為內(nèi)部不包含任何障礙點(diǎn)的子矩形。與有效子矩形不同，有效子矩陣地邊界上也不能包

18、含障礙點(diǎn)。有效子矩陣的權(quán)值（只有有效子矩形才有權(quán)值）為這個(gè)子矩陣包含的所有點(diǎn)的權(quán)值和。最大權(quán)值有效子矩陣為所有有效子矩陣中權(quán)值最大的一個(gè)。以下簡(jiǎn)稱為最大權(quán)值子矩陣。本題的數(shù)學(xué)模型就是正權(quán)值條件下的最大權(quán)值子矩陣問題。再一次利用極大化思想，因?yàn)榫仃囍械臋?quán)值都是正的，所以最大權(quán)值子矩陣一定是一個(gè)極大子矩陣。所以我們只需要枚舉所有的極大子矩陣，就能從中找到最大權(quán)值子矩陣。同樣，兩種算法只需稍加修改就可以解決本題。下面分析兩種算法應(yīng)用在本題上的優(yōu)略：對(duì)于第一種算法，由于矩形中障礙點(diǎn)的個(gè)數(shù)是不確定的，而且最大有可能達(dá)到N×M,這樣時(shí)間復(fù)雜度有可能達(dá)到O(N2M2)，空間復(fù)雜度為O(NM)。此外

19、，由于矩形與矩陣的不同，所以在處理上會(huì)有一些小麻煩。對(duì)于第二種算法，稍加變換就可以直接使用，時(shí)間復(fù)雜度為O(NM),空間復(fù)雜度為O（NM）?？梢钥闯觯谝环N算法并不適合這道題，因此最好還是采用第二種算法。3、 Usaco Training, Section 1.5.4, Big Barn題意簡(jiǎn)述（原題見論文附件） Farmer John想在他的正方形農(nóng)場(chǎng)上建一個(gè)正方形谷倉(cāng)。由于農(nóng)場(chǎng)上有一些樹，而且Farmer John又不想砍這些樹，因此要找出最大的一個(gè)不包含任何樹的一塊正方形場(chǎng)地。每棵樹都可以看成一個(gè)點(diǎn)。參數(shù)約定：牛場(chǎng)為N×N的，樹的棵數(shù)為T。N1000,T10000。分析： 這題

20、是矩形上的問題，但要求的是最大子正方形。首先，明確一些概念。1、 定義有效子正方形為內(nèi)部不包含任何障礙點(diǎn)的子正方形2、 定義極大有效子正方形為不能再向外擴(kuò)展的有效子正方形，一下簡(jiǎn)稱極大子正方形3、 定義最大有效子正方形為所有有效子正方形中最大的一個(gè)（或多個(gè)），以下簡(jiǎn)稱最大子正方形。本題的模型有一些特殊，要在一個(gè)含有一些障礙點(diǎn)的矩形中求最大子正方形。這與前兩題的模型是否有相似之處呢？還是從最大子正方形的本質(zhì)開始分析。與前面的情況類似，利用極大化思想，我們可以得到一個(gè)定理：【定理4】：在一個(gè)有障礙點(diǎn)的矩形中的最大有效子正方形一定是一個(gè)極大有效子正方形。 根據(jù)【定理4】,我們只需要枚舉出所有的極大子

21、正方形，就可以從中找出最大子正方形。極大子正方形有什么特征呢？所謂極大，就是不能再向外擴(kuò)展。如果是極大子矩形，那么不能再向外擴(kuò)展的充要條件是四條邊上都覆蓋了障礙點(diǎn)（【定理2】）。類似的，我們可以知道，一個(gè)有效子正方形是極大子正方形的充要條件是它任何兩條相鄰的邊上都覆蓋了至少一個(gè)障礙點(diǎn)。根據(jù)這一點(diǎn)，可以得到一個(gè)重要的定理。【定理5】：每一個(gè)極大子正方形都至少被一個(gè)極大子矩形包含。且這個(gè)極大子正方形一定有兩條不相鄰的邊與這個(gè)包含它的極大子矩形的邊重合。根據(jù)【定理5】,我們只需要枚舉所有的極大子矩形，并檢查它所包含的極大子正方形（一個(gè)極大子矩形包含的極大子正方形都是一樣大的）是否是最大的就可以了。這

22、樣，問題的實(shí)質(zhì)和前面所說的最大子矩形問題是一樣的，同樣的，所采用的算法也是一樣的。因?yàn)樗惴?和算法2都枚舉出了所有的極大子矩形，因此，算法1和算法2都可以用在本題上。具體的處理方法如下：對(duì)于每一個(gè)枚舉出的極大子矩形，如圖所示，如果它的邊長(zhǎng)為a、b，那么它包含的極大子正方形的邊長(zhǎng)即為min(a,b)?？紤]到N和T的大小不同，所以不同的算法會(huì)有不同的效果。下面分析兩種算法應(yīng)用在本題上的優(yōu)略。對(duì)于第一種算法，時(shí)間復(fù)雜度為O(T2)，對(duì)于第二種算法，時(shí)間復(fù)雜度為O(N2)。因?yàn)镹<T，所以從時(shí)間復(fù)雜度的角度看，第二種算法要比第一種算法好。考慮到兩個(gè)算法的空間復(fù)雜度都可以承受，所以選擇第二種算法較

23、好些。以下是第一種和第二種算法編程實(shí)現(xiàn)后在USACO Training Program Gateway上的運(yùn)行時(shí)間?？梢钥闯?，在數(shù)據(jù)較大時(shí)，算法2的效率比算法1高。算法1：Test 1: 0.009375Test 2: 0.009375Test 3: 0.009375Test 4: 0.009375Test 5: 0.009375Test 6: 0.009375Test 7: 0.021875Test 8: 0.025Test 9: 0.084375Test 10: 0.3875Test 11: 0.525Test 12: 0.5625Test 13: 0.690625Test 14: 0.71875Test 15: 0.75算法2：Test 1: 0.009375Test 2: 0.009375Test 3: 0.009375Test 4: 0.009375Test 5: 0.009375Test 6: 0.00625Test 7: 0.009375Test 8: 0.0093