算法設(shè)計(jì)與分析 課件 許瑾晨 第六章 貪心算法

信息工程大學(xué)算法設(shè)計(jì)與分析貪心法國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版僅有動(dòng)態(tài)規(guī)劃是不夠的動(dòng)態(tài)規(guī)劃是對(duì)分治思想的一種改善，它在發(fā)現(xiàn)分解出來(lái)的子問(wèn)題有重疊時(shí)，保存子問(wèn)題的結(jié)果避免重復(fù)計(jì)算，從而提升了算法的效率。但避免重復(fù)計(jì)算并不是最高明的策略。

動(dòng)態(tài)規(guī)劃的特點(diǎn)是在每次做選擇前，將所有可能的情況進(jìn)行計(jì)算，在此基礎(chǔ)上選擇能夠達(dá)到最優(yōu)的選項(xiàng)。

本章學(xué)習(xí)的貪心算法策略：不考慮所有可能情況，只是做出當(dāng)前看來(lái)是最好的選擇！引例找零錢(qián)問(wèn)題原理和方法兩個(gè)重要性質(zhì)最優(yōu)子結(jié)構(gòu)貪心選擇貪心法正確性證明典型應(yīng)用部分背包活動(dòng)安排過(guò)河問(wèn)題哈夫曼編碼最小生成樹(shù)多機(jī)調(diào)度信息工程大學(xué)算法設(shè)計(jì)與分析貪心法—引例—找零錢(qián)問(wèn)題國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版假設(shè)要找給顧客6.3元，現(xiàn)在你手頭有面值為2.5元、1元、5角和1角的硬幣若干，試問(wèn)如何找錢(qián)使得所找的硬幣總數(shù)最少？策略：優(yōu)先使用面值大的硬幣

2個(gè)2.5元的硬幣1個(gè)1元的硬幣3個(gè)1角的硬幣與其它找法相比，這種找法拿出來(lái)的硬幣個(gè)數(shù)最少。目標(biāo)：找出的硬幣個(gè)數(shù)最少策略：優(yōu)先選用大面值硬幣思考：該策略總是可以得到最優(yōu)解嗎？貪心法假設(shè)要找給某顧客1.5元，現(xiàn)在你手頭有面值為1.1元、5角和1角的硬幣若干，試問(wèn)如何找錢(qián)使得所找的硬幣總數(shù)最少？策略：優(yōu)先使用面值大的硬幣。

1個(gè)1.1元的硬幣

4個(gè)1角的硬幣最優(yōu)解：

3個(gè)5角的硬幣貪心策略不一定總是能夠得到最優(yōu)解！貪心策略從局部最優(yōu)出發(fā)，每次做一個(gè)選擇，問(wèn)題規(guī)模就減小一些，重復(fù)該過(guò)程，直到問(wèn)題解決。貪心策略不一定總是能夠得到最優(yōu)解。信息工程大學(xué)算法設(shè)計(jì)與分析貪心法—基本原理國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版求解最優(yōu)化問(wèn)題的過(guò)程包含一系列步驟每一步都有多種選擇貪心法做出在當(dāng)前看來(lái)最好的選擇希望通過(guò)局部最優(yōu)選擇達(dá)到全局最優(yōu)

貪心算法總是做出當(dāng)前最好的選擇，不是從整體上考慮問(wèn)題的最優(yōu)性，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇，所以有時(shí)貪心算法的解不一定是整體最優(yōu)解。對(duì)于一個(gè)給定的問(wèn)題，通常有多種貪心選擇策略，但不是每種策略都可以得到最優(yōu)解。因此，選擇能產(chǎn)生問(wèn)題最優(yōu)解的貪心選擇策略是使用貪心法的核心問(wèn)題。有些問(wèn)題的貪心選擇策略比較直觀，有些問(wèn)題則需要深入分析。適合用貪心法求解的問(wèn)題一般具有兩個(gè)重要性質(zhì)：貪心選擇性質(zhì)（Greedy-choiceproperty）每步所做的貪心選擇最終可求得問(wèn)題的最優(yōu)解最優(yōu)子結(jié)構(gòu)性質(zhì)（Optimalsubstructure）問(wèn)題的最優(yōu)解包含子問(wèn)題的最優(yōu)解1.證明所求解的問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2.證明所求解的問(wèn)題具有貪心選擇性質(zhì)（證明每一步所做的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解）。反之，只需要舉出一個(gè)反例，就可以說(shuō)明貪心法不正確。貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是它們的共同點(diǎn)。

