算法合集之淺談用極大化思想解決最大子矩形問題-資料下載頁
2025-10-07 20:33本頁面
【正文】 度可以接受，編程實現(xiàn)簡單 ? 缺點：使用有一定的局限性，不適合障礙點較密集的情況。 ? 算法 2 ? 時間復(fù)雜度： O(NM) ? 空間復(fù)雜度： O(S) ? 優(yōu)點：復(fù)雜度與障礙點個數(shù)沒有直接關(guān)系。 ? 缺點：障礙點少時因為要離散化處理，實際復(fù)雜度較高。 推廣 1 最大權(quán)值子矩形問題 ? 最大權(quán)值子矩形問題 模型：在一個帶權(quán)（正權(quán)）矩形中有一 些障礙點，找出一個不包含障礙點 的最大權(quán)值子矩形。 ? 分析：在一個正權(quán)值的矩形中的最大權(quán)值子矩形一定是極大子矩形。所以，問題實際上可以依據(jù)極大化的思想，利用前面的方法解決。 推廣 2 最大子正方形問題 ? 最大子正方形問題 模型：在一個矩形中存在 S個障礙點，要 求找出最大的不包含障礙點的正方 形。 ? 分析： 在一個有障礙點的矩形中的最大有效子正方形一定是一個極大有效子正方形。 推廣 2 最大子正方形問題 ? 極大子正方形的性質(zhì)： 每一個極大子正方形都至少被一個極大子矩形包含，且這個極大子正方形一定有兩條不相鄰的邊與包含它的極大子矩形的邊重合。 推廣 2 最大子正方形問題 ? 解決方法 :通過枚舉每一個極大子矩形找出所有的極大子正方形。 ? 每個極大子矩形對應(yīng)的極大子正方形可能有多個，但大小都一樣。 推廣 2 最大子正方形問題 ? 解決方法 :通過枚舉每一個極大子矩形找出所有的極大子正方形。 ? 每個極大子矩形對應(yīng)的極大子正方形可能有多個，但大小都一樣。 推廣 2 最大子正方形問題 ? 解決方法 :通過枚舉每一個極大子矩形找出所有的極大子正方形。 ? 每個極大子矩形對應(yīng)的極大子正方形可能有多個，但大小都一樣。 …… 矩形類型變換 ? 類型 1 ? 矩形中的點都是兩條垂直線段的交點，有效子矩形可以在邊界包含障礙點。 ? 類型 2 ? 矩形中的點是單位方格，有效子矩形不能包含任何障礙點。 ? 處理方法與類型 1基本相同 要點回顧 極大化思想 最大子矩形問題 算法 2 算法 1 最大子正方形問題 最大權(quán)值子矩形問題
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1