算法分析-貪心算法

貪心算法

GreedyAlgorithm學(xué)習(xí)要點(diǎn)理解貪心算法的概念掌握貪心算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）貪心選擇性質(zhì)理解貪心算法與動(dòng)態(tài)規(guī)劃算法的差異通過應(yīng)用范例學(xué)習(xí)貪心設(shè)計(jì)策略（1）活動(dòng)安排問題；（2）最優(yōu)裝載問題；（3）哈夫曼編碼；（4）單源最短路徑；（5）最小生成樹；（6）多機(jī)調(diào)度問題。怎樣找硬幣？？？設(shè)有4種硬幣，它們的面值分別為1角，5分，2分和1分?，F(xiàn)在要找給某顧客3角7分錢。此時(shí)我們會(huì)不假思索地拿出3個(gè)1角，1個(gè)5分和1個(gè)2分的硬幣交給顧客，這種找法與其他找法相比，拿出的硬幣的個(gè)數(shù)時(shí)最少的。這個(gè)找硬幣的算法就是貪心算法：總是作出在當(dāng)前看來是最好的選擇，即貪心算法并不是從總體最優(yōu)上加以考慮，它所作的選擇只是在某種意義上的局部最優(yōu)選擇。找硬幣問題本身最優(yōu)原理成立，可以用動(dòng)態(tài)規(guī)劃方法求解，但用貪心算法更簡單，直接且解題效率更高。這利用了問題本身的特性。

找硬幣算法：首先選出一個(gè)面值不超過3角7分的最大硬幣（1角）然后從3角7分中減去1角，剩余2角7分再選出一個(gè)不超過2角7分的最大硬幣（另一個(gè)1角），…，直到找足3角7分。怎樣找硬幣？？？又設(shè)有3種硬幣，它們的面值分別為1角1分，5分和1分?，F(xiàn)在要找給某顧客1角5分錢？貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似！

找硬幣貪心算法：給顧客1個(gè)一角一分的硬幣和4個(gè)一分的硬幣。這是最優(yōu)嗎？3個(gè)五分硬幣顯然是最好的找法。一般地，有這樣一類問題：它有n個(gè)輸入，而它的解就由這n個(gè)輸入的某個(gè)子集組成，只是這個(gè)子集必須滿足某些事先給定的條件。把那些必須滿足的條件稱為約束條件；而把滿足約束條件的子集稱為該問題的可行解。為了衡量可行解的優(yōu)劣，事先給出了一定的標(biāo)準(zhǔn)。一般以函數(shù)形式給出，稱為目標(biāo)函數(shù)。那些使目標(biāo)函數(shù)取極值（極大或極?。┑目尚薪?，稱為最優(yōu)解。貪心法也是一個(gè)多步?jīng)Q策法。每一步選擇都使得能構(gòu)成問題的一個(gè)可行解，同時(shí)使目標(biāo)函數(shù)的值增加最快（求max）或增加最小（如求min），這種選擇過程是以某些最優(yōu)量度為根據(jù)，而最優(yōu)化量度有時(shí)可以是目標(biāo)函數(shù)本身，也可以是別的量度。最優(yōu)化度量的選擇是貪心算法的關(guān)鍵。貪心算法一般地，有這樣一類問題：它有n個(gè)輸入，而它的解就由這n個(gè)輸入的某個(gè)子集組成，只是這個(gè)子集必須滿足某些事先給定的條件。把那些必須滿足的條件稱為約束條件；而把滿足約束條件的子集稱為該問題的可行解。為了衡量可行解的優(yōu)劣，事先給出了一定的標(biāo)準(zhǔn)。一般以函數(shù)形式給出，稱為目標(biāo)函數(shù)。那些使目標(biāo)函數(shù)取極值（極大或極小）的可行解，稱為最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。貪心算法貪心算法的基本思路基本思路1.建立數(shù)學(xué)模型來描述問題。2.把求解的問題分成若干個(gè)子問題。3.對每一子問題求解，得到子問題的局部最優(yōu)解。4.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。實(shí)現(xiàn)該算法的過程：從問題的某一初始解出發(fā)；while能朝給定總目標(biāo)前進(jìn)一步do求出可行解的一個(gè)解元素；由所有解元素組合成問題的一個(gè)可行解；活動(dòng)安排問題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動(dòng)。貪心算法提供了一個(gè)簡單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。活動(dòng)安排問題