但對(duì)于具有最優(yōu)子結(jié)構(gòu)的問(wèn)題：選用貪心法還是動(dòng)態(tài)規(guī)劃求解?能用動(dòng)態(tài)規(guī)劃求解的問(wèn)題是否也能用貪心法求解?

給定n個(gè)物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為c。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?物品i要么全部裝入要么不裝。0-1背包問(wèn)題：與0-1背包問(wèn)題不同的是，在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分xi，不一定要全部裝入背包，0≤xi≤1。部分背包問(wèn)題：選擇題。你覺(jué)得以下哪種貪心選擇策略可以得到部分背包問(wèn)題的最優(yōu)解？A.重量輕的物品優(yōu)先裝入B.價(jià)值大的物品優(yōu)先裝入C.單位重量?jī)r(jià)值大的物品優(yōu)先裝入D.以上都不對(duì)部分背包問(wèn)題的貪心選擇策略有：1.重量輕優(yōu)先2.價(jià)值大優(yōu)先3.單位重量?jī)r(jià)值大優(yōu)先反例：n=2，c=5，w=(2,5)，v=(2,10)，優(yōu)先裝入物品1，再裝入物品2的一部分，得到價(jià)值總和為8；而把物品2全部裝入背包得到價(jià)值10是最優(yōu)解。反例：n=2，c=5，w=(2,5)，v=(6,10)，優(yōu)先裝入物品2，得到價(jià)值10；而先全部裝入物品1再裝入物品2的一部分，得到價(jià)值12是最優(yōu)解。錯(cuò)誤錯(cuò)誤該策略綜合考慮到物品重量和價(jià)值兩個(gè)因素，可以得到最優(yōu)解。正確對(duì)物品按單位重量?jī)r(jià)值vi/wi從大到小排序；根據(jù)貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包；若背包內(nèi)的物品總重量未超過(guò)c，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包；依此策略進(jìn)行下去，直到背包裝滿為止。貪心法求解部分背包問(wèn)題的步驟：貪心法求解部分背包問(wèn)題的代碼：voidKnapsack(intn,floatc,float*v,float*w,float*x){knap_sort(n,v,w);/*按單位重量?jī)r(jià)值從大到小排序*/for(i=1;i<=n;i++)x[i]=0;floatleft=c;/*逐一判斷每件物品*/for(i=1;i<=n;i++){if(w[i]>left)break;x[i]=1;left-=w[i];}if(i<=n)x[i]=left/w[i];/*可能有部分裝入的物品*/}時(shí)間復(fù)雜度為O(nlogn)例：c=7,(w1,w2,w3)=(3,4,5),(v1,v2,v3)=(5,6,10)。貪心法得到的最大價(jià)值為10，裝入物品3。實(shí)際最大價(jià)值為11，裝入物品1和2。貪心法不能正確求解0-1背包問(wèn)題。原因：無(wú)法保證最終能將背包裝滿，部分閑置的背包空間使背包的單位空間的價(jià)值降低。在考慮0-1背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再做出最好的選擇。由此就出現(xiàn)許多互相重疊的子問(wèn)題。0-1背包問(wèn)題可用動(dòng)態(tài)規(guī)劃求解。貪心法不能正確求解0-1背包問(wèn)題。動(dòng)態(tài)規(guī)劃貪心共同點(diǎn)最優(yōu)子結(jié)構(gòu)性質(zhì)不同點(diǎn)重疊子問(wèn)題貪心選擇性質(zhì)求解思路對(duì)所有選擇比較后決定最優(yōu)的只考慮一種選擇，因而更高效解題過(guò)程通常采取自底而上，從小問(wèn)題推出大問(wèn)題從大問(wèn)題逐步求解，不斷減少問(wèn)題規(guī)模，直至結(jié)束代碼結(jié)構(gòu)通常是多重循環(huán)通常是排序后一遍掃描貪心法簡(jiǎn)單、高效。選擇正確的貪心選擇策略是關(guān)鍵。兩個(gè)重要性質(zhì)：最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)。貪心算法是否產(chǎn)生最優(yōu)解，需嚴(yán)格證明；反之，要證明某種貪心選擇策略是錯(cuò)誤的，只需要找出一個(gè)反例即可。信息工程大學(xué)算法設(shè)計(jì)與分析貪心法—活動(dòng)安排問(wèn)題國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版活動(dòng)安排問(wèn)題：

