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