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

1、王知昆第1頁(yè)IOI2003國(guó)家集訓(xùn)隊(duì)論文淺談?dòng)脴O大化思想解決最大子矩形問(wèn)題淺談?dòng)脴O大化思想解決最大子矩形問(wèn)題福州第三中學(xué)王知昆【摘要】【摘要】本文針對(duì)一類近期經(jīng)常出現(xiàn)的有關(guān)最大（或最優(yōu)）子矩形及相關(guān)變本文針對(duì)一類近期經(jīng)常出現(xiàn)的有關(guān)最大（或最優(yōu)）子矩形及相關(guān)變形問(wèn)題，介紹了極大化思想在這類問(wèn)題中的應(yīng)用。分析了兩個(gè)具有一定形問(wèn)題，介紹了極大化思想在這類問(wèn)題中的應(yīng)用。分析了兩個(gè)具有一定通用性的算法。并通過(guò)一些例題講述了這些算法選擇和使用時(shí)的一

2、些技通用性的算法。并通過(guò)一些例題講述了這些算法選擇和使用時(shí)的一些技巧。巧?！娟P(guān)鍵字】【關(guān)鍵字】矩形，障礙點(diǎn)，極大子矩形矩形，障礙點(diǎn)，極大子矩形【正文】【正文】一、一、問(wèn)題問(wèn)題最大子矩形問(wèn)題：在一個(gè)給定的矩形網(wǎng)格中有一些障礙點(diǎn)，要找出網(wǎng)格內(nèi)部不包含任何障礙點(diǎn)，且邊界與坐標(biāo)軸平行的最大子矩形。這是近期經(jīng)常出現(xiàn)的問(wèn)題，例如冬令營(yíng)2002的《奶牛浴場(chǎng)》，就屬于最大子矩形問(wèn)題。WinterWinterCamp2002Camp2002奶牛浴場(chǎng)奶牛浴

3、場(chǎng)題意簡(jiǎn)述題意簡(jiǎn)述：（原題見(jiàn)論文附件）John要在矩形牛場(chǎng)中建造一個(gè)大型浴場(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不超過(guò)5000牛場(chǎng)的范圍NM不超過(guò)3000030000。二、二、定義和說(shuō)明定義和說(shuō)明首先明確一些概念。1、定義有效子矩形有效子矩形為

4、內(nèi)部不包含任何障礙點(diǎn)且邊界與坐標(biāo)軸平行的子矩形。如圖所示，第一個(gè)是有效子矩形（盡管邊界上有障礙點(diǎn)），第二個(gè)不是有效子矩形（因?yàn)閮?nèi)部含有障礙點(diǎn)）。王知昆第3頁(yè)IOI2003國(guó)家集訓(xùn)隊(duì)論文定理2的正確性很顯然，如果一個(gè)有效子矩形的某一條邊既沒(méi)有覆蓋一個(gè)障礙點(diǎn)，又沒(méi)有與整個(gè)矩形的邊界重合，那么肯定存在一個(gè)包含它的有效子矩形。根據(jù)定理2，我們可以得到一個(gè)枚舉極大子矩形的算法。為了處理方便，首先在障礙點(diǎn)的集合中加上整個(gè)矩形四角上的點(diǎn)。每次枚舉子矩

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

6、需要注意的是，這樣做枚舉的子矩形雖然是合法的，然而不一定是極大的。所以這個(gè)算法還有優(yōu)化的余地。通過(guò)對(duì)這個(gè)算法不足之處的優(yōu)化，我們可以得到一個(gè)高效的算法。回顧上面的算法，我們不難發(fā)現(xiàn)，所枚舉的矩形的上下邊界都覆蓋了障礙點(diǎn)或者與整個(gè)矩形的邊界重合，問(wèn)題就在于左右邊界上。只有那些左右邊界也覆蓋了障礙點(diǎn)或者與整個(gè)矩形的邊界重合的有效子矩形才是我們需要考察的極大子矩形，所以前面的算法做了不少“無(wú)用功”。怎么減少“無(wú)用功”呢，這里介紹一種算法（算法