設(shè)有n個(gè)活動(dòng)的集合S={1,2,…,n}，其中每個(gè)活動(dòng)都要求使用同一資源，如教室、會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這個(gè)資源。si，fi分別為活動(dòng)i的開(kāi)始和結(jié)束時(shí)間，且si<fi

?；顒?dòng)i與j相容

si

fj或sjfi。求：最大的兩兩相容的活動(dòng)集A。

問(wèn)題的解需要滿足以下條件：是n個(gè)活動(dòng)的一個(gè)子集任何兩個(gè)活動(dòng)都是相容的活動(dòng)個(gè)數(shù)最多活動(dòng)的屬性：開(kāi)始時(shí)間、結(jié)束時(shí)間、持續(xù)時(shí)間可能的貪心策略：盡早開(kāi)始，優(yōu)先安排開(kāi)始時(shí)間早的活動(dòng)占用時(shí)間短，優(yōu)先安排持續(xù)時(shí)間短的活動(dòng)使剩余時(shí)間更多，優(yōu)先安排結(jié)束時(shí)間早的活動(dòng)思考：活動(dòng)安排問(wèn)題可以用貪心法求解嗎？選擇題。你覺(jué)得以下哪種貪心選擇策略可以得到活動(dòng)安排問(wèn)題的最優(yōu)解？A.優(yōu)先安排開(kāi)始時(shí)間早的活動(dòng)B.優(yōu)先安排持續(xù)時(shí)間短的活動(dòng)C.優(yōu)先安排結(jié)束時(shí)間早的活動(dòng)D.以上都不對(duì)策略1：優(yōu)先安排開(kāi)始時(shí)間早的活動(dòng)錯(cuò)誤該策略得到的解：活動(dòng)1最優(yōu)解：活動(dòng)2、活動(dòng)3策略2：

優(yōu)先安排持續(xù)時(shí)間短的活動(dòng)錯(cuò)誤該策略得到的解：活動(dòng)4、5最優(yōu)解：活動(dòng)1、2、3策略3：優(yōu)先安排結(jié)束時(shí)間早的活動(dòng)問(wèn)題：該策略對(duì)所有實(shí)例都能得到最優(yōu)解嗎？該策略對(duì)兩個(gè)實(shí)例都得到了最優(yōu)解。

時(shí)間復(fù)雜度為O(nlogn)S={1,2,…,n}是活動(dòng)集，且f1

…

fn

。

定理：算法GreedySelect執(zhí)行到第k步，選擇k項(xiàng)活動(dòng)i1=1,i2,…,ik，那么存在最優(yōu)解A包含i1=1,i2,…,ik。證明：歸納基礎(chǔ)：k=1,存在最優(yōu)解包含活動(dòng)1。任取最優(yōu)解A,A中的活動(dòng)按結(jié)束時(shí)間遞增排列。如果A的第一個(gè)活動(dòng)為j，j

1,由于f1

fj，則有A′=(A

{j})

{1}，且A′也是最優(yōu)解，并含有活動(dòng)1。

j…A1…A’歸納步驟：假設(shè)命題對(duì)k為真，證明對(duì)k+1也為真。算法執(zhí)行到第k步，選擇了活動(dòng)i1=1,i2,…,ik，根據(jù)歸納假設(shè)存在最優(yōu)解A包含i1=1,i2,…,ik。

