算法分析與設(shè)計—貪心算法論(編輯修改稿)
2025-07-10 10:51 本頁面
【文章內(nèi)容簡介】 少額外的內(nèi)存。一般二次方級的存儲要浪費額外的空間，而且那些空間經(jīng)常得不出正解。但是，使用貪心算法時，這些空間可以幫助算法更容易實現(xiàn)且更快執(zhí)行。如果有正確貪心性質(zhì)存在，那么一定要采用。因為它容易編寫，容易調(diào)試，速度極快，并且節(jié)約空間。幾乎可以說，此時它是所有算法中最好的。但是應(yīng)該注意，貪心算法有兩大難點： （ 1）如何貪心 怎樣用一個小規(guī)模的解構(gòu)造更大規(guī)模的解呢 ?總體上，這與問題本身有關(guān)。但是大部分都是有規(guī)律的。正因為貪心有如此性質(zhì)，它才能比其他算法快。 具有應(yīng)當(dāng)采用貪心算法的問題，當(dāng)“貪心序列”中的每項互異且當(dāng)問題沒有重疊性時，看起來總能通過貪心算法取得（近似）最優(yōu)解的?；蛘撸傆幸环N直覺在引導(dǎo)我們對一些問題采用貪心算法。其中“找零錢”這個問題就是一個例子。題中給出的硬幣面值事實上具有特殊性，如果面值發(fā)生變化，可能貪心算法就不能返回最優(yōu)解了。但是，值得指出的是，當(dāng)一個問題具有多個最優(yōu)解時，貪心算法并不能求出所有最優(yōu)解。另外，我們經(jīng)過實踐發(fā)現(xiàn)，單純的貪心算法是順序處理問題的；而且每個結(jié)果是可 以在處理完一個數(shù)據(jù)后即時輸出的。 （ 2）貪心的正確性 要證明貪心性質(zhì)的正確性，才是貪心算法的真正挑戰(zhàn)，因為并不是每次局部最優(yōu)解都會與整體最優(yōu)解之間有聯(lián)系，往往靠貪心算法生成的解不是最優(yōu)解。這樣，貪心性質(zhì)的證明就成了貪心算法正確的關(guān)鍵。對某些問題貪心性質(zhì)也許是錯的，即使它在大部分?jǐn)?shù)據(jù)中都是可行的，但還必須考慮到所有可能出現(xiàn)的特殊情況，并證明該貪心性質(zhì)在這些特殊情況中仍然正確。而這樣容易陷入證明不正確貪心性質(zhì)的泥塘中無法自拔，因為貪心算法的適用范圍并不大，而且有一部分極難證明，若是沒有把握，最好不要冒險，還有其 他算法會比它要保險。 貪心算法的理論基礎(chǔ) 貪心策略是最接近人類認(rèn)知思維的一種解題策略。但是，越是顯而易見的方法往往越難以證明。下面我們就來介紹貪心策略的理論 — 擬陣。 “擬陣”理論是一種能夠確定貪心策略何時能夠產(chǎn)生最優(yōu)解的理論，雖然這套理論還很不完善，但在求解最優(yōu)化問題時發(fā)揮著越來越重要的作用。 擬陣 M定義為滿足下面 3個條件的有序?qū)Γ?S， I）： （ 1） S 是非空有限集； （ 2） I 是 S的一類具有遺傳性質(zhì)的獨立子集族，即若 B∈ I，則 B 是 S 的獨立子集，且 B 的任意子集也都是 S的獨立子集?？占楸貫?I的成員； （ 3） I 滿足交換性質(zhì)，即若 A∈ I， B∈ I 且 |A||B|，則存在某一元素 x∈ BA，使得 A∪ {x}∈ I。 定理 擬陣 M中所有極大獨立子集具有相同大小。 引理 （擬陣的貪心選擇性質(zhì)）設(shè) M=（ S， I）是具有權(quán)函數(shù) M 的帶權(quán)擬陣，且 S 中元素依權(quán)值從大到小排列，又設(shè) x∈ S是 S中第一個使得 {x}是獨立子集元素，則存在 S 的最優(yōu)子集 A 使得 x∈ A。 引理 設(shè) M=(S， I)是擬陣。若 S 中元素 x 不是空集￠的一個可擴元素，則 x也不可能是 S 中任一獨立子集 A 的可擴展元素。 引理 （擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì)）設(shè) x 是求帶權(quán)擬陣 M=（ S， I）的最優(yōu)子集的貪心算法 Greedy 所選擇的 S 中的第一個元素。那么，原問題可簡化為求帶權(quán)擬陣 M39。=（ S39。， I39。）的最優(yōu)子集問題，其中 S39。={y|y∈ S且 {x， y}∈ I} I39。={B|B? S{x}且 B∪ {x}∈ I} M39。的權(quán)函數(shù)是 M的權(quán)函數(shù)在 S39。上的限制（稱 M39。為 M 關(guān)于元素 x的收縮）。 定理 （帶權(quán)擬陣貪心算法的正確性）高 M=（ S， I）是具有權(quán)函數(shù) W 的帶權(quán)擬陣，算法 Greedy 返回 M的最優(yōu)子集。 適宜于用貪心策 略來求解的許多問題都可以歸結(jié)為在加權(quán)擬陣中找一個具有最大權(quán)值的獨立子集的問題，即給定一個加權(quán)擬陣 M=（ S， I），若能找出
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1