第九章 貪心法

1、 逐步給出解的各部分，逐步給出解的各部分， 在每一步在每一步“貪婪地貪婪地” 選擇最好的部分解，選擇最好的部分解，但不顧及這樣選擇對(duì)整體的影響，但不顧及這樣選擇對(duì)整體的影響， 因此一般地得到的不是最好的解。因此一般地得到的不是最好的解。 但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問(wèn)題，最小生成樹(shù)問(wèn)題等。如單源最短路經(jīng)問(wèn)題，最小生成樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能得到整體在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近最優(yōu)解的很好近似似。 9.1 Prim算法算法 9.2 貪心法的特點(diǎn)貪心法的特點(diǎn) 9.3

2、 kruskal算法算法 9.4 Dijkstra算法算法 9.5哈夫曼樹(shù)哈夫曼樹(shù)設(shè)設(shè)G =(V,E)G =(V,E)是無(wú)向連通帶權(quán)圖。是無(wú)向連通帶權(quán)圖。E E中每條邊中每條邊(v,w)(v,w)的權(quán)重為的權(quán)重為cvwcvw。如果如果G G的的子圖子圖GG是一棵是一棵包含包含G G的所有頂點(diǎn)的所有頂點(diǎn)的樹(shù)，則的樹(shù)，則稱(chēng)稱(chēng)GG為為G G的生成樹(shù)。的生成樹(shù)。在在G G的所有生成樹(shù)中，的所有生成樹(shù)中，所有邊的權(quán)重總和所有邊的權(quán)重總和最小的生最小的生成樹(shù)稱(chēng)為成樹(shù)稱(chēng)為G G的的最小生成樹(shù)最小生成樹(shù)。 圖的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用。圖的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用。 例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)

3、表示城市，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊用邊(v,w)(v,w)的權(quán)的權(quán)cvwcvw表示建立城市表示建立城市v v和城市和城市w w之之間的通信線(xiàn)路所需的費(fèi)用，則最小生成樹(shù)就給出間的通信線(xiàn)路所需的費(fèi)用，則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。設(shè)設(shè)G=(V,E)G=(V,E)是連通帶權(quán)圖，是連通帶權(quán)圖，V=1,2,nV=1,2,n。首先置首先置S=1S=1然后，只要然后，只要S S是是V V的真子集，就作如下的的真子集，就作如下的貪心選擇：貪心選擇：選取滿(mǎn)足條件選取滿(mǎn)足條件i i S S，j j V-SV-S，且，且cijcij最小的邊最小的邊將

4、頂點(diǎn)將頂點(diǎn)j j添加到添加到S S中。中。這個(gè)過(guò)程一直進(jìn)行到這個(gè)過(guò)程一直進(jìn)行到S=VS=V時(shí)為止。時(shí)為止。在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G G的一棵的一棵最最小生成樹(shù)。小生成樹(shù)。 如何有效地找出滿(mǎn)足如何有效地找出滿(mǎn)足條件條件i S,j V-S，且，且權(quán)權(quán)cij最小的邊最小的邊(i,j) 對(duì)每個(gè)不在當(dāng)前樹(shù)中的頂點(diǎn)，附加兩個(gè)標(biāo)記：對(duì)每個(gè)不在當(dāng)前樹(shù)中的頂點(diǎn)，附加兩個(gè)標(biāo)記： (樹(shù)中最近頂點(diǎn)的名稱(chēng)，相應(yīng)邊的權(quán)重樹(shù)中最近頂點(diǎn)的名稱(chēng)，相應(yīng)邊的權(quán)重) 求出距離標(biāo)記最小的點(diǎn)求出距離標(biāo)記最小的點(diǎn) 當(dāng)確定了一個(gè)加入樹(shù)中的頂點(diǎn)當(dāng)確定了一個(gè)加入樹(shù)中的頂點(diǎn)u*后后 把把u*從集合從集

