算法基礎 chap4學習資料

1哈夫曼編碼哈夫曼編碼哈夫曼編碼是廣泛地用于數據文件壓縮的有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現的頻率表來建立一個用0、1串表示各字符的最優表示方式。一個包含100,000個字符的文件，各字符出現頻率不同。定長變碼需要300,000位，而按表中變長編碼方案，文件的總碼長為224,000，總碼長較少約25%。（111110101100）abcdef頻率(千次)4513121695定長碼000001010011100101變長碼0101100111110111002前綴碼前綴碼對每一個字符規定一個0、1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。編碼的前綴性質可以使譯碼方法非常簡單。3前綴碼平均碼長（WPL：帶權路徑長度）給定編碼字符集C及其頻率分布f，C的一個前綴碼編碼方案對應于一棵二叉樹T。字符c在T中的深度為dT(c)（前綴碼長），則該方案的平均碼長為：使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集C的最優前綴碼。4構造哈夫曼編碼哈夫曼編碼哈夫曼提出構造最優前綴碼的貪心算法，由此產生的編碼方案稱為哈夫曼編碼。哈夫曼算法以自底向上的方式構造表示最優前綴碼的二叉樹T。算法從|C|個葉結點開始，執行|C|－1次的“合并”運算后產生最終所要求的樹T。5算法說明算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優先隊列Q用在貪心選擇時有效地確定算法當前要合并的兩棵具有最小頻率的樹。一旦兩棵具有最小頻率的樹合并后，產生一棵新的樹，其頻率為合并的兩棵樹的頻率之和，并將新樹插入優先隊列Q。經過n-1次的合并后，優先隊列中只剩下一棵樹，即所要求的樹T。算法：P94—95。關于n個字符的哈夫曼算法的計算時間為O(nlogn)。67哈夫曼算法的正確性貪心選擇性質C是編碼字符集，字符c的頻率為f(c)。x和y是C中具有最小頻率的兩個字符，則存在C的最優前綴碼使x，y具有相同碼長且僅最后一位編碼不同。證明設二叉樹T是C的任意一個最優前綴碼，只需要證明對T作適當的修改后得到新的二叉樹T"，使得新樹中x，y是最深葉子且為兄弟，同時T"表示的前綴碼也是C的一個最優前綴碼。設b,c

是T中最深葉子且為兄弟，設f(b)

f(c),f(x)

f(y),則由于x和y是C中具有最小頻率的兩個字符，f(x)

f(b),f(y)

f(c)。8哈夫曼算法的正確性在T中交換b,x的位置得到T'，繼續在T'交換c,y的位置得到T"。xycbTbycxT'bcyxT"9哈夫曼算法的正確性則樹T、T'的前綴碼的平均碼長之差為：同樣，可以證明B(T')－B(T")≥0。因此有：B(T")≤

B(T')≤

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

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

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

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

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

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

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

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

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

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

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

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

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