第6講 貪心算法

1、 貪心算法找零錢(qián)問(wèn)題找零錢(qián)問(wèn)題l問(wèn)題描述：用面額為d1d2dm的最少數(shù)量的硬幣找出金額為n的零錢(qián)。例：美國(guó)廣泛使用的硬幣面額為d1=25，d2=10，d3=5，d4=1。如何用這些面額給出48美分的找零？1個(gè)25美分，2個(gè)10美分，3個(gè)1美分基于“貪心”的想法可以將剩余的硬幣數(shù)量降為最低找零錢(qián)問(wèn)題找零錢(qián)問(wèn)題l例：假設(shè)有面值單位分別為1、4和6的硬幣。如果需要找出金額為8的零錢(qián)。若采用貪心算法，得到的解決方案如何？先選取面值最大的，然后再選小面值的采用1枚面值為6的硬幣，兩枚面值為2的硬幣更優(yōu)的解：2枚面值為4的硬幣l貪心算法并不能總是找出最優(yōu)解l采用動(dòng)態(tài)規(guī)劃求最優(yōu)解貪心算法貪心算法l貪心法建議

2、通過(guò)一系列步驟來(lái)構(gòu)造問(wèn)題的解，每一步對(duì)目前構(gòu)造的部分解做一個(gè)擴(kuò)展，直到獲得問(wèn)題的完整解為止。l所做的每一步選擇都必須滿足以下條件：可行：即它必須滿足問(wèn)題的約束局部最優(yōu)：它是當(dāng)前步驟中所有可行選擇中最佳的局部選擇不可取消：選擇一旦做出，在算法的后面步驟中就無(wú)法改變了背包問(wèn)題背包問(wèn)題l問(wèn)題描述給定n個(gè)體積分別為s1,s2,sn、價(jià)值分別為v1,v2,vn的物品和一個(gè)容量為C的背包，要找到非負(fù)實(shí)數(shù)x1,x2,xn, 使和 在約束 下最大。0/1背包問(wèn)題：物品不可分一般背包問(wèn)題：物品是可分割的在最優(yōu)解中，以某種合適的順序選擇每個(gè)物品，并盡可能將該物品裝入背包。niiivx1niiiCsx1Csxnii

3、i1背包問(wèn)題背包問(wèn)題l選擇函數(shù)：選擇剩余物品中價(jià)值最大的選擇剩余物品中體積最小的選擇單位體積上價(jià)值最高的l例：s1020304050v2030664060v/s2.01.52.21.01.2選擇xi值最大vi 0 0 1 0.5 1146最小si 1 1 1 1 0156最大vi/si 1 1 1 0 0.8164Algorithm Greedy-KNAPSACKlInput: size vector s1.n and value vector v1.n of n items that are both sorted as non-increasing order according to t

4、he ratio v(i)/s(i); the capacity C of the knapsack, the total number of items nlOutput: the greedy optimal solution x1.n lfor i 0 to nl xi 0lend forlcu Clfor i 0 to nl if si cu then lexit lend ifl x(i) 1l cu cu-s(i)lend forlif i n then x(i) cu/s(i) end iflreturn x活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最大的相

5、容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題l1 問(wèn)題描述：設(shè)有設(shè)有n個(gè)活動(dòng)的集合個(gè)活動(dòng)的集合E=1,2,n，其中每個(gè)活動(dòng)，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間和一個(gè)結(jié)束時(shí)間fi,且且si fi 。如果選擇了活動(dòng)。如果選擇了活動(dòng)i，則它，則它在半開(kāi)時(shí)間區(qū)間在半開(kāi)時(shí)間區(qū)間si, fi)內(nèi)占用資源。內(nèi)占用資源。若區(qū)間若區(qū)間si, fi)與區(qū)間與區(qū)