5、合V-S移到樹(shù)的頂點(diǎn)集合移到樹(shù)的頂點(diǎn)集合S 更新更新V-S中各頂點(diǎn)的標(biāo)記中各頂點(diǎn)的標(biāo)記 用數(shù)學(xué)歸納法證明：用數(shù)學(xué)歸納法證明： 用用Ti i=1，,n表示表示Prim算法過(guò)程中生成的每算法過(guò)程中生成的每一棵子樹(shù)一棵子樹(shù) T1，顯然是最小生成樹(shù)的一部分，顯然是最小生成樹(shù)的一部分 設(shè)設(shè)Tk-1 是最小生成樹(shù)是最小生成樹(shù)T的一部分的一部分 證明通過(guò)證明通過(guò)Prim算法從算法從Tk-1 生成的生成的Tk也是一棵最小也是一棵最小生成樹(shù)的一部分生成樹(shù)的一部分 反證法：反證法： 設(shè)沒(méi)有一棵最小生成樹(shù)包含設(shè)沒(méi)有一棵最小生成樹(shù)包含Tk ，用，用T表示最小生表示最小生成樹(shù)成樹(shù) 則有則有ek=(v,u)權(quán)重最小，權(quán)重

6、最小，v屬于屬于Tk-1 ，u不屬于不屬于Tk-1 使使Tk-1擴(kuò)展到擴(kuò)展到Tk 因?yàn)橐驗(yàn)閑k不屬于不屬于T 如果把如果把ek加入加入T中，會(huì)形成回路。中，會(huì)形成回路。(為什么？為什么？) 該回路必定包含另一邊該回路必定包含另一邊(x,y), x屬于屬于Tk-1 ，y不屬不屬于于Tk-1 。（為什么？）。（為什么？） 如果刪除該邊得到另一棵生成樹(shù)，權(quán)重小于等如果刪除該邊得到另一棵生成樹(shù)，權(quán)重小于等于于T。（為什么？）。（為什么？） 和假設(shè)矛盾。和假設(shè)矛盾。 取決于表示圖的數(shù)據(jù)結(jié)構(gòu)取決于表示圖的數(shù)據(jù)結(jié)構(gòu) 以及表示以及表示V-S的優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu)的優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu) 可用的數(shù)據(jù)結(jié)構(gòu)：可用的數(shù)據(jù)結(jié)

7、構(gòu)： 圖圖-權(quán)重矩陣；優(yōu)先隊(duì)列權(quán)重矩陣；優(yōu)先隊(duì)列無(wú)序數(shù)組無(wú)序數(shù)組 運(yùn)行時(shí)間屬于運(yùn)行時(shí)間屬于(|V|2) 圖圖鄰接鏈表；優(yōu)先隊(duì)列鄰接鏈表；優(yōu)先隊(duì)列最小堆最小堆 運(yùn)行時(shí)間運(yùn)行時(shí)間O(|E|log|V|) 逐步給出解的各部分，逐步給出解的各部分， 在每一步在每一步“貪婪地貪婪地” 選擇最好的部分解選擇最好的部分解 最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)此問(wèn)題具有稱(chēng)此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。解的關(guān)鍵特

8、征。 貪心算法與動(dòng)態(tài)規(guī)劃算法的差異貪心算法與動(dòng)態(tài)規(guī)劃算法的差異但是，對(duì)于具有但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)的問(wèn)題應(yīng)該選用貪心的問(wèn)題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解算法還是動(dòng)態(tài)規(guī)劃算法求解? ?是否能用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題也能用貪心算是否能用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題也能用貪心算法求解法求解? ?動(dòng)態(tài)規(guī)劃算法通常以動(dòng)態(tài)規(guī)劃算法通常以自底向上自底向上的方式解各子問(wèn)題的方式解各子問(wèn)題而貪心算法則通常以而貪心算法則通常以自頂向下自頂向下的方式進(jìn)行的方式進(jìn)行以迭代的方式作出相繼的貪心選擇，每作一次貪以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。心選擇就將所求問(wèn)

9、題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。下面研究下面研究2 2個(gè)經(jīng)典的個(gè)經(jīng)典的組合優(yōu)化問(wèn)題組合優(yōu)化問(wèn)題，并以此說(shuō)明貪，并以此說(shuō)明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。 0-1背包問(wèn)題： 給定給定n n種物品和一個(gè)背包。物品種物品和一個(gè)背包。物品i i的重量是的重量是WiWi，其價(jià)值為其價(jià)值為ViVi，背包的容量為，背包的容量為C C。應(yīng)如何選擇裝入。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大背包的物品，使得裝入背包中物品的總價(jià)值最大? ?背包問(wèn)題： 與與0-10-1背包問(wèn)題類(lèi)似，所不同的是在選擇物品背包問(wèn)題類(lèi)似，所不同的是在選擇物品i i裝入背包時(shí)，裝入背包時(shí)，可以

