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

1、淺談?dòng)脴O大化思想解決最大子矩形淺談?dòng)脴O大化思想解決最大子矩形問題問題福州第三中學(xué) 王知昆問題：奶牛浴場(chǎng)問題：奶牛浴場(chǎng)題意簡(jiǎn)述題意簡(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不超過5000,牛場(chǎng)的范圍NM不超過3000030000。問題的模型問題的模型 最大子矩形問題： 在一個(gè)給定的矩形中有一些障礙點(diǎn)，要找出內(nèi)部不包含任何障礙點(diǎn)的，輪廓與整個(gè)矩形平行或重合的最大子矩形。定義和說明定義和說明 定義有效

2、子矩形有效子矩形為內(nèi)部不包含任何障礙點(diǎn)的，邊界與坐標(biāo)軸平行的子矩形。 如下圖所示，第一個(gè)是有效子矩形，第二個(gè)不是。定義和說明定義和說明極大化思想極大化思想兩個(gè)不同的算法兩個(gè)不同的算法針對(duì)問題的性質(zhì)，可以設(shè)計(jì)出兩個(gè)不同的算法。他們分別適用于不同的情況。約定：約定：為了敘述方便，設(shè)整個(gè)矩形的大小為NM，其中障礙點(diǎn)個(gè)數(shù)為S。算法算法1 思路思路從極大子矩形的性質(zhì)入手。極大子矩形的性質(zhì)： 一個(gè)極大子矩形的每條邊一定都不能向外擴(kuò)展。更進(jìn)一步地說，一個(gè)有效子矩形是極大子矩形的條件是這個(gè)子矩形的每條邊要么覆蓋了障礙點(diǎn)，要么與整個(gè)矩形的邊界重合。算法設(shè)計(jì)算法設(shè)計(jì) 基本算法算法：枚舉上下左右四個(gè)邊界，然后判斷組

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

4、增加1個(gè)障礙點(diǎn)。算法算法1 1 第一次取1號(hào)點(diǎn)作為所要枚舉的極大子矩形的左邊界 設(shè)定上下邊界為矩形的上下邊界 左邊界上邊界下邊界1算法算法1 1 從左向右掃描，第一次遇到2號(hào)點(diǎn)，可以得到一個(gè)有效的極大子矩形，如圖所示 左邊界上邊界下邊界12算法算法1 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)上方，因此要修改上邊界 左邊界上邊界下邊界12算法算法1 1 繼續(xù)掃描到3號(hào)點(diǎn)，又得到一個(gè)極大有效子矩形，如圖所示 左邊界上邊界下邊界13算法算法1 1 因?yàn)?號(hào)點(diǎn)在1號(hào)點(diǎn)下方，所以要修改下邊界。 左邊界上邊界下邊界13算法算法1 1以此類推

5、，可以得到所有以1號(hào)點(diǎn)為左邊界的極大有效子矩形。然后將左邊界移動(dòng)到2號(hào)點(diǎn)、3號(hào)點(diǎn)橫坐標(biāo)的位置。開始掃描以2號(hào)點(diǎn)、3號(hào)點(diǎn)為左邊界的極大子矩形。 左邊界上邊界下邊界23算法算法1 1 遺漏的情況遺漏的情況 前面的做法可以找出所有左邊界覆蓋了一個(gè)障礙點(diǎn)的極大子矩形，此外，還有兩類遺漏的情況。算法算法1 1 遺漏的情況遺漏的情況一類是左邊界與整個(gè)矩形的左邊界重合，右邊界覆蓋一個(gè)障礙點(diǎn)的情況。解決方法：用類似的方法從右向左掃描一次。算法算法1 1 遺漏的情況遺漏的情況另一類是左邊界與整個(gè)矩形的左邊界重合，且右邊界也與整個(gè)矩形的右邊界重合的情況。解決方法：預(yù)處理時(shí)增加特殊判斷。算法算法1 1 優(yōu)劣分析優(yōu)劣

6、分析 算法1的時(shí)間復(fù)雜度為O(S2)，空間復(fù)雜度為O(S)。 優(yōu)點(diǎn)：利用了極大化思想，復(fù)雜度可以接受，編程實(shí)現(xiàn)簡(jiǎn)單。 缺點(diǎn)：使用有一定的局限性，不適合障礙點(diǎn)較密集的情況。算法算法2 2 設(shè)計(jì)的目的和思路設(shè)計(jì)的目的和思路 因?yàn)樗惴?有使用的局限性，所以我們需要一種在障礙點(diǎn)很密集的時(shí)候仍能奏效的算法。 設(shè)計(jì)一種復(fù)雜度依賴于整個(gè)矩形面積的算法 說明：如果整個(gè)矩形面積很大，可以通過離散化處理來優(yōu)化。算法算法2 2 懸線懸線有效豎線：除了兩個(gè)端點(diǎn)外，不覆蓋任何障礙點(diǎn)的豎直線段。懸線：上端點(diǎn)覆蓋了一個(gè)障礙點(diǎn)或達(dá)到整個(gè)矩形上端的有效豎線。圖中所示的線段均為懸線。算法算法2 2 懸線懸線 每個(gè)懸線都與它底部的