6、間sj, fj)不相交，則稱活動(dòng)不相交，則稱活動(dòng)i與活與活動(dòng)動(dòng)j是相容的。也就是說(shuō)，當(dāng)是相容的。也就是說(shuō)，當(dāng)sifj或或sjfi時(shí)，活動(dòng)時(shí)，活動(dòng)i與活與活動(dòng)動(dòng)j相容。相容。 活動(dòng)安排問(wèn)題就是在所給的集合中選出最大的相活動(dòng)安排問(wèn)題就是在所給的集合中選出最大的相容活動(dòng)子集合。容活動(dòng)子集合。lint greedySelector(int s , int n, int f , bool a )l a1=true; j=1;l count=1;l for ( i=2;i=fj) l ai=true;l j=i;l count+;l l else ai=false;l l return count;l 各

7、活動(dòng)的起始時(shí)間和結(jié)束時(shí)間各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組存儲(chǔ)于數(shù)組s s和和f f中且按結(jié)束時(shí)中且按結(jié)束時(shí)間的非減序排列間的非減序排列 活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題由于輸入的活動(dòng)以其完成時(shí)間的非減序非減序排列，所以算法greedySelectorgreedySelector每次總是選擇具具有最早完成時(shí)間有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說(shuō)，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。 活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題例：例：設(shè)待安排的11個(gè)活動(dòng)的

8、開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下： i1234567891011Si130535688212fi4567891011121314活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題 算法算法greedySelector greedySelector 的計(jì)算過(guò)程的計(jì)算過(guò)程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長(zhǎng)條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。 活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題l正確性證明（用數(shù)學(xué)歸納法證明）1 貪心選擇性質(zhì)即證明活動(dòng)安排問(wèn)題總存在一個(gè)最優(yōu)解從貪心選擇開(kāi)始。4.2 活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題l正確性證明（用數(shù)學(xué)歸納法證明）1 貪心選擇性質(zhì)設(shè)E=1,2

9、,n為所給的活動(dòng)集合。由于E中的活動(dòng)按結(jié)束時(shí)間的非遞減排序，故活動(dòng)1具有最早完成時(shí)間。首先證明活動(dòng)安排問(wèn)題有一個(gè)最優(yōu)解以貪心選擇開(kāi)始，即該最優(yōu)解中包含活動(dòng)1.4.2 活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題l正確性證明（用數(shù)學(xué)歸納法證明）1 貪心選擇性質(zhì)設(shè)AE是所給活動(dòng)安排問(wèn)題的一個(gè)最優(yōu)解，且A中的活動(dòng)也按結(jié)束時(shí)間非遞減排序，A中的第一個(gè)活動(dòng)是k?；顒?dòng)安排問(wèn)題活動(dòng)安排問(wèn)題l正確性證明（用數(shù)學(xué)歸納法證明）1 貪心選擇性質(zhì)若k1,則A就是以貪心選擇開(kāi)始的最優(yōu)解。若k1,設(shè)B=A-k1。因?yàn)閒1=fk且A中的活動(dòng)是相容的。古B中的活動(dòng)也是相容的。又由于B中的活動(dòng)個(gè)數(shù)與A中的活動(dòng)個(gè)數(shù)相同，故A是最優(yōu)的，B也是最優(yōu)的。

10、即B是以選擇活動(dòng)1開(kāi)始的最優(yōu)活動(dòng)安排。由此可見(jiàn)，總存在以貪心選擇開(kāi)始的最優(yōu)活動(dòng)安排方案?；顒?dòng)安排問(wèn)題活動(dòng)安排問(wèn)題l正確性證明（用數(shù)學(xué)歸納法證明）2 最優(yōu)子結(jié)構(gòu)性質(zhì)在作出了貪心選擇，即選擇了活動(dòng)1后，原問(wèn)題簡(jiǎn)化為對(duì)E中所有與活動(dòng)1相容的活動(dòng)進(jìn)行活動(dòng)安排的子問(wèn)題。即若A是原問(wèn)題的最優(yōu)解，則A=A-1是活動(dòng)安排問(wèn)題的E=iE:Sif1的最優(yōu)解。活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題l正確性證明（用數(shù)學(xué)歸納法證明）2 最優(yōu)子結(jié)構(gòu)性質(zhì)反證法：若E中存在另一個(gè)解B，比A有更多的活動(dòng)，則將1加入B中產(chǎn)生另一個(gè)解B，比A有更多的活動(dòng)。與A的最優(yōu)性矛盾。 活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題l正確性證明（用數(shù)學(xué)歸納法證明）因此，每一步所