10、選擇物品可以選擇物品i i的一部分，的一部分，而不一而不一定要全部裝入背包，定要全部裝入背包，1in1in。 在選擇裝入背包的物品時(shí)，對(duì)每種物品在選擇裝入背包的物品時(shí)，對(duì)每種物品i i只有只有2 2種種選擇，即裝入背包或不裝入背包。不能將物品選擇，即裝入背包或不裝入背包。不能將物品i i裝入裝入背包多次，也不能只裝入部分的物品背包多次，也不能只裝入部分的物品i i。這這2類(lèi)問(wèn)題都具有類(lèi)問(wèn)題都具有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但性質(zhì)，極為相似，但背包問(wèn)題可以用貪心算法求解，而背包問(wèn)題可以用貪心算法求解，而0-1背包問(wèn)題背包問(wèn)題卻不能用貪心算法求解。卻不能用貪心算法求解。 貪心法要求每次在構(gòu)

11、造部分解的時(shí)候都挑一個(gè)貪心法要求每次在構(gòu)造部分解的時(shí)候都挑一個(gè)最好的部分解。最好的部分解。 背包問(wèn)題中什么是最好的部分解背包問(wèn)題中什么是最好的部分解 單位價(jià)值單位價(jià)值最大的物品即為最好的部分解最大的物品即為最好的部分解 因此在背包問(wèn)題中因此在背包問(wèn)題中每次都挑當(dāng)前單位價(jià)值最大的每次都挑當(dāng)前單位價(jià)值最大的物品，并盡可能多的放入包中物品，并盡可能多的放入包中。 n=3 w=10,20,30 v=60,100,120 c=50 單位價(jià)值單位價(jià)值V/w=6,5,4 因此第一次挑一號(hào)物品，全部裝入因此第一次挑一號(hào)物品，全部裝入r=40,pv=60 第二次挑第二次挑2號(hào)，全部裝入號(hào)，全部裝入r=20,pv

12、=160 第三次挑第三次挑3號(hào)，部分裝入號(hào)，部分裝入r=20,pv=160+80=240 對(duì)于對(duì)于0-10-1背包問(wèn)題背包問(wèn)題，貪心選擇不一定得到，貪心選擇不一定得到最優(yōu)解。最優(yōu)解。 如：如：n=3 w=10,20,30 v=60,100,120 c=30按貪心法：選擇最有價(jià)值的放入按貪心法：選擇最有價(jià)值的放入 全部放入第全部放入第3個(gè)物品，價(jià)值個(gè)物品，價(jià)值120，但這并不是最好的，但這并不是最好的1，2 物品的放入，總價(jià)值物品的放入，總價(jià)值160因?yàn)槲锲芬催x，要么不選，盡管每次選最有價(jià)值的物品，因?yàn)槲锲芬催x，要么不選，盡管每次選最有價(jià)值的物品，卻無(wú)法保證背包單位重量的價(jià)值最高，所以總重量

13、價(jià)值卻無(wú)法保證背包單位重量的價(jià)值最高，所以總重量?jī)r(jià)值最高。最高。事實(shí)上，在考慮事實(shí)上，在考慮0-10-1背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多由此就導(dǎo)出許多互相重疊的子問(wèn)題互相重疊的子問(wèn)題。這正是該問(wèn)題可用。這正是該問(wèn)題可用動(dòng)動(dòng)態(tài)規(guī)劃算法態(tài)規(guī)劃算法求解的另一重要特征。求解的另一重要特征。實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-10-1背包問(wèn)題。背包問(wèn)題。 貪心算法以貪心算法以自頂向下自頂向下的方式進(jìn)行，以迭代

