最大子矩陣的枚舉方法

1、題意簡(jiǎn)述： John要在牛場(chǎng)中建造一個(gè)大型浴場(chǎng)，但是這個(gè)大型浴場(chǎng)不能覆蓋任何一個(gè)奶牛的產(chǎn)奶點(diǎn)。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不超過(guò)5000,牛場(chǎng)的范圍N×M不超過(guò)30000×30000。,,問(wèn)題：奶牛浴場(chǎng),最大子矩形問(wèn)題： 在一個(gè)給定的矩形中有一些障礙點(diǎn)，要找出內(nèi)部

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

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

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

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

6、的四個(gè)頂點(diǎn)上各增加1個(gè)障礙點(diǎn)。,,,,,,,,,,算法1,第一次取1號(hào)點(diǎn)作為所要枚舉的極大子矩形的左邊界設(shè)定上下邊界為矩形的上下邊界,,,,,,,,,,,左邊界,,,上邊界,下邊界,,1,算法1,從左向右掃描，第一次遇到2號(hào)點(diǎn)，可以得到一個(gè)有效的極大子矩形，如圖所示,,,,,,,,,,左邊界,,,上邊界,下邊界,,1,2,算法1,因?yàn)樽筮吔绺采w1號(hào)點(diǎn)且右邊界在2號(hào)點(diǎn)右邊的有效子矩形都不能包含2號(hào)點(diǎn)，所以需要修改上下邊界2號(hào)點(diǎn)在1號(hào)點(diǎn)

7、上方，因此要修改上邊界,,,,,,,,,,左邊界,,,上邊界,下邊界,,1,2,算法1,繼續(xù)掃描到3號(hào)點(diǎn)，又得到一個(gè)極大有效子矩形，如圖所示,,,,,,,,,,左邊界,,,上邊界,下邊界,,1,3,算法1,因?yàn)?號(hào)點(diǎn)在1號(hào)點(diǎn)下方，所以要修改下邊界。,,,,,,,,,,左邊界,,,上邊界,下邊界,,1,3,算法1,以此類(lèi)推，可以得到所有以1號(hào)點(diǎn)為左邊界的極大有效子矩形。然后將左邊界移動(dòng)到2號(hào)點(diǎn)、3號(hào)點(diǎn)……橫坐標(biāo)的位置。開(kāi)始掃描以2號(hào)點(diǎn)、

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

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

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

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

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

13、示,,,,,,,,,,L[i,j],R[i,j],,H[i,j],點(diǎn)(i,j),考慮點(diǎn)(i,j)對(duì)應(yīng)的懸線與點(diǎn)(i-1,j)對(duì)應(yīng)的懸線的關(guān)系。,算法2 遞推關(guān)系,如果(i－1,j)為障礙點(diǎn)，那么，如圖所示，(i,j)對(duì)應(yīng)的懸線長(zhǎng)度1，左右能移動(dòng)到的位置是整個(gè)矩形的左右邊界。即 H[i,j]＝1, L[i,j]=0,R[i,j]=m,,,,,(i-1,j):障礙點(diǎn),(i,j):當(dāng)前點(diǎn),,,,,,R[i,j],L[i,j],,H[i

14、,j]=1,算法2 遞推關(guān)系,如果(i－1,j)不是障礙點(diǎn)，那么，如圖所示，(i,j)對(duì)應(yīng)的懸線長(zhǎng)度為(i-1,j)對(duì)應(yīng)的懸線長(zhǎng)度＋1。即 H[i,j]＝H[i-1,j]+1,,,,(i-1,j):非障礙點(diǎn),(i,j):當(dāng)前點(diǎn),,,某個(gè)障礙,算法2 遞推關(guān)系,如果(i－1,j)不是障礙點(diǎn)，那么，如圖所示，(i,j)對(duì)應(yīng)的懸線左右能移動(dòng)的位置要在(i-1,j)的基礎(chǔ)上變化。 L[i-1,j]L

15、[i,j]=max (i-1,j)左邊第一個(gè)障礙點(diǎn)的位置,,,,(i,j):當(dāng)前點(diǎn),,,某個(gè)障礙,,,,,L[i-1,j],,L[i,j],,(i-1,j),,,算法2 遞推關(guān)系,同理，也可以得到R[i,j]的遞推式 R[i-1,j] R[i,j]=min (i-1,j)右邊第一個(gè)障

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

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

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