1哈夫曼編碼哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0、1串表示各字符的最優(yōu)表示方式。一個包含100,000個字符的文件，各字符出現(xiàn)頻率不同。定長變碼需要300,000位，而按表中變長編碼方案，文件的總碼長為224,000，總碼長較少約25%。（111110101100）abcdef頻率(千次)4513121695定長碼000001010011100101變長碼0101100111110111002前綴碼前綴碼對每一個字符規(guī)定一個0、1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。編碼的前綴性質(zhì)可以使譯碼方法非常簡單。3前綴碼平均碼長（WPL：帶權(quán)路徑長度）給定編碼字符集C及其頻率分布f，C的一個前綴碼編碼方案對應(yīng)于一棵二叉樹T。字符c在T中的深度為dT(c)（前綴碼長），則該方案的平均碼長為：使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。4構(gòu)造哈夫曼編碼哈夫曼編碼哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。算法從|C|個葉結(jié)點(diǎn)開始，執(zhí)行|C|－1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹T。5算法說明算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法當(dāng)前要合并的兩棵具有最小頻率的樹。一旦兩棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的兩棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q。經(jīng)過n-1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹T。算法：P94—95。關(guān)于n個字符的哈夫曼算法的計算時間為O(nlogn)。67哈夫曼算法的正確性貪心選擇性質(zhì)C是編碼字符集，字符c的頻率為f(c)。x和y是C中具有最小頻率的兩個字符，則存在C的最優(yōu)前綴碼使x，y具有相同碼長且僅最后一位編碼不同。證明設(shè)二叉樹T是C的任意一個最優(yōu)前綴碼，只需要證明對T作適當(dāng)?shù)男薷暮蟮玫叫碌亩鏄銽"，使得新樹中x，y是最深葉子且為兄弟，同時T"表示的前綴碼也是C的一個最優(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)。8哈夫曼算法的正確性在T中交換b,x的位置得到T'，繼續(xù)在T'交換c,y的位置得到T"。xycbTbycxT'bcyxT"9哈夫曼算法的正確性則樹T、T'的前綴碼的平均碼長之差為：同樣，可以證明B(T')－B(T")≥0。因此有：B(T")≤

B(T')≤

B(T)。又由于T所表示的前綴碼是最優(yōu)的，即B(T)≤B(T")，所以：B(T)=B(T")即T"表示的前綴碼也是最優(yōu)的，且x，y具有相同碼長且僅最后一位編碼不同。10哈夫曼算法的正確性最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)T是表示C的一個最優(yōu)前綴碼的完全二叉樹，C中字符c的頻率為f(c)。設(shè)x,y是T中兩個葉子結(jié)點(diǎn)且為兄弟，z為它們的父結(jié)點(diǎn)。若將z看作是具有頻率f(x)+f(y)的字符，則樹T'=T-{x,y}表示字符集C'=C-{x,y}∪{z}的一個最優(yōu)前綴碼。證明首先T的平均碼長B(T)可用T'的平均碼長B(T')表示。11哈夫曼算法的正確性12哈夫曼算法的正確性若T'表示的C'的前綴碼不是最優(yōu)的，則存在T"表示的C'的最優(yōu)前綴碼，Ｂ(T")<B(T')。z作為C'中的一個字符，故z作為T"中的一個葉子，若將x,y加入T"中，作為z的兒子結(jié)點(diǎn)，得到表示C的前綴碼的二叉樹Ｔ'"：與Ｔ最優(yōu)矛盾，T'表示的C'的前綴碼是最優(yōu)的。貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)決定了哈夫曼算法的正確性。13單源最短路徑問題描述給定帶權(quán)有向圖G=(V,E)，每條邊的權(quán)是非負(fù)實(shí)數(shù)。給定V中的一個頂點(diǎn)，稱為源?，F(xiàn)在要計算從源到所有其它各頂點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。單源最短路徑問題的貪心選擇策略：選擇從源v出發(fā)目前最短的路徑所到達(dá)的頂點(diǎn)，這就是目前的局部最優(yōu)解。14算法基本思想Dijkstra算法解單源最短路徑問題的貪心算法。基本思想是設(shè)置頂點(diǎn)集合S并不斷作貪心選擇擴(kuò)充這個集合。一個頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。初始時，S中僅含有源。設(shè)u是G的某一個頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個頂點(diǎn)所對應(yīng)的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最小的最短特殊路徑長度的頂點(diǎn)u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長度。15算法基本思想貪心選擇每次找到最小的dist[u]，將u添加到S中，同時對數(shù)組dist[]作必要的修改。操作步驟由近到遠(yuǎn)逐步計算，每次最小的最短特殊路徑長度就是對應(yīng)頂點(diǎn)的最短路徑長度。然后從這個最近者出發(fā)。即依據(jù)最近者修訂到各頂點(diǎn)的距離，然后再選出新的最近者。如此走下去，直到所有頂點(diǎn)都走到。算法描述P97-981610205010030106012543一個實(shí)例對右圖中的有向圖，應(yīng)用Dijkstra算法計算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。Dijkstra算法的迭代過程迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10∞301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}51050306017算法的正確性和計算復(fù)雜性貪心選擇性質(zhì)Dijkstra算法中所做的貪心選擇是：若u是V–S中具有最小最短特殊路徑的頂點(diǎn)，就將u選入S，并確定了從源到u的最短路徑長度dist[u]。即下一條最短路徑是中間只經(jīng)過S中頂點(diǎn)而最后到達(dá)u的最短路徑。為什么從源到u沒有更短的其它路徑呢？若有，則這條路徑一定經(jīng)過V–S中的其它頂點(diǎn)：vuxSdist[u](最近距離)dist[x]dist[x]+d(x,u)＜dist[u]（條件假設(shè)）從而dist[x]＜dist[u]，與u的選取矛盾18算法的正確性和計算復(fù)雜性最優(yōu)子結(jié)構(gòu)性質(zhì)算法中確定的dist[u]確實(shí)是當(dāng)前從源到頂點(diǎn)u的最短特殊路徑。因此，探討添加u到S中后，以頂點(diǎn)i為參考，考慮dist[i]的變化。計算復(fù)雜性對于具有n個頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個圖，那么Dijkstra算法的主循環(huán)體需要O(n)時間。這個循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要O(n2)時間。19最小生成樹最小生成樹設(shè)G=(V,E)是無向連通帶權(quán)圖，E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G'是一棵包含G的所有頂點(diǎn)的樹，則稱G'為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費(fèi)。在G的所有生成樹中，耗費(fèi)最小的生成樹稱為G的最小生成樹。最小生成樹在實(shí)際中具有廣泛的應(yīng)用。城市間通信網(wǎng)絡(luò)鋪設(shè)20樹的基本性質(zhì)相關(guān)性質(zhì)連通無回路的圖G稱為樹。樹是點(diǎn)比邊多一的連通圖，G連通。樹是點(diǎn)比邊多一的無回路圖，G無回路。樹若添條邊就有回路：G無回路，但對任意的u,v∈V，若(u,v)