14、的方式的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。 如：如：0-10-1背包問(wèn)題背包問(wèn)題 max(i,j)max(i,j)表示在表示在i i個(gè)物品中挑個(gè)物品中挑選物品放入容量為選物品放入容量為j j的背包的最大物品價(jià)值。假的背包的最大物品價(jià)值。假設(shè)有設(shè)有n n個(gè)物品個(gè)物品 max(n,j)-maxValue(n)+ max(n-1,k)- max(n,j)-maxValue(n)+ max(n-1,k)- maxValue(n)+ maxValue(n-1)+ max(n

15、-2,q)maxValue(n)+ maxValue(n-1)+ max(n-2,q) n=3 w=30,20,10 v=120, 100,60 c=50 動(dòng)態(tài)規(guī)劃解動(dòng)態(tài)規(guī)劃解0-1背包：背包：m(i，j)是背包容量為是背包容量為j，可，可選擇物品為選擇物品為1, 2,i時(shí)的最優(yōu)值時(shí)的最優(yōu)值 注意：分析是從頂向下分析，但寫(xiě)程序時(shí)是從底注意：分析是從頂向下分析，但寫(xiě)程序時(shí)是從底向上進(jìn)行。向上進(jìn)行。m(3,50)m(2,50)m(2,40)+60m(1,50)m(1,30)+100m(1,40)+60m(1,20)+60+100給圖的所有結(jié)點(diǎn)著色，限制為給圖的所有結(jié)點(diǎn)著色，限制為一條邊的兩個(gè)端點(diǎn)不

16、能用同樣一條邊的兩個(gè)端點(diǎn)不能用同樣的顏色，的顏色，要求所使用的不同顏色的數(shù)目要求所使用的不同顏色的數(shù)目最小。最小。12345 有有5個(gè)結(jié)點(diǎn)的圖。將結(jié)點(diǎn)任意編號(hào)為個(gè)結(jié)點(diǎn)的圖。將結(jié)點(diǎn)任意編號(hào)為1至至5然然后按編號(hào)給結(jié)點(diǎn)著色，后按編號(hào)給結(jié)點(diǎn)著色， 從貪婪法觀(guān)點(diǎn)考慮，每次給盡可能多的結(jié)點(diǎn)著從貪婪法觀(guān)點(diǎn)考慮，每次給盡可能多的結(jié)點(diǎn)著色。色。 首先用顏色首先用顏色1，可給節(jié)點(diǎn)，可給節(jié)點(diǎn)1和和2著色。著色。 現(xiàn)在必須更換顏色，顏色現(xiàn)在必須更換顏色，顏色2可給結(jié)點(diǎn)可給結(jié)點(diǎn)3和和4著色。著色。 這時(shí)又不得不換顏色，顏色這時(shí)又不得不換顏色，顏色3給結(jié)點(diǎn)給結(jié)點(diǎn)5著色。著色。 但很顯然，更好的辦法只要兩種顏色，一種給但

17、很顯然，更好的辦法只要兩種顏色，一種給結(jié)點(diǎn)結(jié)點(diǎn)1、3、4著色，另一種給結(jié)點(diǎn)著色，另一種給結(jié)點(diǎn)2、5著色。著色。 (1)明確目標(biāo)函數(shù)和約束條件明確目標(biāo)函數(shù)和約束條件 (2)制定部分解結(jié)構(gòu)。制定部分解結(jié)構(gòu)。 確定如何將待解問(wèn)題分解成若干步驟確定如何將待解問(wèn)題分解成若干步驟 Prim算法：最小生成樹(shù)的子樹(shù)算法：最小生成樹(shù)的子樹(shù) 背包問(wèn)題：一部分一部分裝入背包問(wèn)題：一部分一部分裝入 (3)確定貪心策略確定貪心策略 擴(kuò)大部分解的方法，一般涉及極值選擇擴(kuò)大部分解的方法，一般涉及極值選擇 (4)確定候選集確定候選集 明確貪心的選擇范圍明確貪心的選擇范圍 (5)調(diào)整候選集調(diào)整候選集 (6)正確性證明正確性證明

18、 (1)明確目標(biāo)函數(shù)和約束條件明確目標(biāo)函數(shù)和約束條件 求最小生成樹(shù)求最小生成樹(shù) (2)制定部分解結(jié)構(gòu)。制定部分解結(jié)構(gòu)。 確定如何將待解問(wèn)題分解成若干步驟確定如何將待解問(wèn)題分解成若干步驟 該樹(shù)由一個(gè)一個(gè)的邊所組成，該樹(shù)由一個(gè)一個(gè)的邊所組成， 考慮依次選邊考慮依次選邊 (3)確定貪心策略確定貪心策略 擴(kuò)大部分解的方法，一般涉及極值選擇擴(kuò)大部分解的方法，一般涉及極值選擇 選擇一條最短的選擇一條最短的且將之加入到部分解且將之加入到部分解不形成回路不形成回路的邊。的邊。 (4)確定候選集確定候選集 明確貪心的選擇范圍明確貪心的選擇范圍 剩下的邊剩下的邊 (5)調(diào)整候選集調(diào)整候選集 (6)正確性證明正確性

