【文章內(nèi)容簡介】 擇性質(zhì)，必須證明每一步所做的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。做了貪心選擇后，原問題簡化為規(guī)模更小的類似子問題。然后，用數(shù)學(xué)歸納法證明，通過每一步做貪心選擇，最終可得到問題的整體最優(yōu)解。其中，證明貪心選擇后的問題簡化為規(guī)模更小的類似子問題的關(guān)鍵在于利用該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。運用貪心策略在每一次轉(zhuǎn)化時都取得了最優(yōu)解。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法或動態(tài)規(guī)劃算法求解的關(guān)鍵特征。貪心算法的每一次操作都對結(jié)果產(chǎn)生直接影響，而動態(tài)規(guī)劃則不是。貪心算法對每個子問題的解決方案都做出選擇，不能回退；動態(tài)規(guī)劃則會根據(jù)以前的選擇結(jié)果對當(dāng)前進(jìn)行選擇，有回退功能。動態(tài)規(guī)劃主要運用于二維或三維問題，而貪心一般是一維問題。貪心算法的最大特點就是快，通常是線性二次式，不需要多少額外的內(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)解的?；蛘?，總有一種直覺在引導(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)知思維的一種解題策略。但是，越是顯而易見的方法往往越難以證明。下面我們就來介紹貪心策略的理論—擬陣?！皵M陣”理論是一種能夠確定貪心策略何時能夠產(chǎn)生最優(yōu)解的理論，雖然這套理論還很不完善，但在求解最優(yōu)化問題時發(fā)揮著越來越重要的作用。擬陣M定義為滿足下面3個條件的有序?qū)Γ⊿，I）：（1）S是非空有限集；（2）I是S的一類具有遺傳性質(zhì)的獨立子集族，即若B∈I，則B是S的獨立子集，且B的任意子集也都是S的獨立子集?？占楸貫镮的成員；（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|BS{x}且B∪{x}∈I}M39。的權(quán)函數(shù)是M的權(quán)函數(shù)在S39。上的限制（稱M39。為M關(guān)于元素x的收縮）。（帶權(quán)擬陣貪心算法的正確性）高M(jìn)=（S，I）是具有權(quán)函數(shù)W的帶權(quán)擬陣，算法Greedy返回M的最優(yōu)子集。適宜于用貪心策略來求解的許多問題都可以歸結(jié)為在加權(quán)擬陣中找一個具有最大權(quán)值的獨立子集的問題，即給定一個加權(quán)擬陣M=（S，I），若能找出一個獨立且具有最大可能權(quán)值的子集A，且A不被M中比它更大的獨立子集所包含，那么A為最優(yōu)子集，也是一個最大的獨立子集。我們認(rèn)為，針對絕大多數(shù)的信息學(xué)問題，只要它具備了“擬陣”的結(jié)構(gòu)，便可用貪心策略求解。擬陣?yán)碚搶τ谖覀兣袛嘭澬牟呗允欠襁m用于某一復(fù)雜問題是十分有效的。 貪心算法存在的問題（1）不能保證求得的最后解是最佳的。由于貪心策略總是采用從局部看來是最優(yōu)的選擇，因此并不從整體上加以考慮；（2）貪心算法只能用來求某些最大或最小解的問題；（3）貪心算法只能確定某些問題的可行性范圍。第3章 經(jīng)典問題解決及其優(yōu)缺點 哈夫曼編碼 問題描述哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。 編碼原理對每一個字符規(guī)定一個0，1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。編碼的前綴性質(zhì)可以使譯碼方法非常簡單。由于任一字符的代碼都不是其他字符代碼的前綴，從編碼文件中不斷取出代表某一字符的前綴碼，轉(zhuǎn)換為原字符，即可逐個譯出文件中的所有字符?？梢杂枚鏄渥鳛榍熬Y編碼的數(shù)據(jù)結(jié)構(gòu)。在表示前綴碼的二叉樹中，樹葉代表給定的字符，并將每個字符的前綴碼看做是從樹根到代表該字符的樹葉的一條道路。代碼中每一位的0或1分別作為指示某結(jié)點到左兒子或右兒子的“路標(biāo)”。 貪心算法策略設(shè)C是編碼字符集，C中字符c的頻率為f(c)。又設(shè)x和y是C中具有最小頻率的兩個字符，則存在C的最優(yōu)前綴碼使x和y具有相同碼長且僅最后一位編碼不同。證明：設(shè)二叉樹T表示C的任意一個最優(yōu)前綴碼。下面證明可以對T做適當(dāng)修改后得到一棵新的二叉樹T，使得在新樹中，x和y是最深葉子且為兄弟。同時新樹T表示的前綴碼也是C的最優(yōu)前綴碼。如果能做到這一點，則x和y在T表示的最優(yōu)前綴碼中就具有相同的碼長且僅最后一位編碼不同。設(shè)b和c是二叉樹T的最深葉子且為兄弟。不失一般性，可設(shè)f(b)≤f(c)，f(x)≤f(y)。由于x和y是C中具有最小頻率的兩個字符，故f(x)≤f(b)，f(y)≤f(c)。首先在樹T中交換葉子b和x的位置得到樹T39。，然后在樹T39。中再交換葉子c和y的位置。得到樹T。xybcbyxcyccbTT’‘T‘Fig. Counterchange the Codingtree T 編碼樹T的變換由此可知，樹T和T’表示的前綴碼的平均碼長之差為B(T)B(T’)= =f(x)dT(x)+f(b)dT(b)f(x)dT’(x)f(b)dT’(b) =f(x)dT(x)+f(b)dT(b)f(x)dT(b)f(b)dT(x) =(f(b)f(x))(dT(b)dT(x))≥0最后一個不等式是因為f(b)f(x)和dT(b)dT(x)均為非負(fù)。類似地，可以證明在T’中交換y與c的位置也不增加平均碼長，即B(T’)B(T)也是非負(fù)的。由此可知，B(T)≤B(T’)≤B(T)。另一方面，由于T所表示的前綴碼是最優(yōu)的，故B(T)≤B(T)。因此，B(T)=B(T)，即T表示的前綴碼也是最優(yōu)前綴碼，且x和y具有最長的碼長，同時僅最后一位編碼不同。 最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)T是表示字符集C的一個最優(yōu)前綴碼的完全二叉樹。C中字符c的出現(xiàn)頻率為f(c)。設(shè)x和y是樹T中的兩個葉子且為兄弟，z是它們的父親。若將z看做是具有頻率f(z)=f(x)+f(y)的字符，則樹T’=T{x，y}表示字符集C’=C{x，y}∪{z}的一個最優(yōu)前綴碼。證明：首先證明T的平均碼長B(T)要用T’的平均碼長B(T’)來表示。事實上，對任意c∈C{x，y}有dT(c)=dT’(c)，故f(c)dT(c)=f(c)dT’(c)。另一方面，dT(x)=dT(y)=dT’(z)+1，故f(x)dT(x)+f(y)dT(y)=(f(x)+f(y))(dT’(z)+1) =f(x)+f(y)+f(z)dT’(z)由此即知，B(T)=B(T’)+f(x)+f(y)。若T’所表示的字符集C’的前綴碼不是最優(yōu)的，則有T表示的C’的前綴碼使得B(T)B(T’)。由于z被看做是C’中的一個字符，故z在T中是一樹葉。若將x和y加入樹T中作為z的兒子，則得到表示字符集C的前綴碼的二叉樹T39。，且有B（T39。）=B（T）+f(x)+f(y) B(T’)+f(x)+f(y) =B(T)這與T的最優(yōu)性矛盾。故T’所表示的C’的前綴碼是最優(yōu)的。由貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)立即可推出：哈夫曼算法是正確的，即HuffmanTree產(chǎn)生C的一棵最優(yōu)前綴編碼樹。 計算復(fù)雜性算法HuffmanTree用最小堆實現(xiàn)優(yōu)先隊列Q。初始化優(yōu)先隊列需要O（n）計算時間，由于最小堆的DeleteMin和Insert運算均需O(logn)時間，n1次的合并總共需要O(nlogn)計算時間。因此，關(guān)于n個字符的哈夫曼算法的計算時間為O(nlogn)。(Dijkstra算法) 問題描述給定一個帶權(quán)有向圖G=(V，E)，其中每條邊的權(quán)是一個非負(fù)實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在我們要計算從源到所有其他各頂點的最短路徑長度。這里的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。 編碼原理設(shè)置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當(dāng)且僅當(dāng)從源到該頂點的最短路徑長度已知。初始時，S中僅含有源。設(shè)u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個頂點所對應(yīng)的最短特殊路徑長度。Dijkstra算法每次從VS中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。 貪心算法策略Dijkstra算法是應(yīng)用貪心算法設(shè)計策略的一個典型例子。它所作的貪心選擇是從VS中選擇具有最短特殊路徑的頂點u，從而確定從源到u的最短路徑長度dist[u]。這種貪心選擇為什么能導(dǎo)致最優(yōu)解呢？換句話說，為什么從源到u沒有更短的其他路徑呢？事實上，如果存在一條從源到u且長度比dist[u]更短的路，設(shè)這條路初次走出S之外到達(dá)的頂點為x∈VS，然后徘徊于S內(nèi)外若干次，最后離開S到達(dá)u。 yux源S The shortcut which Form fountainhead to U 從源到u的最短路徑在這條路徑上，分別記d(v，x)，d(x，u)和d(v，u)為頂點v到頂點x，頂點x到頂點u和頂點v到頂點u的路長，那么，dist[x]≤d(v，x)，d(v，x)+d(x，u)=d(v，u)dist[u]利用邊權(quán)的非負(fù)性，可知d(x，u)≥0，從而推得dist[x]dist[u]。此為矛盾，這就證明了dist[u]是從源到頂點u的最短路徑長度。要完成Dijkstra算法正確性的證明，還必須證明最優(yōu)子結(jié)構(gòu)性質(zhì)，即算法中確定的dist[u]確實是當(dāng)前從源到頂點u的最短特殊路徑長度。因此，只要考察算法在添加u到S中后，dist[u]的值所起的變化。將添加u之前的S稱為老的S。當(dāng)添加了u之后，可能出現(xiàn)一條到頂點i的新的特殊路。如果這條新特殊路是先經(jīng)過老的S到達(dá)頂點u，然后從u經(jīng)一條邊直接到達(dá)頂點i，則這種路的最短的長度是dist[u]+c[u][i]。這時，如果dist[u]+c[u][i]dist[i]，則算法中用dist[u]+c[u][i]作為dist[i]的新值。如果這條新特殊路徑經(jīng)過老的S到達(dá)u后，不是從u經(jīng)一條邊直接到達(dá)i。xviu老S源Fig. The specialties path isn’t the best shortest 非最短的特殊路徑回到老的S中某個項點x，最后才到達(dá)頂點i，那么由于x在老的S中，因此x比u先加入S，如圖中從源到x的路的長度比從源到u，再從u到x的路的長度小。于是當(dāng)前dist[i]的值小于圖中從源經(jīng)x到i的路的長度，也小于圖中從源經(jīng)u和x，最后到達(dá)i的路的長度。因此，在算法中不必考慮這種路。由此即知，不論算法中dist[u]的值是否有變化，它總是關(guān)于當(dāng)前頂點集S到頂點u的最短特殊路徑長度。 計算復(fù)雜性對于一個具有n個頂點和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個圖，那么Dijkstra算法的主循環(huán)體需要O(n)時間。這個循環(huán)需要執(zhí)行n1次，所以完成循環(huán)需要O(n2)時間。算法的其余部分所需要時間不超過O(n2)。(Prim算法、Kruskal算法)問題描述：設(shè)圖G=(V，E)是一簡單連通圖，|V|=n，|E|=m，每條邊ei都給以權(quán)wi，wi假定是邊ei的長度（其他的也可以），i=1，2，3，…，m。求圖G的總長度最短的樹。 Kruskal算法編碼原理：首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接兩個不同的連通分支：當(dāng)查看到第k條邊(v，w)時，如果端點v和w分別是當(dāng)前兩個不同的連通分支T1和T2中的頂點時，就用邊(v，w)將T1和