淺談用極大化思想解決最大子矩形問題

王知昆第 11 頁IOI2003國家集訓隊論文淺談用極大化思想解決最大子矩形問題福州第三中學 王知昆【摘要】 本文針對一類近期經常出現(xiàn)的有關最大（或最優(yōu)）子矩形及相關變形問題，介紹了極大化思想在這類問題中的應用。分析了兩個具有一定通用性的算法。并通過一些例題講述了這些算法選擇和使用時的一些技巧。【關鍵字】 矩形，障礙點，極大子矩形【正文】一、 問題最大子矩形問題：在一個給定的矩形網格中有一些障礙點，要找出網格內部不包含任何障礙點，且邊界與坐標軸平行的最大子矩形。這是近期經常出現(xiàn)的問題，例如冬令營2002的奶牛浴場，就屬于最大子矩形問題。Winter Camp2002,奶牛浴場題意簡述：（原題見論文附件）John要在矩形牛場中建造一個大型浴場，但是這個大型浴場不能包含任何一個奶牛的產奶點，但產奶點可以出在浴場的邊界上。John的牛場和規(guī)劃的浴場都是矩形，浴場要完全位于牛場之內，并且浴場的輪廓要與牛場的輪廓平行或者重合。要求所求浴場的面積盡可能大。參數(shù)約定：產奶點的個數(shù)S不超過5000,牛場的范圍NM不超過3000030000。二、 定義和說明首先明確一些概念。1、 定義有效子矩形為內部不包含任何障礙點且邊界與坐標軸平行的子矩形。如圖所示，第一個是有效子矩形（盡管邊界上有障礙點），第二個不是有效子矩形（因為內部含有障礙點）。2、 極大有效子矩形：一個有效子矩形，如果不存在包含它且比它大的有效子矩形，就稱這個有效子矩形為極大有效子矩形。（為了敘述方便，以下稱為極大子矩形）3、 定義最大有效子矩形為所有有效子矩形中最大的一個（或多個）。以下簡稱為最大子矩形。三、 極大化思想【定理1】在一個有障礙點的矩形中的最大子矩形一定是一個極大子矩形。證明：如果最大子矩形A不是一個極大子矩形，那么根據(jù)極大子矩形的定義，存在一個包含A且比A更大的有效子矩形，這與“A是最大子矩形”矛盾，所以【定理1】成立。四、 從問題的特征入手，得到兩種常用的算法定理1雖然很顯然，但卻是很重要的。根據(jù)定理1，我們可以得到這樣一個解題思路：通過枚舉所有的極大子矩形，就可以找到最大子矩形。下面根據(jù)這個思路來設計算法。約定：為了敘述方便，設整個矩形的大小為nm，其中障礙點個數(shù)為s。 算法1算法的思路是通過枚舉所有的極大子矩形找出最大子矩形。根據(jù)這個思路可以發(fā)現(xiàn)，如果算法中有一次枚舉的子矩形不是有效子矩形、或者不是極大子矩形，那么可以肯定這個算法做了“無用功”，這也就是需要優(yōu)化的地方。怎樣保證每次枚舉的都是極大子矩形呢，我們先從極大子矩形的特征入手?！径ɡ?】：一個極大子矩形的四條邊一定都不能向外擴展。更進一步地說，一個有效子矩形是極大子矩形的充要條件是這個子矩形的每條邊要么覆蓋了一個障礙點，要么與整個矩形的邊界重合。定理2的正確性很顯然，如果一個有效子矩形的某一條邊既沒有覆蓋一個障礙點，又沒有與整個矩形的邊界重合，那么肯定存在一個包含它的有效子矩形。根據(jù)定理2，我們可以得到一個枚舉極大子矩形的算法。為了處理方便，首先在障礙點的集合中加上整個矩形四角上的點。每次枚舉子矩形的上下左右邊界（枚舉覆蓋的障礙點），然后判斷是否合法（內部是否有包含障礙點）。這樣的算法時間復雜度為O(S5)，顯然太高了。考慮到極大子矩形不能包含障礙點，因此這樣枚舉4個邊界顯然會產生大量的無效子矩形?？紤]只枚舉左右邊界的情況。對于已經確定的左右邊界，可以將所有處在這個邊界內的點按從上到下排序，如圖1中所示，每一格就代表一個有效子矩形。這樣做時間復雜度為O(S3)。由于確保每次得到的矩形都是合法的，所以枚舉量比前一種算法小了很多。但需要注意的是，這樣做枚舉的子矩形雖然是合法的，然而不一定是極大的。所以這個算法還有優(yōu)化的余地。通過對這個算法不足之處的優(yōu)化，我們可以得到一個高效的算法。回顧上面的算法，我們不難發(fā)現(xiàn)，所枚舉的矩形的上下邊界都覆蓋了障礙點或者與整個矩形的邊界重合，問題就在于左右邊界上。只有那些左右邊界也覆蓋了障礙點或者與整個矩形的邊界重合的有效子矩形才是我們需要考察的極大子矩形，所以前面的算法做了不少“無用功”。怎么減少“無用功”呢，這里介紹一種算法（算法1），它可以用在不少此類題目上。算法的思路是這樣的，先枚舉極大子矩形的左邊界，然后從左到右依次掃描每一個障礙點，并不斷修改可行的上下邊界，從而枚舉出所有以這個定點為左邊界的極大子矩形。考慮如圖2中的三個點，現(xiàn)在我們要確定所有以1號點為左邊界的極大矩形。先將1號點右邊的點按橫坐標排序。然后按從左到右的順序依次掃描1號點右邊的點，同時記錄下當前的可行的上下邊界。開始時令當前的上下邊界分別為整個矩形的上下邊界。然后開始掃描。第一次遇到2號點，以2號點作為右邊界，結合當前的上下邊界，就得到一個極大子矩形（如圖3）。同時，由于所求矩形不能包含2號點，且2號點在1號點的下方，所以需要修改當前的下邊界，即以2號點的縱坐標作為新的下邊界。第二次遇到3號點，這時以3號點的橫坐標作為右邊界又可以得到一個滿足性質1的矩形（如圖4）。類似的，需要相應地修改上邊界。以此類推，如果這個點是在當前點（確定左邊界的點）上方，則修改上邊界；如果在下方，則修改下邊界；如果處在同一行，則可中止搜索（因為后面的矩形面積都是0了）。由于已經在障礙點集合中增加了整個矩形右上角和右下角的兩個點，所以不會遺漏右邊界與整個矩形的右邊重合的極大子矩形（如圖5）。需要注意的是，如果掃描到的點不在當前的上下邊界內，那么就不需要對這個點進行處理。這樣做是否將所有的極大子矩形都枚舉過了呢？可以發(fā)現(xiàn)，這樣做只考慮到了左邊界覆蓋一個點的矩形，因此我們還需要枚舉左邊界與整個矩形的左邊界重合的情況。這還可以分為兩類情況。一種是左邊界與整個舉行的左邊界重合，而右邊界覆蓋了一個障礙點的情況，對于這種情況，可以用類似的方法從右到左掃描每一個點作為右邊界的情況。另一種是左右邊界均與整個矩形的左右邊界重合的情況，對于這類情況我們可以在預處理中完成：先將所有點按縱坐標排序，然后可以得到以相鄰兩個點的縱坐標為上下邊界，左右邊界與整個矩形的左右邊界重合的矩形，顯然這樣的矩形也是極大子矩形，因此也需要被枚舉到。通過前面兩步，可以枚舉出所有的極大子矩形。算法1的時間復雜度是O(S2)。這樣，可以解決大多數(shù)最大子矩形和相關問題了。雖然以上的算法（算法1）看起來是比較高效的，但也有使用的局限性?？梢园l(fā)現(xiàn)，這個算法的復雜度只與障礙點的個數(shù)s有關。但對于某些問題，s最大有可能達到nm，當s較大時，這個算法就未必能滿足時間上的要求了。能否設計出一種依賴于n和m的算法呢？這樣在算法1不能奏效的時候我們還有別的選擇。我們再重新從最基本的問題開始研究。算法2 首先，根據(jù)定理1：最大有效子矩形一定是一個極大子矩形。不過與前一種算法不同的是，我們不再要求每一次枚舉的一定是極大子矩形而只要求所有的極大子矩形都被枚舉到?？雌饋磉@種算法可能比前一種差，其實不然，因為前一種算法并不是完美的：雖然每次考察的都是極大子矩形，但它還是做了一定量的“無用功”?？梢园l(fā)現(xiàn)，當障礙點很密集的時候，前一種算法會做大量沒用的比較工作。要解決這個問題，我們必須跳出前面的思路，重新考慮一個新的算法。注意到極大子矩形的個數(shù)不會超過矩形內單位方格的個數(shù)，因此我們有可能找出一種時間復雜度是O(NM)的算法。 定義：有效豎線：除了兩個端點外，不覆蓋任何障礙點的豎直線段。懸線：上端點覆蓋了一個障礙點或達到整個矩形上端的有效豎線。如圖所示的三個有效豎線都是懸線。 對于任何一個極大子矩形，它的上邊界上要么有一個障礙點，要么和整個矩形的上邊界重合。那么如果把一個極大子矩形按x坐標不同切割成多個（實際上是無數(shù)個）與y軸垂直的線段，則其中一定存在一條懸線。而且一條懸線通過盡可能地向左右移動恰好能得到一個子矩形（未必是極大子矩形，但只可能向下擴展）。通過以上的分析，我們可以得到一個重要的定理?！径ɡ?】：如果將一個懸線向左右兩個方向盡可能移動所得到的有效子矩形稱為這個懸線所對應的子矩形，那么所有懸線所對應的有效子矩形的集合一定包含了所有極大子矩形的集合。定理3中的“盡可能”移動指的是移動到一個障礙點或者矩形邊界的位置。根據(jù)【定理3】可以發(fā)現(xiàn)，通過枚舉所有的懸線，就可以枚舉出所有的極大子矩形。由于每個懸線都與它底部的那個點一一對應，所以懸線的個數(shù)(n-1)m（以矩形中除了頂部的點以外的每個點為底部，都可以得到一個懸線，且沒有遺漏）。如果能做到對每個懸線的操作時間都為O(1)，那么整個算法的復雜度就是O(NM)。這樣，我們看到了解決問題的希望。 現(xiàn)在的問題是，怎樣在O(1)的時間內完成對每個懸線的操作。我們知道，每個極大子矩形都可以通過一個懸線左右平移得到。所以，對于每個確定了底部的懸線，我們需要知道有關于它的三個量：頂部、左右最多能移動到的位置。對于底部為(i,j)的懸線，設它的高為highti,j,左右最多能移動到的位置為lefti,j,righti,j。為了充分利用以前得到的信息，我們將這三個函數(shù)用遞推的形式給出。 對于以點(i,j)為底部的懸線：如果點(i1,j)為障礙點，那么，顯然以(i,j)為底的懸線高度為1，而且左右均可以移動到整個矩形的左右邊界，即如果點(i1,j)不是障礙點，那么，以(i,j)為底的懸線就等于以(i-1,j)為底的懸線點(i,j)到點(i-1,j)的線段。因此，heighti,j=heighti-1,j+1。比較麻煩的是左右邊界，先考慮lefti,j。如下圖所示，(i,j)對應的懸線左右能移動的位置要在(i-1,j)的基礎上變化。即lefti,j=max (i,j):當前點某個障礙lefti-1,jlefti,j(i-1,j)righti,j的求法類似。綜合起來，可以得到這三個參數(shù)的遞推式： 這樣做充分利用了以前得到的信息，使每個懸線的處理時間復雜度為O(1)。對于以點(i,j)為底的懸線對應的子矩形，它的面積為(righti,j-lefti,j)*heighti,j。這樣最后問題的解就是：Resultmax整個算法的時間復雜度為O(NM)，空間復雜度是O(NM)。 兩個算法的對比：以上說了兩種具有一定通用性的處理算法，時間復雜度分別為O(S2)和O(NM)。兩種算法分別適用于不同的情況。從時間復雜度上來看，第一種算法對于障礙點稀疏的情況比較有效，第二種算法則與障礙點個數(shù)的多少沒有直接的關系（當然，障礙點較少時可以通過對障礙點坐標的離散化來減小處理矩形的面積，不過這樣比較麻煩，不如第一種算法好），適用于障礙點密集的情況。五、 例題將前面提出的兩種算法運用于具體的問題。1、 Winter Camp2002,奶牛浴場分析：題目的數(shù)學模型就是給出一個矩形和矩形中的一些障礙點，要求出矩形內的最大有效子矩形。這正是我們前面所討論的最大子矩形問題，因此前兩種算法都適用于這個問題。下面分析兩種算法運用在本題上的優(yōu)略：對于第一種算法，不用加任何的修改就可以直接應用在這道題上，時間復雜度為O(S2)，S為障礙點個數(shù)；空間復雜度為O(S)。對于第二種算法，需要先做一定的預處理。由于第二種算法復雜度與牛場的面積有關，而題目中牛場的面積很大（3000030000），因此需要對數(shù)據(jù)進行離散化處理。離散化后矩形的大小降為SS，所以時間復雜度為O(S2)，空間復雜度為O(S)。說明：需要注意的是，為了保證算法能正確執(zhí)行，在離散化的時候需要加上S個點，因此實際需要的時間和空間較大，而且編程較復雜。從以上的分析來看，無論從時空效率還是編程復雜度的角度來看，這道題采用第一種算法都更優(yōu)秀。2、 OIBH模擬賽1,提高組，Candy題意簡述：（原題見論文附件）一個被分為 n*m個格子的糖果盒，第 i 行第 j 列位置的格子里面有 a i,j 顆糖。但糖果盒的一些格子被老鼠洗劫。現(xiàn)在需要盡快從這個糖果盒里面切割出一個矩形糖果盒，新的糖果盒不能有洞，并且希望保留在新糖果盒內的糖的總數(shù)盡量多。參數(shù)約定：1 n，m 1000分析首先需要注意的是：本題的模型是一個矩陣，而不是矩形。在矩陣的情況下，由于點的個數(shù)是有限的，所以又產生了一個新的問題：最大權值子矩陣。 定義： 有效子矩陣為內部不包含任何障礙點的子矩形。與有效子矩形不同，有效子矩陣地邊界上也不能包含障礙點。有效子矩陣的權值（只有有效子矩形才有權值）為這個子矩陣包含的所有點的權值和。最大權值有效子矩陣為所有有效子矩陣中權值最大的一個。以下簡稱為最大權值子矩陣。本題的數(shù)學模型就是正權值條件下的最大權值子矩陣問題。再一次利用極大化思想，因為矩陣中的權值都是正的，所以最大權值子矩陣一定是一個極大子矩陣。所以我們只需要枚舉所有的極大子矩陣，就能從中找到最大權值子矩陣。同樣，兩種算法只需稍加修改就可以解決本題。下面分析兩種算法應用在本題上的優(yōu)略：對于第一種算法，由于矩形中障礙點的個數(shù)是不確定的，而且最大有可能達到NM,這樣時間復雜度有可能達到O(N2M2)，空間復雜度為O(NM)。此外，由于矩形與矩陣的不同，所以在處理上會有一些小麻煩。對于第二種算法，稍加變換就可以直接使用，時間復雜度為O(NM),空間復雜度為O（NM）?？梢钥闯觯谝环N算法并不適合這道題，因此最好還是采用第二種算法。3、 Usaco Training, Section 1.5.4, Big Barn題意簡述（原題見論文附件） Farmer John想在他的正方形農場上建一個正方形谷倉。由于農場上有一些樹，而且Farmer John又不想砍這些樹，因此要找出最大的一個不包含任何樹的一塊正方形場地。每棵樹都可以看成一個點。參數(shù)約定：牛場為NN的，樹的棵數(shù)為T。N1000,T10000。分析： 這題是矩形上的問題，但要求的是最大子正方形。首先，明確一些概念。1、 定義有效子正方形為內部不包含任何障礙點的子正方形2、 定義極大有效子正方形為不能再向外擴展的有效子正方形，一下簡稱極大子正方形3、 定義最大有效子正方形為所有有效子正方形中最大的一個（或多個），以下簡稱最大子正方形。本題的模型有一些特殊，要在一個含有一些障礙點的矩形中求最大子正方形。這與前兩題的模型是否有相似之處呢？還是從最大子正方形的本質開始分析。與前面的情況類似，利用極大化思想，我們可以得到一個定理：【定理4】：在一個有障礙點的矩形中的最大有效子正方形一定是一個極大有效子正方形。 根據(jù)【定理4】,我們只需要枚舉出所有的極大子正方形，就可以從中找出最大子正方形。極大子正方形有什么特征呢？所謂極大，就是不能再向外擴展。如果是極大子矩形，那么不能再向外擴展的充要條件是四條邊上都覆蓋了障礙點（【定理2】）。類似的，我們可以知道，一個有效子正方形是極大子正方形的充要條件是它任何兩條相鄰的邊上都覆蓋了至少一個障礙點。根據(jù)這一點，可以得到一個重要的定理。【定理5】：每一個極大子正方形都至少被一個極大子矩形包含。且這個極大子正方形一定有兩條不相鄰的邊與這個包含它的極大子矩形的邊重合。根據(jù)【定理5】,我們只需要枚舉所有的極大子矩形，并檢查它所包含的極大子正方形（一個極大子矩形包含的極大子正方形都是一樣大的）是否是最大的就可以了。這樣，問題的實質和前面所說的最大子矩形問題是一樣的，同樣的，所采用的算法也是一樣的。因為算法1和算法2都枚舉出了所有的極大子矩形，因此，算法1和算法2都可以用在本題上。具體的處理方法如下：對于每一個枚舉出的極大子矩形，如圖所示，如果它的邊長為a、b，那么它包含的極大子正方形的邊長即為min(a,b)。考慮到N和T的大小不同，所以不同的算法會有不同的效果。下面分析兩種算法應用在本題上的優(yōu)略。對于第一種算法，時間復雜度為O(T2)，對于第二種算法，時間復雜度為O(N2)。因為NT，所以從時間復雜度的角度看，第二種算法要比第一種算法好?？紤]到兩個算法的空間復雜度都可以承受，所以選擇第二種算法較好些。以下是第一種和第二種算法編程實現(xiàn)后在USACO Training Program Gateway上的運行時間?？梢钥闯觯跀?shù)據(jù)較大時，算法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.009375Te