19、證明 把邊按照長(zhǎng)短排序把邊按照長(zhǎng)短排序1342610530204 看上去似乎很簡(jiǎn)單看上去似乎很簡(jiǎn)單 但每次迭代時(shí)，必須要檢查新邊加入后是否會(huì)形但每次迭代時(shí)，必須要檢查新邊加入后是否會(huì)形成回路成回路 換一個(gè)解釋換一個(gè)解釋(從森林的角度從森林的角度)： 初始時(shí)，有初始時(shí)，有|V|個(gè)樹(shù)構(gòu)成的森林個(gè)樹(shù)構(gòu)成的森林 最終的森林由單獨(dú)的樹(shù)構(gòu)成最終的森林由單獨(dú)的樹(shù)構(gòu)成 每次迭代中新邊的加入等價(jià)于從圖中找到一條邊每次迭代中新邊的加入等價(jià)于從圖中找到一條邊,當(dāng)頂點(diǎn)分別屬于不同的樹(shù)時(shí)當(dāng)頂點(diǎn)分別屬于不同的樹(shù)時(shí)，選取該邊，使兩棵，選取該邊，使兩棵樹(shù)變?yōu)橐豢酶蟮臉?shù)。樹(shù)變?yōu)橐豢酶蟮臉?shù)。 通過(guò)通過(guò)union-find(并

20、查并查)算法實(shí)現(xiàn)，對(duì)兩個(gè)頂點(diǎn)是算法實(shí)現(xiàn)，對(duì)兩個(gè)頂點(diǎn)是否屬于同棵樹(shù)否屬于同棵樹(shù)(集合集合)的考察的考察 許多應(yīng)用要求把一個(gè)許多應(yīng)用要求把一個(gè)n個(gè)元素集合個(gè)元素集合S動(dòng)態(tài)劃分為動(dòng)態(tài)劃分為一系列不相交的子集。一系列不相交的子集。 對(duì)不相交子集求并集和查找的混合操作對(duì)不相交子集求并集和查找的混合操作 用用makeset(x):生成一個(gè)單元素集合生成一個(gè)單元素集合x(chóng)。設(shè)該操。設(shè)該操作對(duì)集合作對(duì)集合S的每個(gè)元素只能應(yīng)用一次。的每個(gè)元素只能應(yīng)用一次。 Find(x)：返回一個(gè)包含：返回一個(gè)包含x的子集的子集 Union(x,y)：構(gòu)造分別包含：構(gòu)造分別包含x和和y的不相交子集的的不相交子集的并集并把它添加到

21、子集的集合中，取代原來(lái)的兩并集并把它添加到子集的集合中，取代原來(lái)的兩個(gè)子集。個(gè)子集。 兩個(gè)數(shù)據(jù)結(jié)構(gòu)：兩個(gè)數(shù)據(jù)結(jié)構(gòu)： 使用一個(gè)數(shù)組，用數(shù)組的下標(biāo)表示使用一個(gè)數(shù)組，用數(shù)組的下標(biāo)表示S中的元素，數(shù)組中中的元素，數(shù)組中的值指出包含這些元素的的值指出包含這些元素的子集代表子集代表。 每一個(gè)子集用鏈表表示，表頭包含指向表頭和表尾元素每一個(gè)子集用鏈表表示，表頭包含指向表頭和表尾元素的指針和大小以及表中的元素個(gè)數(shù)的指針和大小以及表中的元素個(gè)數(shù) 對(duì)于初始集合對(duì)于初始集合S=1,2,3,4,5,6下標(biāo)下標(biāo) 123456值值 初始集合初始集合S=1,2,3,4,5,6 通過(guò)通過(guò)6次次makeset(i)產(chǎn)生產(chǎn)生6個(gè)

