最大子矩陣的枚舉方法

1、題意簡述： John要在牛場中建造一個大型浴場，但是這個大型浴場不能覆蓋任何一個奶牛的產(chǎn)奶點。John的牛場和規(guī)劃的浴場都是矩形，浴場要完全位于牛場之內(nèi)，并且浴場的輪廓要與牛場的輪廓平行或者重合。要求所求浴場的面積盡可能大。參數(shù)約定：產(chǎn)奶點的個數(shù)S不超過5000,牛場的范圍N×M不超過30000×30000。,,問題：奶牛浴場,最大子矩形問題： 在一個給定的矩形中有一些障礙點，要找出內(nèi)部

2、不包含任何障礙點的，輪廓與整個矩形平行或重合的最大子矩形。,,問題的模型,定義和說明,定義有效子矩形為內(nèi)部不包含任何障礙點的，邊界與坐標軸平行的子矩形。 如下圖所示，第一個是有效子矩形，第二個不是。,,,,,,,,,,,,,定義和說明,,定義極大子矩形為每條邊都不能向外擴展的有效子矩形。定義最大子矩形為所有有效子矩形中最大的一個（或多個）。,極大化思想,,在一個有障礙點的矩形中的最大子矩形一定是一個極大子矩形。 設計算法的思

3、路：通過枚舉所有的極大子矩形，找出最大子矩形。,兩個不同的算法,,針對問題的性質，可以設計出兩個不同的算法。他們分別適用于不同的情況。約定：為了敘述方便，設整個矩形的大小為N×M，其中障礙點個數(shù)為S。,算法1時間復雜度：O(S2)空間復雜度：O(S),算法2時間復雜度：O(NM)空間復雜度：O(S),算法1 思路,從極大子矩形的性質入手。極大子矩形的性質： 一個極大子矩形的每條邊一定都不能向外擴

4、展。更進一步地說，一個有效子矩形是極大子矩形的條件是這個子矩形的每條邊要么覆蓋了障礙點，要么與整個矩形的邊界重合。,,,,,,算法設計,基本算法算法：枚舉上下左右四個邊界，然后判斷組成的矩形是否是有效子矩形。復雜度：O(S5)可以改進的地方： 產(chǎn)生了大量的無效子矩形,初步改進算法算法：枚舉左右邊界，然后對處在邊界內(nèi)的點排序。每兩個相鄰的點和左右邊界一起組成一個矩形。復雜度：O(S3)可以改進的地方： 枚舉了

5、部分不是極大子矩形的情況,算法改進,設計算法的方向： 1、保證每一個枚舉的子矩形都是有效的 2、保證每一個枚舉的子矩形都是極大的 算法的過程： 枚舉極大子矩形的左邊界 → 根據(jù)確定的左邊界，找出相關的極 大子矩形 → 檢查和處理遺漏的情況,算法1,首先，將所有障礙點按橫坐標從小到大的順序將點標為1號點，2號點……,,,,,,1,2,3,4,算法1,為了處理方便，在矩形

6、的四個頂點上各增加1個障礙點。,,,,,,,,,,算法1,第一次取1號點作為所要枚舉的極大子矩形的左邊界設定上下邊界為矩形的上下邊界,,,,,,,,,,,左邊界,,,上邊界,下邊界,,1,算法1,從左向右掃描，第一次遇到2號點，可以得到一個有效的極大子矩形，如圖所示,,,,,,,,,,左邊界,,,上邊界,下邊界,,1,2,算法1,因為左邊界覆蓋1號點且右邊界在2號點右邊的有效子矩形都不能包含2號點，所以需要修改上下邊界2號點在1號點

7、上方，因此要修改上邊界,,,,,,,,,,左邊界,,,上邊界,下邊界,,1,2,算法1,繼續(xù)掃描到3號點，又得到一個極大有效子矩形，如圖所示,,,,,,,,,,左邊界,,,上邊界,下邊界,,1,3,算法1,因為3號點在1號點下方，所以要修改下邊界。,,,,,,,,,,左邊界,,,上邊界,下邊界,,1,3,算法1,以此類推，可以得到所有以1號點為左邊界的極大有效子矩形。然后將左邊界移動到2號點、3號點……橫坐標的位置。開始掃描以2號點、