11、作出的貪心選擇都將問(wèn)題簡(jiǎn)化為一個(gè)更小的與原問(wèn)題具有相同形式的子問(wèn)題。對(duì)貪心選擇次數(shù)用歸納法可知，貪心算法greedySelector產(chǎn)生問(wèn)題的最優(yōu)解。單源最短路徑問(wèn)題（單源最短路徑問(wèn)題（Dijkstra算法）算法）l問(wèn)題描述已知有向圖 G = (V, E)，每條邊上的權(quán)值均為非負(fù)。其中一個(gè)結(jié)點(diǎn)s指定為源點(diǎn)，求從源點(diǎn)s到圖中所有其它結(jié)點(diǎn)x的距離，即s到x的最短路徑長(zhǎng)度。lDijkstra算法 貪心策略按照最短路徑長(zhǎng)度遞增的次序求得源點(diǎn)到達(dá)每一個(gè)頂點(diǎn)的最短路徑單源最短路徑問(wèn)題單源最短路徑問(wèn)題l最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)：最短路徑的子路徑是最短路徑子路徑是最短路徑對(duì)于一給定的帶權(quán)有向圖G=(V,E)，設(shè)p

12、=是從v1到vk的最短路徑。那么對(duì)于任意i,j，其中1 i j k，設(shè)pij=為p中從頂點(diǎn)vi到頂點(diǎn)vj的子路徑。那么，pij是從vi到vj的最短路徑。l證明：證明：如果將路徑p分解為 ，則有w(p)=w(p1i )+w(pij )+w(pjk )。假設(shè)存在一條從vi到vj的路徑pij，其權(quán)值w(pij)w(pij)。 那么， 是從v1到vk的一條路徑，它的權(quán)值w(p)=w(p1i )+w(pij)+w(pjk )小于w(p)，這與p是v1至vk的最短路徑相矛盾。kpjpipvvvvjkiji11kpjpipvvvvjkiji11Dijkstra算法思想算法思想l假設(shè)V=1,2,n, 源點(diǎn)s=

13、1。l初始頂點(diǎn)分為兩個(gè)集合X = 1 和Y = 2,3,.,n。X集中的頂點(diǎn)是已求得最短路徑的頂點(diǎn)；lY集中的每個(gè)頂點(diǎn)y都有一個(gè)標(biāo)記y, 它是目前從源點(diǎn)到頂點(diǎn)y，中間只經(jīng)過(guò)X集中的頂點(diǎn)的最短路徑的長(zhǎng)度；l每次從Y集中選擇一個(gè)y值最小的頂點(diǎn)y加入X集；l一旦y加入X集，那么考察與y相鄰的每個(gè)頂點(diǎn)w的標(biāo)記，如果源點(diǎn)經(jīng)過(guò)y到達(dá)w的路徑更短，則更新該標(biāo)記；l若y表示從源點(diǎn)到v的距離，那么算法結(jié)束時(shí)，對(duì)每個(gè)頂點(diǎn)均有y= yAlgorithm 8.1 DIJKSTRA Input: A weighted directed graph G=(V,E), where V=1,2,n.Output: The d

14、istance from vertex 1 to every other vertex in G.1. X=1; YV-1; 102. for y2 to n3. if y is adjacent to 1 then ylength1,y4.else y 5.end if6.end for7.for j1 to n-18. Let y Y be such that y is minimum9.XX y add vertex y to X10.YY-y delete vertex y form Y11.for each edge (y,w)12.if w Y and y+lengthy,w w