設(shè)有n個(gè)活動(dòng)的集合E={1,2,…,n}，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si<fi。如果選擇了活動(dòng)i，則它在半開時(shí)間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時(shí)，活動(dòng)i與活動(dòng)j相容?；顒?dòng)安排問題template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}活動(dòng)安排問題的貪心算法GreedySelector:各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列

活動(dòng)安排問題

由于輸入的活動(dòng)以其完成時(shí)間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。活動(dòng)安排問題

例：設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314活動(dòng)安排問題

算法greedySelector的計(jì)算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。活動(dòng)安排問題若被檢查的活動(dòng)i的開始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加入集合A中。貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動(dòng)安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明?；顒?dòng)安排問題貪心算法的基本要素可以用貪心算法求解的問題的一般特征:

對于一個(gè)具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個(gè)問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。

對于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。貪心算法的基本要素

當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。最優(yōu)子結(jié)構(gòu)性質(zhì)貪心算法的基本要素

貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類算法的一個(gè)共同點(diǎn)。但是，對于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解?是否能用動(dòng)態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個(gè)經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。貪心算法與動(dòng)態(tài)規(guī)劃算法的差異貪心算法的基本要素0-1背包問題：

給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?

在選擇裝入背包的物品時(shí)，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。背包問題背包問題：

與0-1背包問題類似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。

背包問題

首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 具體算法可描述如下：

用貪心算法解背包問題的基本步驟：背包問題voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}

算法knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。背包問題0-1背包問題：有三種物品，背包容量為50公斤。物品1重10公斤，價(jià)值60元，物品2重20公斤，價(jià)值100元，物品3重30公斤，價(jià)值120元。因此，物品1每公斤價(jià)值6元，物品2每公斤價(jià)值5元，物品3每公斤價(jià)值4元。若依貪心選擇策略，應(yīng)首先物品1裝入背包，然而從圖b的各種情況可以看出，最優(yōu)選擇方案是選擇物品2和3裝入背包。首選物品1的2種方案都不是最優(yōu)的。對于背包問題，貪心選擇最終可得到最優(yōu)解，其選擇方案如圖c所示

對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。背包問題背包問題有一個(gè)背包，背包容量是M=150。有7個(gè)物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過總?cè)萘俊Ｎ锲稟BCDEFG重量35306050401025價(jià)值10403050354030分析：目標(biāo)函數(shù)：∑pi最大約束條件是裝入的物品總重量不超過背包容量：∑wi<=M(M=150)（1）根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？（2）每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？（3）每次選取單位重量價(jià)值最大的物品，成為解本題的策略。?值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經(jīng)過證明成立后，它就是一種高效的算法。背包問題貪心算法還是很常見的算法之一，這是由于它簡單易行，構(gòu)造貪心策略不是很困難?？上У氖牵枰C明后才能真正運(yùn)用到題目的算法中。一般來說，貪心算法的證明圍繞著：整個(gè)問題的最優(yōu)解一定由在貪心策略中存在的子問題的最優(yōu)解得來的。對于例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：（1）貪心策略：選取價(jià)值最大者。反例：

W=30物品：ABC重量：281212價(jià)值：302020根據(jù)策略，首先選取物品A，接下來就無法再選取了，選取B、C哪個(gè)更好呢？背包問題（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。（3）貪心策略：選取單位重量價(jià)值最大的物品。反例：

W=30物品：ABC重量：282010價(jià)值：282010根據(jù)策略，三種物品單位重量價(jià)值一樣，程序無法依據(jù)現(xiàn)有策略作出判斷，如果選擇A，則答案錯(cuò)誤。背包問題

有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。最優(yōu)裝載最優(yōu)裝載1、算法描述 最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁。

template<classType>voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(inti=1;i<=n;i++) x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++) { x[t[i]]=1; c-=w[t[i]]; }}2、貪心選擇性質(zhì)

可以證明最優(yōu)裝載問題具有貪心選擇性質(zhì)。最優(yōu)裝載3、最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。 算法loading的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為O(nlogn)。

