算法合集之淺談用極大化思想解決最大子矩形問題(編輯修改稿)
2024-11-12 20:33 本頁面
【文章內(nèi)容簡介】 次。 算法 1 遺漏的情況 ? 另一類是左邊界與整個矩形的左邊界重合，且右邊界也與整個矩形的右邊界重合的情況。 ? 解決方法：預(yù)處理時增加特殊判斷。 算法 1 優(yōu)劣分析 ? 算法 1的時間復(fù)雜度為 O(S2)，空間復(fù)雜度為 O(S)。 ? 優(yōu)點：利用了極大化思想，復(fù)雜度可以接受，編程實現(xiàn)簡單。 ? 缺點：使用有一定的局限性，不適合障礙點較密集的情況。 算法 2 設(shè)計的目的和思路 ? 因為算法 1有使用的局限性，所以我們需要一種在障礙點很密集的時候仍能奏效的算法。 ? 設(shè)計一種復(fù)雜度依賴于整個矩形面積的算法 說明：如果整個矩形面積很大，可以通過離散化處理來優(yōu)化。 算法 2 懸線 ? 有效豎線：除了兩個端點外，不覆蓋任何障礙點的豎直線段。 ? 懸線：上端點覆蓋了一個障礙點或達到整個矩形上端的有效豎線。 ? 圖中所示的線段均為懸線。 算法 2 懸線 ? 每個懸線都與它底部的點一一對應(yīng)。 矩形中的每一個點（矩形頂部的點除外）都對應(yīng)了一個懸線。 ? 懸線的個數(shù)＝ (N－ 1) M 算法 2 懸線與極大子矩形 ?如果把一個極大子矩形按 x坐標不同切割成多個與 y軸平行的線段，則其中至少存在一個懸線。 …… Y X 算法 2 懸線與極大子矩形 ? 如果把一個懸線向左右兩個方向盡可能移動，就能得到一個矩形，不妨稱為這個懸線對應(yīng)的矩形。 ? 懸線對應(yīng)的矩形不一定是極大子矩形，因為下邊界可能還可以向下擴展。 設(shè)計算法 ?原理：所有懸線對應(yīng)矩形的集合一定包含了極大子矩形的集合。 ?通過枚舉所有的懸線，找出所有的極大子矩形。 ?算法規(guī)模： 懸線個數(shù)＝ (N－ 1) M 極大子矩形個數(shù) ≤懸線個數(shù) 算法 2 關(guān)鍵點 ?解決問題的關(guān)鍵： 對每個懸線的處理時間。 ?解決方法： 充分利用前面得到的信息。 算法 2 處理方法 ? 具體方法： 設(shè) H[i,j]為點 (i,j)對應(yīng)的懸線的長度。 L[i,j]為點 (i,j)對應(yīng)的懸線向左最多能夠移動到的 位置 。 R[i,j]為點 (
教學課件相關(guān)推薦
鄂ICP備17016276號-1