22、單元素子集個(gè)單元素子集 1, 2,3, 4, 5, 6 對(duì)于上述數(shù)據(jù)結(jié)構(gòu)的操作對(duì)于上述數(shù)據(jù)結(jié)構(gòu)的操作 把數(shù)組中的值設(shè)為相應(yīng)子集的代表元素把數(shù)組中的值設(shè)為相應(yīng)子集的代表元素 鏈表為鏈表為6個(gè)單節(jié)點(diǎn)鏈表個(gè)單節(jié)點(diǎn)鏈表 List1 Makeset(i)的時(shí)間效率是多少？的時(shí)間效率是多少？下標(biāo)下標(biāo) 123456值值12345611null 假設(shè)執(zhí)行假設(shè)執(zhí)行union(1,4)下標(biāo)下標(biāo)123456值值12345611null14null下標(biāo)下標(biāo)123456值值12315621null40nullnull一次一次union操作的時(shí)間操作的時(shí)間效率效率 N次次union的時(shí)間效率？的時(shí)間效率？ 一系列按大小求

23、并的操作，可證明最差效率是一系列按大小求并的操作，可證明最差效率是 O(nlogn) 用樹(shù)表示每個(gè)子集用樹(shù)表示每個(gè)子集 根元素作為子集代表根元素作為子集代表 樹(shù)中的邊從子女指向他們的父母樹(shù)中的邊從子女指向他們的父母 維護(hù)一個(gè)從集合元素到樹(shù)中節(jié)點(diǎn)的映射維護(hù)一個(gè)從集合元素到樹(shù)中節(jié)點(diǎn)的映射 如對(duì)于如對(duì)于S1=1,4,5,2 S2=3,6 union(5,6)145236145236 Makeset(x)的時(shí)間效率的時(shí)間效率(1) Union(x,y)的時(shí)間效率是的時(shí)間效率是(1) Find(x)從包含從包含x的節(jié)點(diǎn)開(kāi)始找到根，考慮最差情的節(jié)點(diǎn)開(kāi)始找到根，考慮最差情況，退化為一個(gè)況，退化為一個(gè)n節(jié)點(diǎn)的

24、鏈表節(jié)點(diǎn)的鏈表O(n) 運(yùn)行時(shí)間：運(yùn)行時(shí)間： 若采用高效的并查算法若采用高效的并查算法 則則kruskal算法的運(yùn)行時(shí)間取決于對(duì)圖中邊的權(quán)算法的運(yùn)行時(shí)間取決于對(duì)圖中邊的權(quán)重排序的時(shí)間重排序的時(shí)間 O(|E|log|E|)給定帶權(quán)有向圖給定帶權(quán)有向圖G =(V,E)G =(V,E)，其中每條邊的權(quán)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。是非負(fù)實(shí)數(shù)。給定給定V V中的一個(gè)頂點(diǎn)，稱(chēng)為中的一個(gè)頂點(diǎn)，稱(chēng)為源源。計(jì)算從源到所有其他各頂點(diǎn)的計(jì)算從源到所有其他各頂點(diǎn)的最短路徑長(zhǎng)度最短路徑長(zhǎng)度。這里路徑的長(zhǎng)度是指路徑上各邊權(quán)之和。這里路徑的長(zhǎng)度是指路徑上各邊權(quán)之和。這個(gè)問(wèn)題通常稱(chēng)為這個(gè)問(wèn)題通常稱(chēng)為單源最短路徑問(wèn)題單源最短路

25、徑問(wèn)題。1.1.算法基本思想算法基本思想DijkstraDijkstra算法是解單源最短路徑問(wèn)題的貪心算法。算法是解單源最短路徑問(wèn)題的貪心算法。對(duì)右圖中的有向圖，對(duì)右圖中的有向圖，如何考慮用貪心法獲如何考慮用貪心法獲得從源頂點(diǎn)得從源頂點(diǎn)1 1到其他頂?shù)狡渌旤c(diǎn)間最短路徑點(diǎn)間最短路徑設(shè)置頂點(diǎn)集合設(shè)置頂點(diǎn)集合S S并不斷地作并不斷地作貪心選擇貪心選擇來(lái)擴(kuò)充這個(gè)集合。來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合一個(gè)頂點(diǎn)屬于集合S S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。度已知。初始時(shí)，初始時(shí)，S S中僅含有源。中僅含有源。設(shè)設(shè)u u是是G G的某一個(gè)頂點(diǎn)，把從源到的某一個(gè)頂點(diǎn)，