15、then13. w y+lengthy,w14.end for15. end forDijkstra算法算法261534112531549413X11,21,2,41,2,4,31,2,4,3,51,2,4,3,5,6Y34561221356104456171938619513617Dijkstra算法總是在Y集中選擇離源點(diǎn)最近的頂點(diǎn)加入集合X，故稱該算法使用了貪心策略。Dijkstra算法的貪心選擇性質(zhì)（正確性證明）算法的貪心選擇性質(zhì)（正確性證明）l貪心策略并非總是能獲得全局意義上的最理想結(jié)果，但Dijkstra算法確實(shí)得到了最短路徑。關(guān)鍵要證明，當(dāng)頂點(diǎn)y加入集合X時(shí)，有y= y1xwyX數(shù)

16、學(xué)歸納法證明數(shù)學(xué)歸納法證明Dijkstra算法算法l定理8.1：給出一個(gè)邊具有非負(fù)權(quán)值的有向圖G和源點(diǎn)s， Dijkstra算法在時(shí)間(n2) 內(nèi)找出從s到其他每一頂點(diǎn)距離的長(zhǎng)度。l對(duì)Dijkstra算法的改進(jìn)針對(duì)稠密圖利用小頂堆數(shù)據(jù)結(jié)構(gòu)，在O(log)時(shí)間內(nèi)從Y集中選出頂點(diǎn)y采用鄰接表為圖的存儲(chǔ)結(jié)構(gòu)Algorithm 8.2 SHORTESTPATHInput: A weighted directed graph G=(V,E), where V=1,2,.,n.Output: The distance from vertex 1 to every other vertex in G. As

17、sume that we have an empty heap H at the beginning.1.YV-1; 10; key(1) 12.for y2 to n3.if y is adjacent to 1 then4. y=length1,y5. key(y) y6. INSERT(H,y)7.else8. y 9. keyy y10.end if 11. end for NEXT PAGEAlgorithm 8.2 SHORTESTPATH 12. for j1 to n-113.yDELETEMIN(H)14.YY-y15.for each vertex w Y that is

18、adjacent to y16. if y+lengthy,w w then17. w y+lengthy,w18.key(w) w19. end if20. if w H then INSERT(H,w)21. else SIFTUP(H,H-1(W)22. end if23.end for24. end forO(mlog n)最小生成樹(shù)問(wèn)題（最小生成樹(shù)問(wèn)題（Kruskal算法）算法）l定義8.1：設(shè)G = (V, E)是一個(gè)具有含權(quán)邊的連通無(wú)向圖。G的一棵生成樹(shù)(V,T)是G的作為樹(shù)的子圖。如給G加權(quán)并且T的各邊的權(quán)的和為最小值，那么(V,T)就稱為最小耗費(fèi)生成樹(shù)，簡(jiǎn)稱生成樹(shù)。l Kru

19、skal算法：對(duì)G的邊以非降序權(quán)重排列；對(duì)排好序的每條邊，如果將其加入T不會(huì)形成回路，則加入樹(shù)T中；否則將其丟棄。例：例： Kruskal算法算法61235412131139746(1,2)(1,3)(4,6)(5,6)(2,3)(4,5)(3,4)(2,4)(3,5)12346791113612354若構(gòu)成回路，則丟棄該邊若構(gòu)成回路，則丟棄該邊Kruskal算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)l表示森林的數(shù)據(jù)結(jié)構(gòu)用不相交集數(shù)據(jù)結(jié)構(gòu)來(lái)表示森林初始時(shí)，圖的每個(gè)頂點(diǎn)由包含一個(gè)頂點(diǎn)的樹(shù)表示算法執(zhí)行時(shí)，森林中的每個(gè)連通分量由一棵樹(shù)來(lái)表示選擇權(quán)值最小的邊將兩個(gè)連通分量連接起來(lái)由Union操作實(shí)現(xiàn)Algorithm 8.

