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

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

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

3、場題意簡述題意簡述：（原題見論文附件）John要在矩形牛場中建造一個(gè)大型浴場，但是這個(gè)大型浴場不能包含任何一個(gè)奶牛的產(chǎn)奶點(diǎn)，但產(chǎn)奶點(diǎn)可以出在浴場的邊界上。John的牛場和規(guī)劃的浴場都是矩形，浴場要完全位于牛場之內(nèi)，并且浴場的輪廓要與牛場的輪廓平行或者重合。要求所求浴場的面積盡可能大。參數(shù)約定：產(chǎn)奶點(diǎn)的個(gè)數(shù)S不超過5000牛場的范圍NM不超過3000030000。二、二、定義和說明定義和說明首先明確一些概念。1、定義有效子矩形有效子矩形為

4、內(nèi)部不包含任何障礙點(diǎn)且邊界與坐標(biāo)軸平行的子矩形。如圖所示，第一個(gè)是有效子矩形（盡管邊界上有障礙點(diǎn)），第二個(gè)不是有效子矩形（因?yàn)閮?nèi)部含有障礙點(diǎn)）。王知昆第3頁IOI2003國家集訓(xùn)隊(duì)論文定理2的正確性很顯然，如果一個(gè)有效子矩形的某一條邊既沒有覆蓋一個(gè)障礙點(diǎn)，又沒有與整個(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)生大量的無效子矩形?？紤]只枚舉左右邊界的情況。對(duì)于已經(jīng)確定的左右邊界，可以將所有處在這個(gè)邊界內(nèi)的點(diǎn)按從上到下排序，如圖1中所示，每一格就代表一個(gè)有效子矩形。這樣做時(shí)間復(fù)雜度為O(S3)。由于確保每次得到的矩形都是合法的，所以枚舉量比前一種算法小了很多。但

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