7、點(diǎn)一一對(duì)應(yīng)。 矩形中的每一個(gè)點(diǎn)（矩形頂部的點(diǎn)除外）都對(duì)應(yīng)了一個(gè)懸線。 懸線的個(gè)數(shù)(N1)M算法算法2 2 懸線與極大子矩形懸線與極大子矩形 如果把一個(gè)極大子矩形按x坐標(biāo)不同切割成多個(gè)與y軸平行的線段，則其中至少存在一個(gè)懸線。YX算法算法2 2 懸線與極大子矩形懸線與極大子矩形如果把一個(gè)懸線向左右兩個(gè)方向盡可能移動(dòng)，就能得到一個(gè)矩形，不妨稱為這個(gè)懸線對(duì)應(yīng)的矩形。懸線對(duì)應(yīng)的矩形不一定是極大子矩形，因?yàn)橄逻吔缈赡苓€可以向下擴(kuò)展。設(shè)計(jì)算法設(shè)計(jì)算法 原理：所有懸線對(duì)應(yīng)矩形的集合一定包含了極大子矩形的集合。 通過枚舉所有的懸線，找出所有的極大子矩形。 算法規(guī)模： 懸線個(gè)數(shù)(N1)M 極大子矩形個(gè)數(shù)懸線個(gè)數(shù)

8、算法算法2 2 關(guān)鍵點(diǎn)關(guān)鍵點(diǎn) 解決問題的關(guān)鍵： 對(duì)每個(gè)懸線的處理時(shí)間。 解決方法： 充分利用前面得到的信息。算法算法2 2 處理方法處理方法具體方法： 設(shè) Hi,j為點(diǎn)(i,j)對(duì)應(yīng)的懸線的長(zhǎng)度。 Li,j為點(diǎn)(i,j)對(duì)應(yīng)的懸線向左最多能夠移動(dòng)到的位置位置。 Ri,j為點(diǎn)(i,j)對(duì)應(yīng)的懸線向右最多能夠移動(dòng)到的位置位置。圖示圖示Li,jRi,jHi,j點(diǎn)(i,j)算法算法2 2 遞推關(guān)系遞推關(guān)系如果(i1,j)為障礙點(diǎn)，那么，如圖所示，(i,j)對(duì)應(yīng)的懸線長(zhǎng)度1，左右能移動(dòng)到的位置是整個(gè)矩形的左右邊界。即 Hi,j1, Li,j=0,Ri,j=m(i-1,j):障礙點(diǎn)(i,j):當(dāng)前點(diǎn)Ri,

9、jLi,jHi,j=1算法算法2 2 遞推關(guān)系遞推關(guān)系 如果(i1,j)不是障礙點(diǎn)，那么，如圖所示，(i,j)對(duì)應(yīng)的懸線長(zhǎng)度為(i-1,j)對(duì)應(yīng)的懸線長(zhǎng)度1。 即 Hi,jHi-1,j+1(i-1,j):非障礙點(diǎn)(i,j):當(dāng)前點(diǎn)某個(gè)障礙算法算法2 2 遞推關(guān)系遞推關(guān)系 如果(i1,j)不是障礙點(diǎn)，那么，如圖所示，(i,j)對(duì)應(yīng)的懸線左右能移動(dòng)的位置要在(i-1,j)的基礎(chǔ)上變化。 Li-1,jLi,j=max (i-1,j)左邊第一個(gè)障礙點(diǎn)的位置 (i,j):當(dāng)前點(diǎn)某個(gè)障礙Li-1,jLi,j(i-1,j)算法算法2 2 遞推關(guān)系遞推關(guān)系同理，也可以得到Ri,j的遞推式 Ri-1,j Ri,

10、j=min (i-1,j)右邊第一個(gè)障礙點(diǎn)的位置 Li,jRi,jHi,j點(diǎn)(i,j)算法算法2 2 優(yōu)劣分析優(yōu)劣分析 算法2的時(shí)間復(fù)雜度為O(NM)，空間復(fù)雜度為O(S)。 優(yōu)點(diǎn)： 復(fù)雜度與障礙點(diǎn)個(gè)數(shù)沒有直接關(guān)系。 缺點(diǎn)：障礙點(diǎn)少時(shí)處理較復(fù)雜，不如算法1兩個(gè)不同的算法兩個(gè)不同的算法推廣推廣1 1 最大權(quán)值子矩形問題最大權(quán)值子矩形問題 最大權(quán)值子矩形問題模型：在一個(gè)帶權(quán)（正權(quán)）矩形中有一些障礙點(diǎn)，找出一個(gè)不包含障礙點(diǎn) 的最大權(quán)值子矩形。分析：在一個(gè)正權(quán)值的矩形中的最大權(quán)值子矩形一定是極大子矩形。所以，問題實(shí)際上可以依據(jù)極大化的思想，利用前面的方法解決。推廣推廣2 2 最大子正方形問題最大子正方

11、形問題 最大子正方形問題模型：在一個(gè)矩形中存在S個(gè)障礙點(diǎn)，要 求找出最大的不包含障礙點(diǎn)的正方 形。分析：在一個(gè)有障礙點(diǎn)的矩形中的最大有效子正方形一定是一個(gè)極大有效子正方形。推廣推廣2 2 最大子正方形問題最大子正方形問題 極大子正方形的性質(zhì)： 每一個(gè)極大子正方形都至少被一個(gè)極大子矩形包含，且這個(gè)極大子正方形一定有兩條不相鄰的邊與包含它的極大子矩形的邊重合。 推廣推廣2 2 最大子正方形問題最大子正方形問題 解決方法:通過枚舉每一個(gè)極大子矩形找出所有的極大子正方形。 每個(gè)極大子矩形對(duì)應(yīng)的極大子正方形可能有多個(gè)，但大小都一樣。推廣推廣2 2 最大子正方形問題最大子正方形問題 解決方法:通過枚舉每一個(gè)極大子矩形找出所有的極大