單源最短路徑問題描述給定一個(gè)帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)項(xiàng)點(diǎn)，稱為源。

現(xiàn)在我們要計(jì)算從源到所有其他各項(xiàng)點(diǎn)的最短路徑長度。這里的長度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。

其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。 初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對應(yīng)的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點(diǎn)u，將u添加到S中，同時(shí)對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長度。算法基本思想 Dijkstra算法是解單源最短路徑問題的貪心算法。單源最短路徑例：求右圖中u到其余各點(diǎn)的距離。解：由圖中得出初始值：L(v1)=1,L(v2)=3,L(v3)=∞,L(v4)=6,L(u)=0,T={u}1)選擇T集合外與u點(diǎn)相關(guān)連路徑最小一點(diǎn)v1,于是有

T={u,v1}根據(jù)v1修改T外各點(diǎn)路徑因L(v1)+w(v1,v2)=1+1<L(v2)則L(v2)=2同理L(v3)==1+3=4，L(v4)=6（不改變）2）選擇T集合外路徑最小一點(diǎn)v2，于是有

T={u,v1,v2}根據(jù)v2修改T外各點(diǎn)路徑因L(v2)+w(v2,v3)=2+1<L(v3)=4則L(v3)=3L(v4)=6（不改變）3）選擇T集合外路徑最小一點(diǎn)v3，于是有

T={u,v1,v2,v3}根據(jù)v3修改T外各點(diǎn)路徑L(v4)=3+2=54)得到最后一點(diǎn)v4,于是有T={u,v1,v2,v3,v4}

最后T=V,計(jì)算結(jié)束。U到各點(diǎn)的路離為：L(v1)=1,L(v2)=2,L(v3)=3,L(v5)=5

對右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過程列在下頁的表中。單源最短路徑迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060Dijkstra算法的迭代過程：單源最短路徑

對于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時(shí)間。算法的其余部分所需要時(shí)間不超過。2、算法的正確性和計(jì)算復(fù)雜性 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì) (3)計(jì)算復(fù)雜性單源最短路徑

設(shè)G=(V,E)是無向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹，則稱G’為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費(fèi)。在G的所有生成樹中，耗費(fèi)最小的生成樹稱為G的最小生成樹。 網(wǎng)絡(luò)的最小生成樹在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。最小生成樹1、最小生成樹性質(zhì)

用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹的有效算法。介紹的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這2個(gè)算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì)。

最小生成樹2、Prim算法

設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。 構(gòu)造G的最小生成樹的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且c[i][j]最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過程一直進(jìn)行到S=V時(shí)為止。 在這個(gè)過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。Prim算法 利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T始終包含G的某棵最小生成樹中的邊。因此，在算法結(jié)束時(shí)，T中的所有邊構(gòu)成G的一棵最小生成樹。

如對于右圖中的帶權(quán)圖，按Prim算法選取邊的過程如下頁圖所示。Prim算法

在生成樹的構(gòu)造過程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集U和尚未落在生成樹上的頂點(diǎn)集V-U，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。UV-UPrim算法abcdegf195141827168213127abegf14d8c351621Prim算法算法的核心：選擇向集合U中加入的頂點(diǎn)時(shí)，要選擇到U具有最短邊的頂點(diǎn)1、對任何一個(gè)頂點(diǎn)v，如果它有多個(gè)鄰接U的邊，則需要找出最短的邊作為鄰接到U的邊2、從所有的V–U頂點(diǎn)中，找出具有最短邊的頂點(diǎn)，將它加入U(xiǎn)Prim算法

在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出滿足條件iS,jV-S，且權(quán)c[i][j]最小的邊(i,j)。實(shí)現(xiàn)這個(gè)目的的較簡單的辦法是設(shè)置2個(gè)數(shù)組closest和lowcost。 在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closest[j］)，最后將j添加到S中，并對closest和lowcost作必要的修改。 用這個(gè)辦法實(shí)現(xiàn)的Prim算法所需的計(jì)算時(shí)間為最小生成樹3、Kruskal算法