26、把從源到u u且中間只經(jīng)過(guò)且中間只經(jīng)過(guò)S S中頂點(diǎn)的中頂點(diǎn)的路稱(chēng)為從源到路稱(chēng)為從源到u u的特殊路徑，并用數(shù)組的特殊路徑，并用數(shù)組distdist記錄當(dāng)前每記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。DijkstraDijkstra算法每次從算法每次從V-SV-S中取出具有最短特殊路長(zhǎng)度的頂中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)點(diǎn)u u，將，將u u添加到添加到S S中，同時(shí)對(duì)數(shù)組中，同時(shí)對(duì)數(shù)組distdist作必要的修改。作必要的修改。一旦一旦S S包含了所有包含了所有V V中頂點(diǎn)，中頂點(diǎn)，distdist就記錄了從源到所有其就記錄了從源到所有其他頂點(diǎn)之間的最短路徑長(zhǎng)度

27、。他頂點(diǎn)之間的最短路徑長(zhǎng)度。迭代Sudist2 dist3 dist4 dist5初始11- -1010maxintmaxint303010010011,21,22 210106060303010010021,2,41,2,44 4101050503030909031,2,4,31,2,4,33 3101050503030606041,2,4,3,51,2,4,3,55 51010505030306060Dijkstra算法的迭代過(guò)程： 編碼：文本中的字符賦予一串比特位編碼：文本中的字符賦予一串比特位 定長(zhǎng)編碼定長(zhǎng)編碼 變長(zhǎng)編碼：較短的比特串給常用字符變長(zhǎng)編碼：較短的比特串給常用字符 較長(zhǎng)比特

28、串給不常用字符較長(zhǎng)比特串給不常用字符 前綴碼：所有的比特串都不是另一個(gè)字符比特串前綴碼：所有的比特串都不是另一個(gè)字符比特串的前綴的前綴 考慮將字符和二叉樹(shù)的葉子聯(lián)系起來(lái)形成前綴碼考慮將字符和二叉樹(shù)的葉子聯(lián)系起來(lái)形成前綴碼哈夫曼編碼哈夫曼編碼是廣泛地用于是廣泛地用于數(shù)據(jù)文件壓縮數(shù)據(jù)文件壓縮的十分有效的編的十分有效的編碼方法。其壓縮率通常在碼方法。其壓縮率通常在20%20%90%90%之間之間 哈夫曼編碼算法用字符在文件中出現(xiàn)的哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率頻率表來(lái)建立一表來(lái)建立一個(gè)用個(gè)用0 0，1 1串表示各字符的最優(yōu)表示方式。串表示各字符的最優(yōu)表示方式。自己考慮用貪心法如何以二叉樹(shù)的組

29、織形式，自己考慮用貪心法如何以二叉樹(shù)的組織形式，關(guān)鍵字位于葉子節(jié)點(diǎn)，且關(guān)鍵字具有出現(xiàn)頻率關(guān)鍵字位于葉子節(jié)點(diǎn)，且關(guān)鍵字具有出現(xiàn)頻率使對(duì)這些關(guān)鍵字編碼后的平均長(zhǎng)度最小使對(duì)這些關(guān)鍵字編碼后的平均長(zhǎng)度最小 編碼過(guò)程：編碼過(guò)程： 初始化初始化n個(gè)字符單節(jié)點(diǎn)的樹(shù)，每個(gè)字符具有概率，個(gè)字符單節(jié)點(diǎn)的樹(shù)，每個(gè)字符具有概率，記為權(quán)重記為權(quán)重 重復(fù)下面的步驟直到剩下一棵單獨(dú)的樹(shù)。重復(fù)下面的步驟直到剩下一棵單獨(dú)的樹(shù)。 找到兩個(gè)樹(shù)權(quán)重最小，把他們作為新樹(shù)中的左右找到兩個(gè)樹(shù)權(quán)重最小，把他們作為新樹(shù)中的左右子樹(shù)。并把其權(quán)重之和作為新的權(quán)重記錄在新樹(shù)子樹(shù)。并把其權(quán)重之和作為新的權(quán)重記錄在新樹(shù)的根中。的根中。 如如a 0.35 b 0.1 c 0.2 d 0.2 _ 0.15 建樹(shù)后平均字長(zhǎng)是多少？建樹(shù)后平均字長(zhǎng)是多少？ 壓縮率壓縮率 如何獲得字符頻率？如何獲得字符頻率？ 掃描給定的文本統(tǒng)計(jì)每個(gè)字符的出現(xiàn)次數(shù)掃描給定的文本統(tǒng)計(jì)每個(gè)字符的出現(xiàn)次數(shù) 逐步給出解的各部分，逐步給出解的各部分， 在每一步在每一步“貪婪地貪婪地” 選