20、3 KRUSKAL Input: A weighted connected undirected graph G=(V,E) with n vertices. Output: The set of edges T of a minimum cost spanning tree for G.1.Sort the edges in E by nondecreasing weight2.for each vertex vV3.MAKESETv4.end for5.T=6.while |T|n-17.Let (x,y) be the next edge in E.8.if FIND(x) FIND(y

21、) then9. Add(x,y) to T10 UNION(x,y)11end if12. end whileKruskal算法正確性證明算法正確性證明l引理8.2：在含權(quán)無(wú)向圖中，Kruskal算法能正確地找出最小生成樹(shù)l證明：對(duì)T的大小實(shí)施歸納法，證明T是最小生成樹(shù)邊集的子集初始時(shí)，T=，命題成立；設(shè)加入邊e = (x,y)之前命題成立，即有TT*，其中T*是最小生成樹(shù)邊的集合；設(shè)X是包含x的子樹(shù)的頂點(diǎn)集，T=Te，需證明T也是最小生成樹(shù)邊集T*的子集。Kruskal算法正確性證明算法正確性證明l由于TT*，若T*包含e，則T=Te T*；l若T*不包含e，則T*e必定包含以e為一條邊的

22、回路；le=(x,y)連接了X中的一個(gè)頂點(diǎn)和V-X中的另一個(gè)頂點(diǎn)，則T*中必定存在另一條邊e=(w,z)，其中wX，zV-X；l由于e在e之前添加，故cost(e) cost(e)；l構(gòu)造T*=T*-ee，則TT*，且T*是最小生成樹(shù)邊的集合。Kruskal算法時(shí)間效率分析算法時(shí)間效率分析l第1和第2步分別花費(fèi) O(mlogm) 和(n), m = |E|; l第7步執(zhí)行n-1次，需要花費(fèi)O(n);l第9步花費(fèi)(1), 最多執(zhí)行m次,總共花費(fèi) O(m);lUnion操作執(zhí)行n-1 次，而find 操作最多執(zhí)行 2m 次.，兩個(gè)操作總的花費(fèi)為O(mlog*n);l算法總的運(yùn)行時(shí)間取決于排序算法，

23、即O(mlogm);l定理8.3：在一個(gè)有m條邊的含權(quán)無(wú)向圖中， Kruskal算法可在O(mlogm)時(shí)間內(nèi)找出最小生成樹(shù)最小生成樹(shù)問(wèn)題（最小生成樹(shù)問(wèn)題（Prim算法）算法）l設(shè)G=(V,E), V取整數(shù)集合1,2,n. l算法從建立兩個(gè)頂點(diǎn)集開(kāi)始: X=1和Y=2,n, 然后生長(zhǎng)生成樹(shù)，每次生成一條邊。l生成的邊(x,y)具有以下性質(zhì)： xX, y Y， 且該邊是所有滿足上述條件的邊中權(quán)值最小者。l然后將y從Y集移到X集。l重復(fù)生成邊的步驟直到Y(jié)集為空為止。Prim算法算法1.T; X1; YV-12.while Y 3. Let (x,y) be of minimum weight su

24、ch that xX and yY4. XXy5. YY-y6. TT(x,y)7.end while 例：例：Prim算法生成生成樹(shù)算法生成生成樹(shù)61235412131139746Algorithm 8.4 PRIM Input: A weighted connected undirected graph G=(V,E), where V=1,2,.,n.Output: The set of edges T of a minimum cost spanning tree for G.1.T; X1; YV-12.for y2 to n3.if y adjacent to 1 then4.Ny

25、15.Cyc1,y6.else Cy7.end if 8.end for NEXT PAGEAlgorithm 8.4 PRIM9. for j1 to n-1 find n-1 edges10. Let yY be such that Cy is minimum11.TTy,Ny add edge (y,Ny) to T12.XXy add vertex y to X13. YY-y delete vertex y from Y14. for each vertex w Y that is adjacent to y15. if cy,wCw then16. Nwy17. Cwcy,w18.