Kruskal算法構(gòu)造G的最小生成樹的基本思想是，首先將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個(gè)不同的連通分支：當(dāng)查看到第k條邊(v,w)時(shí)，如果端點(diǎn)v和w分別是當(dāng)前2個(gè)不同的連通分支T1和T2中的頂點(diǎn)時(shí)，就用邊(v,w)將T1和T2連接成一個(gè)連通分支，然后繼續(xù)查看第k+1條邊；如果端點(diǎn)v和w在當(dāng)前的同一個(gè)連通分支中，就直接再查看第k+1條邊。這個(gè)過程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。

Kruskal算法 如對前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹上的邊如下圖所示。Kruskal算法 關(guān)于集合的一些基本運(yùn)算可用于實(shí)現(xiàn)Kruskal算法。 按權(quán)的遞增順序查看等價(jià)于對優(yōu)先隊(duì)列執(zhí)行removeMin運(yùn)算。可以用堆實(shí)現(xiàn)這個(gè)優(yōu)先隊(duì)列。 對一個(gè)由連通分支組成的集合不斷進(jìn)行修改，需要用到抽象數(shù)據(jù)類型并查集UnionFind所支持的基本運(yùn)算。 當(dāng)圖的邊數(shù)為e時(shí)，Kruskal算法所需的計(jì)算時(shí)間是。當(dāng)時(shí)，Kruskal算法比Prim算法差，但當(dāng)時(shí)，Kruskal算法卻比Prim算法好得多。Kruskal算法

具體做法:先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。

考慮問題的出發(fā)點(diǎn):為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。Kruskal算法abcdegf3abcegfd21581416abcdegf195141827168213127Kruskal算法abcdegf195141827168213127連通網(wǎng)：n個(gè)城市和城市間可能的通信線路網(wǎng)的頂點(diǎn)：表示城市網(wǎng)的邊：表示兩個(gè)城市之間的線路網(wǎng)的邊上的權(quán)值：通信代價(jià)構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。常用算法：克魯斯卡爾算法、普里姆算法該問題等價(jià)于： 哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。1、前綴碼 對每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。哈夫曼編碼

編碼的前綴性質(zhì)可以使譯碼方法非常簡單。 表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)。 平均碼長定義為： 使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。

哈夫曼編碼2、構(gòu)造哈夫曼編碼

哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。 哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。 算法以|C|個(gè)葉結(jié)點(diǎn)開始，執(zhí)行|C|－1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹T。

哈夫曼編碼 在書上給出的算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊(duì)列Q。經(jīng)過n－1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹，即所要求的樹T。 算法huffmanTree用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列Q。初始化優(yōu)先隊(duì)列需要O(n)計(jì)算時(shí)間，由于最小堆的removeMin和put運(yùn)算均需O(logn)時(shí)間，n－1次的合并總共需要O(nlogn)計(jì)算時(shí)間。因此，關(guān)于n個(gè)字符的哈夫曼算法的計(jì)算時(shí)間為O(nlogn)。哈夫曼編碼3、哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

(1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì)哈夫曼編碼ABCHIDEFG75249WPL(T)=7×

2+5×

2+2×

3+4×

3+9×

2=60樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和表示

WPL(T)=wklk(對所有葉子結(jié)點(diǎn))nk=1哈夫曼編碼ABCHIDEFG74952WPL(T)=7×4+9×

4+5×

3+4×

2+2×

1=89

哈夫曼編碼1.根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn),其左、右子樹為空樹;哈夫曼編碼2.在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和;3.從F中刪去這兩棵樹，同時(shí)將剛生成的新樹加入到F中;4.重復(fù)(2)和(3)兩步，直至F中只含一棵樹為止。哈夫曼編碼練習(xí):已知權(quán)值W={5,6,2,9,8}95628769713852761)2)3)527哈夫曼編碼4)5)6713852715671328852715WPL=2×3+5×3+6×2+7×2+8×2=63次序哈夫曼編碼特點(diǎn)：1、有n個(gè)葉子結(jié)點(diǎn)2、沒有度為1的結(jié)點(diǎn)3、總的結(jié)點(diǎn)數(shù)為2n-14、形態(tài)不唯一哈夫曼編碼

利用哈夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。哈夫曼編碼A B C D E6 7 2 5 9例：假設(shè)有5個(gè)符號(hào)以及它們的頻率：求前綴編碼。哈夫曼編碼95271667132901010011000110010111前綴編碼1、建立赫夫曼樹2、對邊編號(hào)