算法合集之淺談用極大化思想解決最大子矩形問題-資料下載頁
2025-01-09 19:42本頁面
【正文】 5】：每一個極大子正方形都至少被一個極大子矩形包含。且這個極大子正方形一定有兩條不相鄰的邊與這個包含它的極大子矩形的邊重合。 根據(jù)【定理 5】 ,我們只需要枚舉所有的極大子矩形，并檢查它所包含的極大子正方形（一個極大子矩形包含的極大子正方形都是一樣大的）是否是最大的就可以了。這樣，問題的實質(zhì)和前面所說的最大子矩形問題是一樣的，同樣的，所采用的算法也是一樣的。 王知昆 第 9 頁 IOI2022 國家集訓(xùn)隊論文 因為算法 1 和算法 2 都枚舉出了所有的極大子矩形，因此，算法 1 和算法 2 都可以用在本題上。具體的 處理方法如下：對于每一個枚舉出的極大子矩形，如圖所示，如果它的邊長為 a、 b，那么它包含的極大子正方形的邊長即為 min(a,b)。 考慮到 N 和 T 的大小不同，所以不同的算法會有不同的效果。下面分析兩種算法應(yīng)用在本題上的優(yōu)略。 對于第一種算法，時間復(fù)雜度為O(T2)，對于第二種算法，時間復(fù)雜度為O(N2)。因為 NT，所以從時間復(fù)雜度的角度看，第二種算法要比第一種算法好。考慮到兩個算法的空間復(fù)雜度都可以承受，所以選擇第二種算法較好些。 以下是第一種和第二種算法編程實現(xiàn)后在 USACO Training Program Gateway 上的運行時間。可以看出，在數(shù)據(jù)較大時，算法 2 的效率比算法 1高。 算法 1： Test 1: Test 2: Test 3: Test 4: Test 5: Test 6: Test 7: Test 8: Test 9: Test 10: Test 11: Test 12: Test 13: Test 14: Test 15: 算法 2： Test 1: Test 2: Test 3: Test 4: Test 5: Test 6: Test 7: Test 8: Test 9: Test 10: Test 11: Test 12: Test 13: Test 14: Test 15: 以上，利用極大化思想和前面設(shè)計的兩個算法，通過轉(zhuǎn)換模型，解決了三個具有一定代表性的例題。解題的關(guān)鍵就是如何利用極大化思想進(jìn)行模型轉(zhuǎn)換和如何選擇算法。 五、小結(jié) 王知昆 第 10 頁 IOI2022 國家集訓(xùn)隊論文 設(shè)計算法要從問題的基本特征入手，找出解題的突破口。本文介紹了兩種適用于大部分最大子矩形問題及相關(guān)變型問題 的算法，它們設(shè)計的突破口就是利用了極大化思想，找到了枚舉極大子矩形這種方法。 在效率上，兩種算法對于不同的情況各有千秋。一個是針對障礙點來設(shè)計的，因此復(fù)雜度與障礙點有關(guān)；另一個是針對整個矩形來設(shè)計的，因此復(fù)雜度與矩形的面積有關(guān)。雖然兩個算法看起來有著巨大的差別，但他們的本質(zhì)是相通的，都是利用極大化思想，從枚舉所有的極大有效子矩形入手，找出解決問題的方法。 需要注意的是，在解決實際問題是僅靠套用一些現(xiàn)有算法是不夠的，還需要對問題進(jìn)行全面、透徹的分析 ,找出解題的突破口。 此外，如果采用極 大化思想，前面提到的兩種算法的復(fù)雜度已經(jīng)不能再降低了，因為極大有效子矩形的個數(shù)就是 O(NM)或 O(S2)的。如果采用其他算法，理論上是有可能進(jìn)一步提高算法效率，降低復(fù)雜度的。 七、 附錄： 幾個例題的原題。 見 論文附件 .doc 例題的程序。 見 論文附件 .doc 說明：所有程序均在 Free Pascal IDE for Dos, Version 編譯運行 參考書目 信息學(xué)奧林匹克 競賽指導(dǎo) 1997～ 1998競賽試題解析 吳文虎 王建德 著 IOI99 中國集訓(xùn)隊優(yōu)秀論文集 信息學(xué)奧林匹克（季刊） 《金牌之路 競賽輔導(dǎo)》 江文哉主編 陜西師范大學(xué)出版社出版
試題試卷相關(guān)推薦
鄂ICP備17016276號-1