最優(yōu)解A中剩下的活動(dòng)子集B來(lái)自集合S′={i|i

S,si

fk}，且A={i1,i2,…,ik}B。其中B是S′的最優(yōu)解。若不然,設(shè)S′的最優(yōu)解為B*,B*的活動(dòng)比B多，那么B*

{1,i2,…,ik}是S的最優(yōu)解，且比A的活動(dòng)多,與A的最優(yōu)性矛盾。待選集合S′1,i2,…,ik不相容活動(dòng)集BAB*B={ik+1,…}?將S′看做一個(gè)子問(wèn)題，根據(jù)歸納基礎(chǔ)，存在S′的最優(yōu)解B′含有S′中的第一個(gè)活動(dòng)，即ik+1,且|B′|=|B|,于是也是原問(wèn)題的最優(yōu)解.待選集合S′1,i2,…,ikBB’ik+1活動(dòng)安排問(wèn)題的主要特征：使用一個(gè)共享資源，安排盡可能多的活動(dòng)。在日常生活中這樣的應(yīng)用場(chǎng)景很多，比如給一個(gè)教室安排盡可能多的課程、一個(gè)會(huì)場(chǎng)安排盡量多的會(huì)議等。信息工程大學(xué)算法設(shè)計(jì)與分析貪心法—過(guò)河問(wèn)題國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版一群人在河的右岸，想通過(guò)唯一的一根獨(dú)木橋走到河的左岸，過(guò)橋時(shí)必須借助燈光照明。獨(dú)木橋最多能承受兩個(gè)人，由于只有一盞燈，因此過(guò)橋時(shí)間等于較慢的那個(gè)人單獨(dú)過(guò)橋所需要的時(shí)間。給定N個(gè)人(2<=N<1000)人單獨(dú)過(guò)橋需要的時(shí)間，

請(qǐng)計(jì)算最少需要多少時(shí)間，他們才能全部到達(dá)河左岸。每個(gè)人的過(guò)河時(shí)間從小到大存儲(chǔ)在t[i]中，i=0~n-1。按照問(wèn)題規(guī)模從小到大進(jìn)行分析：當(dāng)n=1,2時(shí)，直接過(guò)河；當(dāng)n=3時(shí)，需要兩趟；n=3時(shí)，用時(shí)：t[0]+t[1]+t[2]1.最快的和最慢的(t[2])2.最快的返回(t[0])3.最快的和次慢的(t[1])按照問(wèn)題規(guī)模從小到大進(jìn)行分析：當(dāng)n=1,2,3時(shí)，容易求解；當(dāng)n較大時(shí)，把若干人送到對(duì)岸，再有人把燈拿回來(lái)，就可以轉(zhuǎn)換為規(guī)模更小的過(guò)河問(wèn)題?；谟脮r(shí)最少的要求，選擇過(guò)河時(shí)間較快的人把燈拿回來(lái)。按照問(wèn)題規(guī)模從小到大進(jìn)行分析。當(dāng)n=1,2,3時(shí)，容易求解；當(dāng)n≥4時(shí)，將過(guò)河所需時(shí)間最多的兩個(gè)人送到河對(duì)岸，有兩種方式：方式一：用最快的逐人送用時(shí)：2*t[0]+t[n-1]+t[n-2]方式二：最慢和次慢的一起過(guò)河用時(shí)：t[0]+2*t[1]+t[n-1]1.最快的和最慢的(t[n-1])2.最快的返回(t[0])3.最快的和次慢的(t[n-2])4.最快的返回(t[0])1.最快的和次快的(t[1])2.最快的返回(t[0])3.最慢的和次慢的(t[n-1])4.次快的返回(t[1])貪心法求解過(guò)河問(wèn)題的步驟：按從小到大的順序?qū)^(guò)河時(shí)間排序，存儲(chǔ)到數(shù)組t中；當(dāng)n>=4時(shí)，比較方式一和方式二的時(shí)間，選擇用時(shí)少的（貪心選擇策略），同時(shí)n=n-2；重復(fù)步驟2，直到人數(shù)不足4時(shí)，直接求解。sort(t,t+num);/*對(duì)過(guò)河時(shí)間從小到大排序*/voidwork(intn)/*貪心法求解n個(gè)人的過(guò)河問(wèn)題*/{if(n==1){ans+=t[0];return;}if(n==2){ans+=t[1];return;}if(n==3){ans+=t[0]+t[1]+t[2];return;}if(n>=4){if((t[1]*2)>=(t[0]+t[n-2]))ans+=t[0]*2+t[n-2]+t[n-1];/*選擇方式一*/elseans+=t[1]*2+t[0]+t[n-1];

/*選擇方式二*/work(n-2);/*遞歸調(diào)用*/return;}}時(shí)間復(fù)雜度為O(nlogn)信息工程大學(xué)算法設(shè)計(jì)與分析貪心法—哈夫曼編碼國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版二進(jìn)制編碼問(wèn)題：

