Posted on 2010-10-15 11:15
MiYu 閱讀(2042)
評論(0) 編輯 收藏 引用 所屬分類:
ACM_資料
Matrix67原創(chuàng) Trackback: http://www.matrix67.com/blog/archives/108
如果說今年這時候OIBH問得最多的問題是二分圖，那么去年這時候問得最多的算是離散化了。對于“什么是離散化”，搜索帖子你會發(fā)現(xiàn)有各種說法，比如“排序后處理”、“對坐標(biāo)的近似處理”等等。哪個是對的呢？哪個都對。關(guān)鍵在于，這需要一些例子和不少的講解才能完全解釋清楚。
離散化是程序設(shè)計中一個非常常用的技巧，它可以有效的降低時間復(fù)雜度。其基本思想就是在眾多可能的情況中“只考慮我需要用的值”。下面我將用三個例子說明，如何運用離散化改進一個低效的，甚至根本不可能實現(xiàn)的算法。
《算法藝術(shù)與信息學(xué)競賽》中的計算幾何部分，黃亮舉了一個經(jīng)典的例子，我認為很適合用來介紹離散化思想。這個問題是UVA10173(http://acm.uva.es/p/v101/10173.html)，題目意思很簡單，給定平面上n個點的坐標(biāo)，求能夠覆蓋所有這些點的最小矩形面積。這個問題難就難在，這個矩形可以傾斜放置（邊不必平行于坐標(biāo)軸）。
這里的傾斜放置很不好處理，因為我們不知道這個矩形最終會傾斜多少度。假設(shè)我們知道這個矩形的傾角是α，那么答案就很簡單了：矩形面積最小時四條邊一定都挨著某個點。也就是說，四條邊的斜率已經(jīng)都知道了的話，只需要讓這些邊從外面不斷逼近這個點集直到碰到了某個點。你不必知道這個具體應(yīng)該怎么實現(xiàn)，只需要理解這可以通過某種方法計算出來，畢竟我們的重點在下面的過程。
我們的算法很顯然了：枚舉矩形的傾角，對于每一個傾角，我們都能計算出最小的矩形面積，最后取一個最小值。
這個算法是否是正確的呢？我們不能說它是否正確，因為它根本不可能實現(xiàn)。矩形的傾角是一個實數(shù)，它有無數(shù)種可能，你永遠不可能枚舉每一種情況。我們說，矩形的傾角是一個“連續(xù)的”變量，它是我們無法枚舉這個傾角的根本原因。我們需要一種方法，把這個“連續(xù)的”變量變成一個一個的值，變成一個“離散的”變量。這個過程也就是所謂的離散化。
我們可以證明，最小面積的矩形不但要求四條邊上都有一個點，而且還要求至少一條邊上有兩個或兩個以上的點。試想，如果每條邊上都只有一個點，則我們總可以把這個矩形旋轉(zhuǎn)一點使得這個矩形變“松”，從而有余地得到更小的矩形。于是我們發(fā)現(xiàn)，矩形的某條邊的斜率必然與某兩點的連線相同。如果我們計算出了所有過兩點的直線的傾角，那么α的取值只有可能是這些傾角或它減去90度后的角（直線按“\”方向傾斜時）這么C(n,2)種。我們說，這個“傾角”已經(jīng)被我們 “離散化”了。雖然這個算法仍然有優(yōu)化的余地，但此時我們已經(jīng)達到了本文開頭所說的目的。
對于某些坐標(biāo)雖然已經(jīng)是整數(shù)（已經(jīng)是離散的了）但范圍極大的問題，我們也可以用離散化的思想縮小這個規(guī)模。最近搞模擬賽Vijos似乎火了一把，我就拿兩道Vijos的題開刀。
VOJ1056(http://www.vijos.cn/Problem_Show.asp?id=1056) 永遠是離散化的經(jīng)典問題。大意是給定平面上的n個矩形（坐標(biāo)為整數(shù)，矩形與矩形之間可能有重疊的部分），求其覆蓋的總面積。平常的想法就是開一個與二維坐標(biāo)規(guī)模相當(dāng)?shù)亩SBoolean數(shù)組模擬矩形的“覆蓋”（把矩形所在的位置填上True）。可惜這個想法在這里有些問題，因為這個題目中坐標(biāo)范圍相當(dāng)大（坐標(biāo)范圍為-10^8到10^8之間的整數(shù)）。但我們發(fā)現(xiàn)，矩形的數(shù)量n<=100遠遠小于坐標(biāo)范圍。每個矩形會在橫縱坐標(biāo)上各“使用”兩個值， 100個矩形的坐標(biāo)也不過用了-10^8到10^8之間的200個值。也就是說，實際有用的值其實只有這么幾個。這些值將作為新的坐標(biāo)值重新劃分整個平面，省去中間的若干坐標(biāo)值沒有影響。我們可以將坐標(biāo)范圍“離散化”到1到200之間的數(shù)，于是一個200*200的二維數(shù)組就足夠了。實現(xiàn)方法正如本文開頭所說的“排序后處理”。對橫坐標(biāo)（或縱坐標(biāo)）進行一次排序并映射為1到2n的整數(shù)，同時記錄新坐標(biāo)的每兩個相鄰坐標(biāo)之間在離散化前實際的距離是多少。這道題同樣有優(yōu)化的余地。
最后簡單講一下計算幾何以外的一個運用實例（實質(zhì)仍然是坐標(biāo)的離散）。才考的VOJ1238(http://www.vijos.cn/Problem_Show.asp?id=1238)中，標(biāo)程開了一個與時間范圍一樣大的數(shù)組來儲存時間段的位置。這種方法在空間上來看十分危險。一旦時間取值范圍再大一點，盲目的空間開銷將導(dǎo)致Memory Limit Exceeded。我們完全可以采用離散化避免這種情況。我們對所有給出的時間坐標(biāo)進行一次排序，然后同樣用時間段的開始點和結(jié)束點來計算每個時刻的游戲數(shù)，只是一次性加的經(jīng)驗值數(shù)將乘以排序后這兩個相鄰時間點的實際差。這樣，一個1..n的數(shù)組就足夠了。
離散化的應(yīng)用相當(dāng)廣泛，以后你會看到還有很多其它的用途。
2007.04.05補充：
VOJ1056那個例子看來還是有人不明白。
我發(fā)一張示意圖，注意左邊的10*7的數(shù)組是如何等價地轉(zhuǎn)化為右邊兩個4*4的數(shù)組的