8、3號點……為左邊界的極大子矩形。,,,,,,,,,,,左邊界,,,上邊界,下邊界,,2,3,算法1 遺漏的情況,前面的做法可以找出所有左邊界覆蓋了一個障礙點的極大子矩形，此外，還有兩類遺漏的情況。,,,,,,,,,,算法1 遺漏的情況,一類是左邊界與整個矩形的左邊界重合，右邊界覆蓋一個障礙點的情況。解決方法：用類似的方法從右向左掃描一次。,,,,,,,,,,,算法1 遺漏的情況,另一類是左邊界與整個矩形的左邊界重合，且右邊界也與整個矩

9、形的右邊界重合的情況。解決方法：預處理時增加特殊判斷。,,,,,,,,,,,算法1 優(yōu)劣分析,算法1的時間復雜度為O(S2)，空間復雜度為O(S)。優(yōu)點：利用了極大化思想，復雜度可以接受，編程實現(xiàn)簡單。缺點：使用有一定的局限性，不適合障礙點較密集的情況。,算法2 設計的目的和思路,因為算法1有使用的局限性，所以我們需要一種在障礙點很密集的時候仍能奏效的算法。設計一種復雜度依賴于整個矩形面積的算法 說明：如果整個矩形面積

10、很大，可以通過離散化處理來優(yōu)化。,算法2 懸線,有效豎線：除了兩個端點外，不覆蓋任何障礙點的豎直線段。懸線：上端點覆蓋了一個障礙點或達到整個矩形上端的有效豎線。圖中所示的線段均為懸線。,,,,,,,,算法2 懸線,每個懸線都與它底部的點一一對應。 矩形中的每一個點（矩形頂部的點除外）都對應了一個懸線。懸線的個數(shù)＝(N－1)×M,,,,,,,,,,算法2 懸線與極大子矩形,如果把一個極大子矩形按x坐標不同切割成多

11、個與y軸平行的線段，則其中至少存在一個懸線。,,,,,,,,,,,,……,,,Y,X,算法2 懸線與極大子矩形,如果把一個懸線向左右兩個方向盡可能移動，就能得到一個矩形，不妨稱為這個懸線對應的矩形。懸線對應的矩形不一定是極大子矩形，因為下邊界可能還可以向下擴展。,,,,,,,,,設計算法,原理：所有懸線對應矩形的集合一定包含了極大子矩形的集合。通過枚舉所有的懸線，找出所有的極大子矩形。算法規(guī)模： 懸線個數(shù)

12、＝(N－1)×M 極大子矩形個數(shù)≤懸線個數(shù),算法2 關鍵點,解決問題的關鍵： 對每個懸線的處理時間。解決方法： 充分利用前面得到的信息。,算法2 處理方法,具體方法： 設 H[i,j]為點(i,j)對應的懸線的長度。 L[i,j]為點(i,j)對應的懸線向左最多能夠移動到的位置。 R[i,j]為點(i,j)對應的懸線向右最多能夠移動到的位置。,圖

13、示,,,,,,,,,,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

14、,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

15、[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)右邊第一個障

16、礙點的位置,,,,,,,,,,,L[i,j],R[i,j],,H[i,j],點(i,j),,算法2 優(yōu)劣分析,算法2的時間復雜度為O(NM)，空間復雜度為O(S)。優(yōu)點： 復雜度與障礙點個數(shù)沒有直接關系。缺點：障礙點少時處理較復雜，不如算法1,兩個不同的算法,,算法1時間復雜度：O(S2)空間復雜度：O(S)優(yōu)點：復雜度可以接受，編程實現(xiàn)簡單缺點：使用有一定的局限性，不適合障礙點較密集的情況。,算法2時間復雜度：O

17、(NM)空間復雜度：O(S) 優(yōu)點：復雜度與障礙點個數(shù)沒有直接關系。缺點：障礙點少時因為要離散化處理，實際復雜度較高。,推廣1 最大權值子矩形問題,最大權值子矩形問題模型：在一個帶權（正權）矩形中有一些障礙點，找出一個不包含障礙點的最大權值子矩形。分析：在一個正權值的矩形中的最大權值子矩形一定是極大子矩形。所以，問題實際上可以依據(jù)極大化的思想，利用前面的方法解決。,推廣2 最大子正方形問題,最大子正方形問題模型

18、：在一個矩形中存在S個障礙點，要求找出最大的不包含障礙點的正方形。分析：在一個有障礙點的矩形中的最大有效子正方形一定是一個極大有效子正方形。,推廣2 最大子正方形問題,極大子正方形的性質： 每一個極大子正方形都至少被一個極大子矩形包含，且這個極大子正方形一定有兩條不相鄰的邊與包含它的極大子矩形的邊重合。,,,,,推廣2 最大子正方形問題,解決方法:通過枚舉每一個極大子矩形找出所有的極大子正方形。每個極大子