給定字符集D={d1,d2,...,dn}，字符出現(xiàn)的頻率為{w1,w2,…,wn}，要求為每個(gè)字符確定一種由0、1構(gòu)成的二進(jìn)制編碼方案，使得編碼后的文件長(zhǎng)度最短。字符編碼轉(zhuǎn)換01編碼譯碼轉(zhuǎn)換字符

編碼方案：等長(zhǎng)編碼存在的問(wèn)題：字符頻率不等時(shí)，得到的編碼總長(zhǎng)度可能不是最短的。非等長(zhǎng)編碼潛在的問(wèn)題：如00表示E，01表示T，0001表示W(wǎng)，收到的編碼是0001，那么這組編碼是W還是ET呢？無(wú)法區(qū)分!!原因是E的編碼和W的編碼的開(kāi)始部分（前綴）相同。2.非等長(zhǎng)編碼：采用非等長(zhǎng)的二進(jìn)制串表示。頻度高的字符采用較短的二進(jìn)制串表示，頻度低的字符采用較長(zhǎng)的二進(jìn)制串表示，從而達(dá)到縮短報(bào)文總長(zhǎng)的目的。前綴碼：任一字符的編碼都不是其它字符編碼的前綴。因此，對(duì)字符集進(jìn)行不等長(zhǎng)編碼，則要求這種不等長(zhǎng)編碼必須是前綴碼。判斷題。等長(zhǎng)編碼一定是前綴碼。A.正確B.錯(cuò)誤

戴維?哈夫曼提出了利用二叉樹(shù)構(gòu)造最優(yōu)前綴碼的方法。相應(yīng)的二叉樹(shù)稱為哈夫曼樹(shù)，對(duì)應(yīng)的編碼稱為哈夫曼編碼。設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度li與葉子結(jié)點(diǎn)權(quán)值wi的乘積的和稱為該二叉樹(shù)的帶權(quán)路徑長(zhǎng)度(WeightedPathLength，WPL)。

