離散化

離散化

轉自&＃xff08;Matrix67 &＃xff09;

對於「 什麼是離散化」 &＃xff0c;搜索帖子你會發現有各種說法&＃xff0c;比如「 排序後處理」 、「 對坐標的近似處理」等等。哪個是對的呢&＃xff1f;哪個都對。關鍵在於&＃xff0c;這需要一些例子和不少的講解才能完全解釋清楚。

離散相對於連續而言&＃xff0c;連續通俗來講指平滑的過渡&＃xff0c;比如1 和2 之間可以有無數的數&＃xff0c;可以無限分割。而離散指數據的不連續性&＃xff0c;比如1 &＃xff0c;2 &＃xff0c;3 。。。。這樣畫出的曲線是不連續的。

離散數學是數據結構的基礎&＃xff0c;其實是一切馮氏結構計算機的理論基礎。

離散化是程序設計中一個非常常用的技巧&＃xff0c;它可以有效的降低時間復雜度。其基本思想就是在眾多可能的情況中「 只考慮我需要用的值」 。下面我將用三個例子說明&＃xff0c;如何運用離散化改進一個低效的&＃xff0c;甚至根本不可能實現的算法

《算法藝術與信息學競賽》中的計算幾何部分&＃xff0c;黃亮舉了一個經典的例子&＃xff0c;我認為很適合用來介紹離散化思想。題目意思很簡單&＃xff0c;給定平面上n 個點的坐標&＃xff0c;求能夠覆蓋所有這些點的最小矩形面積。這個問題難就難在&＃xff0c;這個矩形可以傾斜放置&＃xff08;邊不必平行於坐標軸&＃xff09;。

這裡的傾斜放置很不好處理&＃xff0c;因為我們不知道這個矩形最終會傾斜多少度。假設我們知道這個矩形的傾角是α &＃xff0c;那麼答案就很簡單了&＃xff1a;矩形面積最小時四條邊一定都 挨著某個點。也就是說&＃xff0c;四條邊的斜率已經都知道了的話&＃xff0c;只需要讓這些邊從外面不斷逼近這個點集直到碰到了某個點。你不必知道這個具體應該怎麼實現&＃xff0c;只需要理解這可以通過某種方法計算出來&＃xff0c;畢竟我們的重點在下面的過程。

我們的算法很顯然了&＃xff1a;枚舉矩形的傾角&＃xff0c;對於每一個傾角&＃xff0c;我們都能計算出最小的矩形面積&＃xff0c;最後取一個最小值。

這個算法是否是正確的呢&＃xff1f;我們不能說它是否正確&＃xff0c;因為它根本不可能實現。矩形的傾角是一個實數&＃xff0c;它有無數種可能&＃xff0c;你永遠不可能枚舉每一種情況。我們說&＃xff0c;矩形的傾角是一個「 連續的」 變量&＃xff0c;它是我們無法枚舉這個傾角的根本原因。我們需要一種方法&＃xff0c;把這個「 連續的」 變量變成一個一個的值&＃xff0c;變成一個「 離散的」 變量。這個過程也就是所謂的離散化。

我們可以證明&＃xff0c;最小面積的矩形不但要求四條邊上都有一個點&＃xff0c;而且還要求至少一條邊上有兩個或兩個以上的點。試 想&＃xff0c;如果每條邊上都只有一個點&＃xff0c;則我們總可以把這個矩形旋轉一點使得這個矩形變「 松」 &＃xff0c;從而有余地得到更小的矩形。於是我們發現&＃xff0c;矩形的某條邊的斜率必然與某兩點的連線相同。如果我們計算出了所有過兩點的直線的傾角&＃xff0c;那麼α 的取值只有可能是這些傾角或它減去90 度後的角&＃xff08;直線按「/」 方向傾斜時&＃xff09;這麼C(n,2) 種。我們說&＃xff0c;這個「 傾角」 已經被我們 「 離散化」 了。雖然這個算法仍然有優化的余地&＃xff0c;但此時我們已經達到了本文開頭所說的目的。

對於某些坐標雖然已經是整數&＃xff08;已經是離散的了&＃xff09;但范圍極大的問題&＃xff0c;我們也可以用離散化的思想縮小這個規模。最近搞模擬賽Vijos 似乎火了一把&＃xff0c;我就拿兩道Vijos 的題開刀。
VOJ1056(http://www.vijos.cn /Problem_Show.asp?id&＃61;1056) 永遠是離散化的經典問題。大意是給定平面上的n 個矩形&＃xff08;坐標為整數&＃xff0c;矩形與矩形之間可能有重疊的部分&＃xff09;&＃xff0c;求其覆蓋的總面積。平常的想法就是開一個與二維坐 標規模相當的二維Boolean 數組模擬矩形的「 覆蓋」 &＃xff08;把矩形所在的位置填上True &＃xff09;。可惜這個想法在這裡有些問題&＃xff0c;因為這個題目中坐標范圍相當大 &＃xff08;坐標范圍為-10^8 到10^8 之間的整數&＃xff09;。但我們發現&＃xff0c;矩形的數量n<&＃61;100 遠遠小於坐標范圍。每個矩形會在橫縱坐標上各「 使用」 兩個值&＃xff0c; 100 個矩形的坐標也不過用了-10^8 到10^8 之間的200 個值。也就是說&＃xff0c;實際有用的值其實只有這麼幾個。這些值將作為新的坐標值重新劃分整個平 面&＃xff0c;省去中間的若干坐標值沒有影響。我們可以將坐標范圍「 離散化」 到1 到200 之間的數&＃xff0c;於是一個200*200 的二維數組就足夠了。實現方法正如本文開 頭所說的「 排序後處理」 。對橫坐標&＃xff08;或縱坐標&＃xff09;進行一次排序並映射為1 到2n 的整數&＃xff0c;同時記錄新坐標的每兩個相鄰坐標之間在離散化前實際的距離是多少。這 道題同樣有優化的余地。

最後簡單講一下計算幾何以外的一個運用實例&＃xff08;實質仍然是坐標的離散&＃xff09;。才考的VOJ1238(http://www.vijos.cn/Problem_Show.asp?id&＃61;1238) 中&＃xff0c;標程開了一個與時間范圍一樣大的數組 來儲存時間段的位置。這種方法在空間上來看十分危險。一旦時間取值范圍再大一點&＃xff0c;盲目的空間開銷將導致Memory Limit Exceeded 。我們完全可以采用離散化避免這種情況。我們對所有給出的時間坐標進行一次排序&＃xff0c;然後同樣用時間段的開始點和結束點來計算每個時刻的游戲數&＃xff0c;只是一次性加的經驗值數將乘以排序後這兩個相鄰時間點的實際差。這樣&＃xff0c;一個1..n 的數組就足夠了。