26、 end if19. end for20. end for Prim算法的正確性證明算法的正確性證明l引理8.3：在含權(quán)無(wú)向圖中，Prim算法能正確地找出最小生成樹(shù)l證明：對(duì)T的大小實(shí)施歸納法，證明(X,T)是最小生成樹(shù)的子樹(shù)初始時(shí)，T=，命題成立；假設(shè)添加邊e=(x,y)之前命題成立， 其中xX, yY設(shè)X=Xy，T=Te，需證明G=(X,T)也是最小生成樹(shù)的子樹(shù)（參見(jiàn)P155）Prim算法的效率分析算法的效率分析l第1步花費(fèi)(n); l第2步循環(huán)花費(fèi)(n)時(shí)間.第3-6步花費(fèi)O(n);l第10步搜索離X最近的頂點(diǎn)y，每次迭代花費(fèi)時(shí)間(n). 搜索需執(zhí)行 n-1次，故第10步總體花費(fèi) (n2

27、); l第14步共執(zhí)行 2m 次，第15步測(cè)試執(zhí)行m次，第16、17步最多執(zhí)行m次；l因此，算法的時(shí)間復(fù)雜度為 (m+n2).Prim算法的改進(jìn)算法的改進(jìn)l利用最小堆數(shù)據(jù)結(jié)構(gòu)，使得可以在O(logn)時(shí)間內(nèi)取得Y集中的頂點(diǎn)y，這個(gè)y和V-Y集中一個(gè)頂點(diǎn)連接的邊的代價(jià)是最小的。改進(jìn)的改進(jìn)的Prim算法算法Input: A weighted connected undirected graph G=(V,E), where V=1,2,.,n.Output: The set of edges T of a minimum cost spanning tree for G. Assume that

28、we have an empty heap H at the beginning.1.T; YV-12.for y2 to n3. if y is adjacent to 1 then4.Ny15.key(y)c1,y6.INSERT(H,y)7. else key(y)8. end if9. end for NEXT PAGE改進(jìn)的改進(jìn)的Prim算法算法 10. for j1 to n-1 find n-1 edges11. yDELETEMIN(H)12. TT(y,N|y|) add edge (y,N|y|) to T13. YY-y delete vertex y from Y14.

29、 for each vertex w Y that is adjacent to y15. if cy,wkey(w) then16. Nwy17. key(w)cy,w18.end if19.if w H then INSERT(H,w)20.else SIFTUP(H,H-1(w)21. end for22. end for文件壓縮問(wèn)題（文件壓縮問(wèn)題（Huffman樹(shù)算法）樹(shù)算法）l設(shè)有100,000個(gè)字符的文件，其中只包含有 a, e, t, r, f, d 六種不同的字符，且字符出現(xiàn)的頻度不盡相同。計(jì)算機(jī)中能夠表達(dá)的信息只有0和1。怎樣編碼才能使文件的編碼長(zhǎng)度最短？文件編碼文件編碼ae

30、trfd頻度(千字)4513121695等長(zhǎng)等長(zhǎng)編碼編碼000001010011100101變長(zhǎng)變長(zhǎng)編碼編碼1000101011011011100變長(zhǎng)變長(zhǎng)編碼編碼201011001111101110011011000110110001100110011001100前綴編碼前綴編碼前綴編碼前綴編碼a45e13t12r16d5f9000011111 00a45t12e13d5f9r160000011111用用二叉樹(shù)二叉樹(shù)表表示示前綴編碼前綴編碼等長(zhǎng)等長(zhǎng)編碼編碼變長(zhǎng)變長(zhǎng)編碼編碼CcTcdcfTB)()()(文件編碼長(zhǎng)度文件編碼長(zhǎng)度Huffman算法算法l貪心策略：將短的編碼分配給高頻字符，長(zhǎng)的編碼分配給低頻字符構(gòu)造 n 棵只含根只含根結(jié)點(diǎn)的二叉樹(shù)選擇兩個(gè)權(quán)值最小權(quán)值最小的二叉樹(shù)，構(gòu)造新的二叉樹(shù)重復(fù)重復(fù)該過(guò)程，直到只剩一棵只剩一棵二叉樹(shù)為止Huffman算法的正確性算法的正確性l具有貪心選擇性質(zhì)設(shè)x和y是字母表C中具有最低頻度的兩個(gè)字符，則存在C的一種最優(yōu)前綴編碼，其中x和y的編碼長(zhǎng)度相同但