WPL最小的二叉樹(shù)稱為哈夫曼樹(shù)。字符出現(xiàn)的頻率根結(jié)點(diǎn)到字符結(jié)點(diǎn)的路徑長(zhǎng)度二進(jìn)制編碼問(wèn)題本質(zhì)上是構(gòu)造哈夫曼樹(shù)的問(wèn)題。基于出現(xiàn)頻率越高的字符、編碼長(zhǎng)度越短的貪心思想，哈夫曼提出了構(gòu)造哈夫曼樹(shù)的貪心法，優(yōu)先選擇頻率低的字符，以自下而上的方式構(gòu)造哈夫曼樹(shù)。哈夫曼樹(shù)的構(gòu)造過(guò)程：初始時(shí)，每個(gè)結(jié)點(diǎn)作為一棵樹(shù)，共有n棵樹(shù)；新建一個(gè)結(jié)點(diǎn)v，選擇具有最低頻率的兩個(gè)根結(jié)點(diǎn)作為結(jié)點(diǎn)v的左、右孩子，形成一棵樹(shù)，v的權(quán)值為其左、右孩子的權(quán)值之和；重復(fù)步驟2，直到只剩下一棵樹(shù)為止。選擇題。已知n個(gè)葉子結(jié)點(diǎn)，構(gòu)造哈夫曼樹(shù)需要執(zhí)行（）次合并操作（合并操作指步驟2）。A.nB.n-1C.以上都不對(duì)c:14b:15d:17a:38f:6e:101601第一步例子：a:38，b:15，c:14，d:17，f:6，e:10c:14b:15d:17a:38f:6e:10初始化c:14b:15d:17a:38f:6e:101601第二步2901c:14b:152901f:6e:101601d:1733a:3801620110001第五步c:14b:152901f:6e:101601d:1733a:38016201第四步c:14b:152901f:6e:101601d:1733a:3801第三步字符對(duì)應(yīng)的編碼：f：1100e：1101d：111c：100b：101a：0c:14b:152901f:6e:101601d:1733a:3801620110001選擇題。下圖所示的哈夫曼樹(shù)，密文“010110111111001101100111”對(duì)應(yīng)的明文是（）。A.abdffecdB.abbdfecdC.以上都不對(duì)Huffman(C)/*構(gòu)建哈夫曼樹(shù)*/輸入：C={x1,x2,…,xn}，n,

f(xi),i=1,2,…,n輸出：C’1.復(fù)制C到C’中，初始化C’中每個(gè)字符的左、右孩子為-1；2.Q

C’;/*用字符頻率集構(gòu)建小根堆*/3.for(i=1;i<=n-1;i++){4.z=Allocate-Node();/*生成新結(jié)點(diǎn)z加入C’中*/5.z.left=pop(Q);/*取出Q最小元為z的左兒子*/6.z.right=pop(Q);/*取出Q次小元為z的右兒子*/

7.f(z)=f(x)+f(y);8.push(Q,z);/*將z插入Q*/9.}10.returnC’;時(shí)間復(fù)雜度為O(nlogn)石子合并問(wèn)題：有n堆石子排成一排，依次編號(hào)為1~n。現(xiàn)要將石子兩兩合并為一堆，并將新的一堆石子數(shù)記為本次合并的代價(jià)。計(jì)算將n堆石子合并成一堆的最小代價(jià)。

結(jié)點(diǎn)i的權(quán)值wi根結(jié)點(diǎn)到結(jié)點(diǎn)i的路徑長(zhǎng)度li

*3465101518合并代價(jià)=10+15+18=43=3*1+4*3+6*3+5*2哈夫曼樹(shù)是WPL最小的二叉樹(shù)，不僅可以解決最優(yōu)前綴碼問(wèn)題，還可以解決很多類似的問(wèn)題。

應(yīng)用：生活中，把常用的物品放在容易拿到的地方。深入理解WPL的含義是關(guān)鍵。信息工程大學(xué)算法設(shè)計(jì)與分析貪心法--哈夫曼算法的正確性證明國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版定理：Huffman算法對(duì)任意規(guī)模為n（n2）的字符集C都能得到關(guān)于C的最優(yōu)前綴碼的二叉樹(shù)。

該定理的證明需要兩個(gè)引理。則T與T’的WPL之差為其中dT(i)為i在T中的層數(shù)（i到根的距離）,引理1成立。引理1：設(shè)C是字符集，

c

C,f(c)為頻率，x,y

C,f(x),f(y)頻率最小，那么存在最優(yōu)二元前綴碼使得x,y的編碼長(zhǎng)度相等，且僅在最后一位不同。f(x)

f(a)f(y)

f(b)a與x交換b與y交換

TT’yabxTbxyaT’證明:設(shè)T是C的最優(yōu)前綴樹(shù)，且a和b是具有最大深度的兩個(gè)兄弟字符:引理2：設(shè)T是最優(yōu)二元前綴碼所對(duì)應(yīng)的二叉樹(shù)，

x,y

T,x,y是樹(shù)葉兄弟，z是x,y的父親，令T’=T

