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