E，則G+(u,v)中恰有一條回路。樹若減條邊就不連通：G連通，但對

e∈E,G–e不連通。n個頂點(diǎn)的連通圖的生成樹含有n–1條邊。21最小生成樹性質(zhì)MST性質(zhì)用貪心算法設(shè)計策略可以設(shè)計出構(gòu)造最小生成樹的有效算法。構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計策略的例子。盡管這兩個算法做貪心選擇的方式不同，它們都利用了最小生成樹性質(zhì)。設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)∈E，且u∈U，v∈V-U，且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。22最小生成樹性質(zhì)一定只有一條邊連接左右兩部分Why？23構(gòu)造最小生成樹要保證n–1條邊構(gòu)成樹，必須使這n–1條邊是連通無回路的。Prim算法：在保證連通的前提下依次選出權(quán)重較小的n–1條邊（實(shí)現(xiàn)中體現(xiàn)為n個頂點(diǎn)的選擇）。Kruskal算法：在保證無回路的前提下依次選擇權(quán)重較小的n–1條邊。24Prim算法基本思想在保證連通的前提下，依次選出權(quán)重較小的n–1條邊。G=(V,E)為無向連通帶權(quán)圖，令V={1,2,…,n}。設(shè)置一個集合S，初始化S={1}，T=Φ。貪心策略：如果V–S中的頂點(diǎn)j與S中的某個點(diǎn)i連接且(i,j)是E中的權(quán)重最小的邊，于是就選擇j(將j加入S)，并將(i,j)加入T中。重復(fù)執(zhí)行貪心策略，直至V–S為空。時間復(fù)雜度為O(n2)

25Prim算法一個實(shí)例給定一個連通帶權(quán)圖如下：1234561655536624初始時S={1}，T=Φ；1第一次選擇：∵(1,3)權(quán)最小∴S={1,3}T={(1,3)}

；3第二次選擇：∵(3,6)權(quán)最小∴S={1,3,6}，

T={(1,3),(3,6)}

；6第三次選擇：∵(6,4)權(quán)最小∴S={1,3,6,4}，

T={(1,3),(3,6),(6,4)}

；4第四次選擇：∵(2,3)權(quán)最小∴S={1,3,6,4,2}，

T={(1,3),(3,6),(6,4),(2,3)}

；2第五次選擇：∵(5,2)權(quán)最小∴S={1,3,6,4,2,5}，

T={(1,3),(3,6),(6,4),(3,2)(2,5)}

；526Kruskal算法基本思想在保證無回路的前提下依次選擇權(quán)重較小的n–1條邊。貪心策略如果(i,j)是E中尚未被選中的邊中權(quán)重最小的，并且(i,j)不會與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇(i,j)。如何知道(i,j)不會造成回路？若邊(i,j)的兩個端點(diǎn)i和j屬于同一個連通分支，則選擇(i,j)會造成回路，反之則不會造成回路。因此，初始時將圖的n個頂點(diǎn)看成n個孤立分支。27Kruskal算法算法執(zhí)行首先將G的n個頂點(diǎn)看成n個孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接兩個不同的連通分支：當(dāng)查看到第k條邊(v,w)時，如果端點(diǎn)v和w分別是當(dāng)前2個不同的連通分支T1和T2中的頂點(diǎn)時，就