{x,y},且令z的頻率f(z)=f(x)+f(y)，T’是對(duì)應(yīng)于二元前綴碼C’=(C

{x,y})

{z}的二叉樹(shù)，那么WPL(T)=WPL

(T’)+f(x)+f(y)。bczT’0011f(c)f(b)f(x)+f(y)bcxyT000111f(x)f(c)f(y)f(b)z定理：Huffman算法對(duì)任意規(guī)模為n（n2）的字符集C都能得到關(guān)于C的最優(yōu)前綴碼的二叉樹(shù)。

歸納基礎(chǔ)

n=2，字符集C={x1,x2}，Huffman算法得到的編碼是0和1，是最優(yōu)前綴碼。歸納步驟

假設(shè)Huffman算法對(duì)于規(guī)模為k的字符集能得到最優(yōu)前綴碼?？紤]規(guī)模為k+1的字符集C={x1,x2,...,xk+1},其中x1,x2

C是頻率最小的兩個(gè)字符。

令

C’=(C－{x1,x2})

{z}，

f(z)=f(x1)+f(x2)根據(jù)歸納假設(shè)，Huffman算法得到一棵關(guān)于字符集C’、頻率f(z)和f(xi)（i=3,4,...,k+1）的最優(yōu)前綴碼的二叉樹(shù)T’。把x1和x2作為z的兒子附加到T’上，得到樹(shù)T，那么T是關(guān)于字符集C=(C’－{z})

{x1,x2}的最優(yōu)前綴碼的二叉樹(shù)。

zT’x2x1T

zx1T*x2T*‘

z如若不然，存在更優(yōu)的樹(shù)T*。根據(jù)引理1，其最深層樹(shù)葉是x1,

x2，且WPL(T*)<WPL(T)。去掉T*中的x1和x2，根據(jù)引理2，所得二叉樹(shù)T*’滿足WPL(T*’)＝WPL(T*)－(f(x1)+f(x2))<WPL(T)－(f(x1)+f(x2))=WPL(T’)與T’是一棵關(guān)于C’的最優(yōu)前綴碼的二叉樹(shù)矛盾。

信息工程大學(xué)算法設(shè)計(jì)與分析貪心法—最小生成樹(shù)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版最小生成樹(shù)(Minimum-costSpanningTree)：設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹(shù)，則稱G’為G的生成樹(shù)。

生成樹(shù)的性質(zhì)：包含n個(gè)頂點(diǎn)；有且僅有(n-1)條邊；任兩點(diǎn)都是有路可達(dá)的。生成樹(shù)上各邊權(quán)的總和稱為該生成樹(shù)的耗費(fèi)。耗費(fèi)最小的生成樹(shù)稱為G的最小生成樹(shù)。1234566515366425

最小生成樹(shù)有廣泛應(yīng)用。比如建立城市間的通信網(wǎng)絡(luò)、鄉(xiāng)村間的道路連通等問(wèn)題，最小生成樹(shù)可以給出最優(yōu)的建設(shè)方案。最小生成樹(shù)問(wèn)題的本質(zhì)：求無(wú)向連通帶權(quán)圖的最小連通代價(jià)。判斷題。對(duì)于一個(gè)無(wú)向連通帶權(quán)圖，最小生成樹(shù)可能是不唯一的。A.不正確B.正確Prim算法和Kruskal算法都是用貪心思想構(gòu)造的最小生成樹(shù)。盡管它們的貪心策略不同，但都利用了最小生成樹(shù)性質(zhì)。

uv頂點(diǎn)集U頂點(diǎn)集V-UMST性質(zhì)證明：（反證法）假設(shè)G的任何一棵最小生成樹(shù)中都不包含邊(u,v)。設(shè)T是G的一棵最小生成樹(shù)，但不包含邊(u,v)。由于T是樹(shù)，且是連通的，因此必有一條從u到v的路徑，且該路徑上必有一條連接兩個(gè)頂點(diǎn)集U和V-U的邊(u',v')，其中u'屬于U，v'屬于V-U。將邊(u,v)加入到T中，得到一個(gè)含邊(u,v)的回路。當(dāng)刪除邊(u',v')時(shí)，回路被消除。由此得到另一棵生成樹(shù)T’，T’和T的區(qū)別僅在于用邊(u,v)取代了T中的邊(u’,v’)。因?yàn)?u,v)的權(quán)<=(u’,v’)的權(quán)，故T‘的權(quán)值<=T的權(quán)值。因此，T’也是G的最小生成樹(shù)，并包含邊（u,v），與假設(shè)矛盾。uu'vv'頂點(diǎn)集U頂點(diǎn)集V-U

1234566515366425123456112345614123456142123456154212345615342①②③④⑤⑥

需要的數(shù)據(jù)結(jié)構(gòu)：標(biāo)識(shí)頂點(diǎn)i是否屬于集合S：使用數(shù)組s如何有效地找出滿足條件i

S，j

V-S，且權(quán)值c[i][j]最小的邊(i,j)？

對(duì)于V-S中每個(gè)頂點(diǎn)j，把S到j(luò)權(quán)值最小的點(diǎn)i存入parent[j]，權(quán)值c[i][j]存入dist[j]，當(dāng)有新的點(diǎn)加入S時(shí)，更新parent[j]和dist[j]。1234566515366425迭代Sjp[2]d[2]p[3]d[3]p[4]d[4]p[5]d[5]p[6]d[6]初始{1}161115—∞—∞1{1,3}335111536342{1,3,6}635116236343{1,3,6,4}435116236344{1,3,6,4,2}235116223345{1,3,6,4,2,5}3511622334Prim算法執(zhí)行過(guò)程中相關(guān)數(shù)組的變化情況（parent[j]簡(jiǎn)寫(xiě)為p[j]，dist[j]簡(jiǎn)寫(xiě)為d[j]）1234561(1)5(4)3(5)4(2)2(3)voidprim(){/*prim算法構(gòu)建最小生成樹(shù)*//*初始化*/s[1]=1;s[2~n]=0;forj=2ton ifc[1][j]!=INF{parent[j]=1;dist[j]=c[j][1]；}/*循環(huán)n-1次，依次加入點(diǎn)和邊*/for(k=1;k<=n-1;k++){/*找出V-S中dist值最小的頂點(diǎn)j*/inttmin=INF;j=-1;fori=2ton if(s[i]==0)&&dist[i]<tmin){tmin=dist[i];j=i;}s[j]=1;/*將j添加到S中*//*依次判斷和j相鄰且在V-S中的點(diǎn)，判斷該邊權(quán)值是否更小，如果是，則修改parent和dist*/fori=2tonif(s[i]==0)&&dist[i]<c[j][i]){dist[i]=c[j][i];parent[i]=j;}}}時(shí)間復(fù)雜度：O(n2)最小生成樹(shù)性質(zhì)：只要是連接兩個(gè)集合的權(quán)值最小的邊，一定在某棵最小生成樹(shù)中。Kruskal算法基本思想：1.

n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支，將所有的邊按權(quán)值從小到大排序；

2.依次查看每一條邊(i,j)，如果i和j分別來(lái)自不同的連通分支T1和T2時(shí)，就用邊(i,j)將T1和T2連接成一個(gè)連通分支；3.重復(fù)步驟2，直到只剩下一個(gè)連通分支時(shí)為止。1234561212345611234561534212345612312345665153664251234561423①②③④⑤⑥Kruskal算法中的關(guān)鍵步驟：邊按權(quán)值從小到大排序逐一判斷邊的兩個(gè)鄰接點(diǎn)是否在同一個(gè)連通分支中，如不是1）合并兩個(gè)端點(diǎn)所在的分支2）把邊加入最小生成樹(shù)中用并查集高效實(shí)現(xiàn)查找元素屬于哪個(gè)集合合并兩個(gè)集合Prim算法和Kruskal算法比較：共同點(diǎn)：根據(jù)MST性質(zhì)做貪心選擇不同點(diǎn)：Prim算法：不斷加點(diǎn)，時(shí)間復(fù)雜度為O(n2)Kr