貪心算法實(shí)用PPT課件PPT課件

1、1u Greedy算法的基本思想算法的基本思想V0V12V13V21V11V23V22V3467241435121第1頁/共42頁2 求解最優(yōu)化問題求解最優(yōu)化問題我們可能會(huì)想到用我們可能會(huì)想到用動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法，但有時(shí)用但有時(shí)用貪心算法貪心算法會(huì)更簡(jiǎn)單、有效。會(huì)更簡(jiǎn)單、有效。例子例子：背包問題背包問題：給定給定n種物品和一個(gè)背包種物品和一個(gè)背包。物品物品i的的重量是重量是wi，其價(jià)值為其價(jià)值為vi，背包的容量為背包的容量為W。應(yīng)如。應(yīng)如何選擇物品裝入背包，使得裝入背包中的物品何選擇物品裝入背包，使得裝入背包中的物品的總價(jià)值最大的總價(jià)值最大？在選擇物品在選擇物品i裝入背包時(shí)，可以裝入背包時(shí)，

2、可以選擇物品選擇物品i的一部分的一部分, ,而不一定要全部裝入背包。而不一定要全部裝入背包。貪心策略貪心策略：每次選每次選vi/wi最大的物品最大的物品i放進(jìn)包中。放進(jìn)包中。 背包問題具有背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)，它可以用它可以用動(dòng)態(tài)動(dòng)態(tài)規(guī)劃算法規(guī)劃算法來解來解。 但是，用但是，用貪心算法貪心算法更簡(jiǎn)單，解題效率更高更簡(jiǎn)單，解題效率更高。第2頁/共42頁3 貪心算法貪心算法總是總是做出在做出在當(dāng)前看來當(dāng)前看來是最好的選擇是最好的選擇。也。也就是說貪心算法就是說貪心算法并不從整體最優(yōu)上加以考慮并不從整體最優(yōu)上加以考慮，所以，所以貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解。貪心算法不

3、是對(duì)所有問題都能得到整體最優(yōu)解。0-1背包問題背包問題：給定給定n種物品和一個(gè)背包種物品和一個(gè)背包。物品物品i的的重量是重量是wi，價(jià)值為價(jià)值為vi，背包的容量為背包的容量為C。如何選擇物如何選擇物品裝入背包，使得裝入背包中的物品的總價(jià)值最大品裝入背包，使得裝入背包中的物品的總價(jià)值最大？對(duì)每種物品對(duì)每種物品i只有兩種選擇，要么裝入，要么不裝入，只有兩種選擇，要么裝入，要么不裝入，不能將物品不能將物品i裝入背包多次裝入背包多次，也不能只裝入物品也不能只裝入物品i i的的一部分。因此，該問題稱為一部分。因此，該問題稱為0-1背包問題背包問題。 對(duì)于對(duì)于0-1背包問題，貪心選擇之所以不能得到最優(yōu)背包

4、問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樗鼰o法保證最終將背包裝滿，部分背包空解是因?yàn)樗鼰o法保證最終將背包裝滿，部分背包空間的閑置使每公斤背包空間所具有的價(jià)值降低了間的閑置使每公斤背包空間所具有的價(jià)值降低了。 例：背包容量背包容量C=10，n=3 ， 三個(gè)物品的重量三個(gè)物品的重量W=3,5,7， 三個(gè)物品的價(jià)值三個(gè)物品的價(jià)值V=9,10,12 。貪心法裝入背包的貪心法裝入背包的 價(jià)值為價(jià)值為1919。但最優(yōu)值是但最優(yōu)值是21 21 。第3頁/共42頁4 雖然貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣的許多問題雖然貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣的許多問題能能

5、產(chǎn)產(chǎn)生整體最優(yōu)解。如生整體最優(yōu)解。如：?jiǎn)卧醋疃搪方?jīng)問題單源最短路經(jīng)問題, , 最小生成樹問題最小生成樹問題，哈夫曼編碼問題哈夫曼編碼問題等。等。 在一些情況下，即使貪心算法在一些情況下，即使貪心算法不能不能得到整體最優(yōu)解，但卻是最優(yōu)解的很好的得到整體最優(yōu)解，但卻是最優(yōu)解的很好的近似解近似解。如如：在下圖中求從在下圖中求從V0到到V3的最短路徑問題。的最短路徑問題。 V0V12V13V21V11V23V22V3467241435121第4頁/共42頁5u Greedy算法產(chǎn)生優(yōu)化解的條件算法產(chǎn)生優(yōu)化解的條件 Optimal substructure（最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)） Greedy-

6、choice property（貪心選擇性質(zhì)貪心選擇性質(zhì)）定義定義1 1（最優(yōu)子結(jié)構(gòu)性質(zhì)）（最優(yōu)子結(jié)構(gòu)性質(zhì)） 若一個(gè)問題的優(yōu)化解包括它的子問題的優(yōu)化解，則稱若一個(gè)問題的優(yōu)化解包括它的子問題的優(yōu)化解，則稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。定義定義2 2（greedy選擇性質(zhì)）選擇性質(zhì)） 若一個(gè)優(yōu)化問題的全局優(yōu)化解可通過局部?jī)?yōu)化選擇若一個(gè)優(yōu)化問題的全局優(yōu)化解可通過局部?jī)?yōu)化選擇得到，則該問題稱為具有得到，則該問題稱為具有g(shù)reedy選擇性質(zhì)。選擇性質(zhì)。第5頁/共42頁6u Greedy算法正確性證明方法算法正確性證明方法第6頁/共42頁7u 與動(dòng)態(tài)規(guī)劃方法的比較與動(dòng)態(tài)規(guī)劃方法的比較 動(dòng)態(tài)規(guī)

7、劃動(dòng)態(tài)規(guī)劃：每一步作一個(gè)選擇每一步作一個(gè)選擇依賴于子問題的解。依賴于子問題的解。 貪心方法貪心方法：每一步作一個(gè)選擇每一步作一個(gè)選擇不依賴于子問題的解。不依賴于子問題的解。 可用動(dòng)態(tài)規(guī)劃方法的條件可用動(dòng)態(tài)規(guī)劃方法的條件： 最優(yōu)子結(jié)構(gòu)性質(zhì)；子問題的重疊性質(zhì)；子問題空間小。最優(yōu)子結(jié)構(gòu)性質(zhì)；子問題的重疊性質(zhì)；子問題空間小。 可用貪心方法的條件可用貪心方法的條件： 最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)。 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃：自底向上求解；自底向上求解； 貪心方法貪心方法： 自頂向下求解。自頂向下求解。 可用貪心法時(shí)，動(dòng)態(tài)規(guī)劃方法可能不適用；可用貪心法時(shí)，動(dòng)態(tài)規(guī)劃方法可能不適用； 可

8、用動(dòng)態(tài)規(guī)劃方法時(shí)，貪心法可能不適用?？捎脛?dòng)態(tài)規(guī)劃方法時(shí)，貪心法可能不適用。第7頁/共42頁8問題的定義問題的定義 活動(dòng)安排問題是可以用貪心算法有效求解的一個(gè)很好的例子?；顒?dòng)安排問題是可以用貪心算法有效求解的一個(gè)很好的例子。 活動(dòng)活動(dòng) 設(shè)有設(shè)有n個(gè)活動(dòng)的集合個(gè)活動(dòng)的集合E其中每個(gè)活其中每個(gè)活動(dòng)都要求動(dòng)都要求使用同一資源使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只允許一個(gè)活動(dòng)使用這一資源。每個(gè)活動(dòng)間內(nèi)只允許一個(gè)活動(dòng)使用這一資源。每個(gè)活動(dòng)i都有都有一個(gè)要求使用該資源的起始時(shí)間一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間和一個(gè)結(jié)束時(shí)間fi，且且si fi。如果選擇了活動(dòng)如果

9、選擇了活動(dòng)i，則它在半開的時(shí)間區(qū)間，則它在半開的時(shí)間區(qū)間( (si，fi內(nèi)占用資源。內(nèi)占用資源。第8頁/共42頁9相容活動(dòng)相容活動(dòng) 若區(qū)間若區(qū)間si，fi與區(qū)間與區(qū)間sj，fj不相交，則稱活動(dòng)不相交，則稱活動(dòng)i與活動(dòng)與活動(dòng)j是相容的。也就是說，是相容的。也就是說，當(dāng)當(dāng)sj fi或或si fj時(shí)，活動(dòng)時(shí)，活動(dòng)i與活動(dòng)與活動(dòng)j是相容是相容。問題定義問題定義 活動(dòng)安排問題是要在所給的活動(dòng)集合中選出活動(dòng)安排問題是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合最大的相容活動(dòng)子集合。sifisjfjtsjfifjsifjsi相容！相容！相容！相容！不相容！不相容！第9頁/共42頁10算法設(shè)計(jì)算法設(shè)計(jì)貪心思想

10、：貪心思想： 為了選擇最多的相容活動(dòng)，每次選為了選擇最多的相容活動(dòng)，每次選 fi 最小的最小的活動(dòng)，使剩余的可安排時(shí)間段極大化，以活動(dòng)，使剩余的可安排時(shí)間段極大化，以便接待盡可能多的相容活動(dòng)。便接待盡可能多的相容活動(dòng)。輸入輸入： 各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組sn和和fn中，且按結(jié)束時(shí)間的非減序中，且按結(jié)束時(shí)間的非減序：f1f2fn排列。排列。輸出輸出： 最大相容活動(dòng)子集最大相容活動(dòng)子集A。第10頁/共42頁11例例：設(shè)待安排的設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下按結(jié)束時(shí)間的非減序排列如下： 按貪

11、心算法計(jì)算按貪心算法計(jì)算最大相容活動(dòng)子集最大相容活動(dòng)子集A的的過程如下過程如下: : A=1 與活動(dòng)與活動(dòng)1相容的剩余活動(dòng)子集為相容的剩余活動(dòng)子集為： 4，6，7，8，9，11A=1,4 與活動(dòng)與活動(dòng)4相容的剩余活動(dòng)子集為相容的剩余活動(dòng)子集為： 8，9，11A=1,4,8 與活動(dòng)與活動(dòng)8相容的剩余活動(dòng)子集為相容的剩余活動(dòng)子集為： 11A=1,4,8,11 與活動(dòng)與活動(dòng)11相容的剩余活動(dòng)子集為相容的剩余活動(dòng)子集為： i1234567891011si130535688212fi 456789101112 1314第11頁/共42頁12算法：算法：Template void GreedySelect

12、or (int n, Type s , Type f , bool A ) A1 = true; int j=1; / j用以記錄最近一次加入到A中的活動(dòng)。 for (int i=2; i= fj） Ai=true; j=i; else Ai= false; 算法時(shí)間復(fù)雜性分析：算法時(shí)間復(fù)雜性分析：當(dāng)結(jié)束時(shí)間已排序當(dāng)結(jié)束時(shí)間已排序，T(n)=(n)。當(dāng)結(jié)束時(shí)間未排序當(dāng)結(jié)束時(shí)間未排序，T(n)=(n)+(n log n)。i1234567891011si130535688212fi 4567891011121314第12頁/共42頁13算法正確性證明算法正確性證明1.1.證明問題具有優(yōu)化子結(jié)構(gòu)證

13、明問題具有優(yōu)化子結(jié)構(gòu)引理引理1 1 設(shè)設(shè)S=1,2,n是是n個(gè)活動(dòng)集合個(gè)活動(dòng)集合，sj，fj是是活動(dòng)的起活動(dòng)的起 止時(shí)間，且止時(shí)間，且f1f2fn，則則S的活動(dòng)選的活動(dòng)選擇問題的擇問題的某個(gè)優(yōu)化解包括活動(dòng)某個(gè)優(yōu)化解包括活動(dòng)1。證：證：設(shè)設(shè)A是一個(gè)優(yōu)化解，按結(jié)束時(shí)間排序是一個(gè)優(yōu)化解，按結(jié)束時(shí)間排序A中活動(dòng)，中活動(dòng)， 設(shè)其第一個(gè)活動(dòng)為設(shè)其第一個(gè)活動(dòng)為k，第二個(gè)活動(dòng)為，第二個(gè)活動(dòng)為j。 如果如果k=1，引理成立，引理成立。 如果如果k1，令令B=A- -k1 ， 由于由于A中的活動(dòng)相容中的活動(dòng)相容， f1fksj， B中的活動(dòng)相容中的活動(dòng)相容。 | |B|=|=|A| |，B是一個(gè)優(yōu)化解，且包含活動(dòng)

14、是一個(gè)優(yōu)化解，且包含活動(dòng)1。i1234567891011si130535688212fi 4567891011121314第13頁/共42頁14定理定理1 1 設(shè)設(shè)S=1,2,n是是n個(gè)活動(dòng)集合個(gè)活動(dòng)集合，sj，fj是活動(dòng)是活動(dòng)j (1jn)的起止時(shí)間，且的起止時(shí)間，且f1f2fn。設(shè)設(shè)A是是S的的調(diào)度問題的一個(gè)調(diào)度問題的一個(gè)優(yōu)化解優(yōu)化解，且包括活動(dòng)且包括活動(dòng)1，則則A2=A-1是是S2= jS | sjf1 的調(diào)度問題的的調(diào)度問題的優(yōu)化解優(yōu)化解。證：證：顯然，顯然，A2中的活動(dòng)是相容的，且中的活動(dòng)是相容的，且A2是是S2的子集的子集。 A2是是S2的解。的解。 我們僅需證明我們僅需證明A2是

15、最大的是最大的。若不然若不然， 存在一個(gè)存在一個(gè)S2的活動(dòng)選擇問題的優(yōu)化解的活動(dòng)選擇問題的優(yōu)化解B2，|B2|A2| 令令B=1B2，對(duì)于對(duì)于jS2，sjf1，B中活動(dòng)相容中活動(dòng)相容。 B是是S的一個(gè)解的一個(gè)解。 由于由于|A|=|A2|+1，|B|=|B2|+1 ， |B| |A|，與與|A|最大矛盾最大矛盾。 定理定理1說明活動(dòng)選擇問題具有說明活動(dòng)選擇問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。第14頁/共42頁15 2. 2.證明問題具有貪心選擇性證明問題具有貪心選擇性定理定理2 2 設(shè)設(shè)S=1,2,n是是n個(gè)活動(dòng)集合個(gè)活動(dòng)集合，sj，fj是活動(dòng)是活動(dòng)j的起止時(shí)間，且的起止時(shí)間，且f1f2fn

16、。li是是Si = jS | sjfl i-1中具有最小結(jié)束時(shí)間中具有最小結(jié)束時(shí)間fli的活動(dòng)的活動(dòng)( (設(shè)設(shè)l0=0，f0=0) )。設(shè)設(shè)A是是S的包含活動(dòng)的包含活動(dòng)1的的優(yōu)化解優(yōu)化解，則則A= 。證：證：對(duì)對(duì)|A|作歸納法（即對(duì)貪心選擇的次數(shù)作歸納法）作歸納法（即對(duì)貪心選擇的次數(shù)作歸納法）。 當(dāng)當(dāng)|A|=1時(shí)，由引理時(shí)，由引理1，命題成立命題成立； 設(shè)設(shè)|A|k時(shí)時(shí)，命題成立命題成立； 當(dāng)當(dāng)|A|=k時(shí)時(shí)，A=1A2, 由定理由定理1，A2是是S= jS | sjf1 的優(yōu)化解的優(yōu)化解。 由歸納假設(shè)由歸納假設(shè)，A2= 。于是于是，A= 。 定理定理2說明活動(dòng)選擇問題具有說明活動(dòng)選擇問題具有

17、貪心選擇性貪心選擇性。 k k1 1i iililk k2 2i i k k1 1i iil第15頁/共42頁163. 3. GREEDY_ACTIVITY-SELECTOR算法是按定理算法是按定理2的Greedy選擇性進(jìn)行局部選擇性進(jìn)行局部?jī)?yōu)化選擇的優(yōu)化選擇的。 因此因此GREEDY_ACTIVITY_SELECTOR算法對(duì)于活動(dòng)安排問題來說，總能求算法對(duì)于活動(dòng)安排問題來說，總能求得整體最優(yōu)解得整體最優(yōu)解 (即相容活動(dòng)集合即相容活動(dòng)集合A的規(guī)模最大的規(guī)模最大)。第16頁/共42頁17其中其中，xi0,1, 1in (nin (n是集裝箱總數(shù)是集裝箱總數(shù)) )， 問題定義問題定義 有一批集裝箱

18、要裝上一艘載重量為有一批集裝箱要裝上一艘載重量為c的輪船的輪船。其中其中，集裝箱集裝箱i的重量為的重量為Wi。最優(yōu)裝載問題要求確定最優(yōu)裝載問題要求確定，在裝載在裝載體積不受限制的情況下，應(yīng)如何裝載才能體積不受限制的情況下，應(yīng)如何裝載才能將盡可能將盡可能多多的集裝箱裝上輪船的集裝箱裝上輪船。該問題可形式化地描述為該問題可形式化地描述為:n n1 1i ii ix xmaxcn n1 1i ii ii ix xw wii表表示示裝裝入入集集裝裝箱箱表表示示不不裝裝入入集集裝裝箱箱1 10 0ix三三、最優(yōu)裝載問題最優(yōu)裝載問題(Loading Problem)第17頁/共42頁18算法算法基本思想基

19、本思想： 用重量用重量最輕者先裝最輕者先裝的貪心策略。由此可產(chǎn)生裝載問題的最優(yōu)解。的貪心策略。由此可產(chǎn)生裝載問題的最優(yōu)解。輸入輸入： n個(gè)集裝箱的重量，輪船的載重量個(gè)集裝箱的重量，輪船的載重量c。輸出輸出： 裝進(jìn)輪船的集裝箱編號(hào)裝進(jìn)輪船的集裝箱編號(hào)(最多的集裝箱最多的集裝箱）。第18頁/共42頁19算法：算法：Template void Loading(int x , Type w , Type c, int n) int *t= new intn+1; Sort(w, t, n); /數(shù)組元素?cái)?shù)組元素ti ti 存放重量第存放重量第i i輕的集裝箱號(hào)。輕的集裝箱號(hào)。 for ( int i=

20、1;i=n; i+) xi=0; / / 數(shù)組元素?cái)?shù)組元素xi=0 xi=0表示不裝入集裝箱表示不裝入集裝箱i i。 for ( int i=1; i=n &wti= c; i+) xti =1; c- = wti; 算法復(fù)雜性：算法復(fù)雜性：算法的主要計(jì)算量是將集裝箱依其重量從小到大排序算法的主要計(jì)算量是將集裝箱依其重量從小到大排序， T(n)=O(n log n)+ O(n) = O(n log n)第19頁/共42頁20問題定義問題定義二進(jìn)制字符編碼二進(jìn)制字符編碼： 每個(gè)字符用一個(gè)二進(jìn)制每個(gè)字符用一個(gè)二進(jìn)制0,1串來表示串來表示。固定長(zhǎng)編碼：固定長(zhǎng)編碼： 每個(gè)字符都用等長(zhǎng)的每個(gè)字符

21、都用等長(zhǎng)的0,1串來表示串來表示?？勺冮L(zhǎng)編碼：可變長(zhǎng)編碼： 經(jīng)常出現(xiàn)的字符用短碼，不經(jīng)常出現(xiàn)的字符用長(zhǎng)碼。經(jīng)常出現(xiàn)的字符用短碼，不經(jīng)常出現(xiàn)的字符用長(zhǎng)碼。前綴編碼：前綴編碼： 無任何字符的編碼是另一個(gè)字符編碼的前綴無任何字符的編碼是另一個(gè)字符編碼的前綴。第20頁/共42頁21前綴碼的哈夫曼樹表示前綴碼的哈夫曼樹表示 每個(gè)字符的編碼每個(gè)字符的編碼: :從根到對(duì)應(yīng)的葉路徑上的從根到對(duì)應(yīng)的葉路徑上的0,1串串。100A: 4555012530C: 12B: 13E: 9D: 1614F: 511110000葉結(jié)點(diǎn)：葉結(jié)點(diǎn)：用字符及其出用字符及其出現(xiàn)頻數(shù)標(biāo)記?，F(xiàn)頻數(shù)標(biāo)記。邊標(biāo)記：邊標(biāo)記：一個(gè)結(jié)點(diǎn)的左側(cè)一

22、個(gè)結(jié)點(diǎn)的左側(cè)邊標(biāo)記為邊標(biāo)記為0 0, 右側(cè)右側(cè)邊標(biāo)記為邊標(biāo)記為1 1。內(nèi)結(jié)點(diǎn)：內(nèi)結(jié)點(diǎn)：其子樹的其子樹的葉子頻數(shù)葉子頻數(shù)和。和。第21頁/共42頁22問題定義問題定義 給定編碼字符集給定編碼字符集C及其概率分布及其概率分布f，即，即C中任意字符中任意字符c以概率以概率f(c)在數(shù)據(jù)文件中出現(xiàn)。在數(shù)據(jù)文件中出現(xiàn)。C的一個(gè)前綴編碼方的一個(gè)前綴編碼方案對(duì)應(yīng)一棵二叉樹案對(duì)應(yīng)一棵二叉樹T。字符字符c在樹在樹T中的深度記為中的深度記為dT(c)。dT(c)也是字符也是字符c的前綴碼長(zhǎng)的前綴碼長(zhǎng)。該該編碼方案的編碼方案的平均碼長(zhǎng)定義為平均碼長(zhǎng)定義為： 。目標(biāo)目標(biāo)：求出使平均碼長(zhǎng)最小的前綴編碼方案求出使平均碼長(zhǎng)

23、最小的前綴編碼方案哈夫曼編碼哈夫曼編碼。)(B(T)cdTC Cc cf f( (c c) )第22頁/共42頁23 構(gòu)造最優(yōu)前綴碼的哈夫曼算法構(gòu)造最優(yōu)前綴碼的哈夫曼算法基本思想：基本思想： 循環(huán)地選擇具有循環(huán)地選擇具有最低頻率的最低頻率的兩個(gè)根結(jié)點(diǎn)，生成一棵子樹，直到形成樹兩個(gè)根結(jié)點(diǎn)，生成一棵子樹，直到形成樹。輸入：輸入： 字符表字符表C= c1, c2,cn, 及其相應(yīng)的及其相應(yīng)的權(quán)權(quán)。輸出：輸出： Huffman樹樹。第23頁/共42頁24算法：算法：HUFFMAN(C) / / 使用堆操作實(shí)現(xiàn)使用堆操作實(shí)現(xiàn) n=|C|; Q=Initialize（C）; / / 初始建堆。初始建堆。優(yōu)

24、先隊(duì)列優(yōu)先隊(duì)列用堆來實(shí)現(xiàn)用堆來實(shí)現(xiàn) 。 for(i=1; ilchild=x; z-rchild=y; z-f = x-f + y-f; Insert(z, Q); /堆操作堆操作 return(DeleteMin(Q); 初始建堆需初始建堆需O(n)時(shí)間時(shí)間循環(huán)循環(huán)n-1次次每個(gè)堆操作需每個(gè)堆操作需O(logn)時(shí)間時(shí)間算法的時(shí)間復(fù)雜性算法的時(shí)間復(fù)雜性：T(n)= O(n)+ O(nlog n) = O(nlog n) 輸入：輸入：C=a,b,c,d，f(C)=6,5,3,7第24頁/共42頁25算法復(fù)雜性分析：算法復(fù)雜性分析： 設(shè)優(yōu)先隊(duì)列設(shè)優(yōu)先隊(duì)列Q由一個(gè)堆實(shí)現(xiàn)由一個(gè)堆實(shí)現(xiàn)。 第二步使用堆

25、排序的初始建堆算法實(shí)現(xiàn)，需第二步使用堆排序的初始建堆算法實(shí)現(xiàn)，需 要的時(shí)間為要的時(shí)間為O(n); 每個(gè)堆操作要求每個(gè)堆操作要求O(log n), 循環(huán)循環(huán)n-1次次，需要需要O(nlog n); T(n)= O(n)+ O(nlog n)= O(nlog n).第25頁/共42頁26哈夫曼算法的正確性證明哈夫曼算法的正確性證明1 1證明具有最優(yōu)子結(jié)構(gòu)性質(zhì)證明具有最優(yōu)子結(jié)構(gòu)性質(zhì)定理定理1 1（最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)）：設(shè)設(shè)T是字母表是字母表C的哈夫曼樹的哈夫曼樹， ，f(c)是是c在文件中出現(xiàn)的概在文件中出現(xiàn)的概率率。設(shè)設(shè)x，y是是T中任意兩個(gè)相鄰葉結(jié)點(diǎn)中任意兩個(gè)相鄰葉結(jié)點(diǎn)，z是它們的父結(jié)點(diǎn)是它們

26、的父結(jié)點(diǎn)，則則z作為概率為作為概率為f(z)=f(x)+f(y)的字符的字符，T1=T-x,y表示了字母表表示了字母表C1=C-x,yz的哈夫曼樹的哈夫曼樹。CcbycT f(x)f(b)f(c) x f(y)bzT1cf(x)+f(y)f(b)f(c)第26頁/共42頁27bzT1cf(x)+f(y)f(b)f(c)往證往證：z作為概率為f(z)=f(x)+f(y)的字符， T1=T-x,y表示了字母表C1=C-x,yz的哈夫曼樹。C Cc cT Tf f( (c c) )d d( (T T) )(cB)()()()()(ydyfxdxfvTTyyx,x,- -C Cv vT Tf(v)df

27、(v)d)()()()(11zdyfxfvTy y x x, ,- -C Cv vT T1 1f f( (v v) )d d)()()()()(yfxfzdzfvT1y y x x, ,- -C Cv vT T1 1f f( (v v) )d d)()()(yfxfw C Cw wT T1 1f f( (w w) )d d1證證: :bycT f(x)f(b)f(c) x f(y)()()(yfxfTB1z第27頁/共42頁28往證往證：z作為概率為作為概率為f(z)=f(x)+f(y)的字符的字符， T1=T-x,y表示表示了字母表了字母表C1=C-x,yz的哈夫曼樹的哈夫曼樹。bycT f

28、(x)f(b)f(c) x f(y) 因?yàn)橐驗(yàn)閦在在C1中是一個(gè)字符，它必是中是一個(gè)字符，它必是T2中中的葉子。把結(jié)點(diǎn)的葉子。把結(jié)點(diǎn)x，y加入加入T2，作為作為z的子結(jié)點(diǎn)，則得到的子結(jié)點(diǎn)，則得到C的一個(gè)前綴樹的一個(gè)前綴樹T。反證：反證：若若T1不不是是C1的優(yōu)化前綴編碼樹，的優(yōu)化前綴編碼樹，則存在則存在T2，其葉子在其葉子在C1中，使中，使B(T2)B(T1)。zbf(x)+f(y)cf(b)f(c)T2同理可證：同理可證：B(T)= B(T2)+ f(x) +f(y) 與與T是優(yōu)化的是優(yōu)化的( (即即HUFFMAN樹樹) )矛盾矛盾，故故T1是優(yōu)化的是優(yōu)化的。 B(T) B(T)zbyuT

29、f(x)f(b) f(c) x f(y)cbzT1cf(x)+f(y)f(b)f(c)第28頁/共42頁292 2證明具有貪心選擇性證明具有貪心選擇性定理定理2 2（Greedy選擇性選擇性）: : 設(shè)設(shè)C是字母表是字母表， , , f(c)是是c在文件中出現(xiàn)的頻率在文件中出現(xiàn)的頻率。設(shè)設(shè)x,y是是C中具有最小概率的兩個(gè)字符，中具有最小概率的兩個(gè)字符，則存在一個(gè)則存在一個(gè)C的優(yōu)化前的優(yōu)化前綴樹綴樹, ,在該優(yōu)化前綴樹中在該優(yōu)化前綴樹中x,y具有最大深度，其編碼長(zhǎng)度相具有最大深度，其編碼長(zhǎng)度相同，僅在最末一位不同同，僅在最末一位不同。證證：設(shè)設(shè)T是是C的優(yōu)化前綴樹，且的優(yōu)化前綴樹，且b,c是具有

30、最大深度的兩個(gè)是具有最大深度的兩個(gè)字符字符。不失一般性，設(shè)不失一般性，設(shè)f(b)f(c)，f(x)f(y).因因x與與y是具有最低概率的字符是具有最低概率的字符, ,所以所以f(b)f(x), ,f(c)f(y).從從T構(gòu)造構(gòu)造T1，交換交換T的的b和和x; ;從從T1構(gòu)造構(gòu)造T2, ,交換交換T1的的c和和y; ;往證往證，T2是最大前綴樹是最大前綴樹。C Cc c B(T)-B(T1) =(c)f(c)d(c)f(c)dCcT1CcT= f(x)dT(x)+ f(b)dT(b)-( f(x)dT1(x)+ f(b)dT1(b)= f(x)dT(x) + f(b)dT(b) - f(x)dT

31、(b) - f(b)dT (x)= (f(b)- f(x)(dT (b)- dT(x)因?yàn)閒(b)f(x)，dT (b)dT(x) （因?yàn)閎的深度最大）所以B(T)-B(T1)0。byuT f(x)f(b) f(c) x f(y)cxyuT1f(b)f(x)f(c) b f(y)cxcuT2f(b)f(x)f(y) b f(c)y第29頁/共42頁30同理可證，同理可證，B(T1)B(T2)。于是于是B(T)B(T2)。又由于又由于T是優(yōu)化的，所以是優(yōu)化的，所以B(T)B(T2)。于是于是B(T)=B(T2). 所以所以T2是是C的最優(yōu)前綴編碼樹的最優(yōu)前綴編碼樹。 在在T2中中，x,y具有相同

32、長(zhǎng)度編碼，而且僅最后一位不具有相同長(zhǎng)度編碼，而且僅最后一位不同同（且在該優(yōu)化前綴樹中具有最大深度且在該優(yōu)化前綴樹中具有最大深度）。3 3哈夫曼算法是按定理哈夫曼算法是按定理2的的Greedy選擇性進(jìn)行局部?jī)?yōu)化選擇的。選擇性進(jìn)行局部?jī)?yōu)化選擇的。 因此哈夫曼算法是正確的，即因此哈夫曼算法是正確的，即HUFFMAN(C)產(chǎn)生產(chǎn)生C的一個(gè)最優(yōu)前綴碼。的一個(gè)最優(yōu)前綴碼。xyuT1f(b)f(x) f(c) b f(y)cxcuT2f(b)f(x) f(y) b f(c)ybyuT f(x)f(b) f(c) x f(y)c第30頁/共42頁311 1. 單源最短路徑問題單源最短路徑問題 對(duì)于給定的又向網(wǎng)

33、絡(luò)對(duì)于給定的又向網(wǎng)絡(luò)G=（V,E）及單個(gè)源點(diǎn)及單個(gè)源點(diǎn)v, ,求從求從v到到G中其余各頂點(diǎn)的最短路徑中其余各頂點(diǎn)的最短路徑。2.2.單源最短路徑問題的單源最短路徑問題的Dijkstra算法算法貪心策略？貪心策略？第31頁/共42頁32Dijkstra算法算法（貪心法貪心法）基本思想基本思想： 按路徑長(zhǎng)度遞增的次序產(chǎn)生諸頂點(diǎn)的按路徑長(zhǎng)度遞增的次序產(chǎn)生諸頂點(diǎn)的最短路徑最短路徑。求解過程求解過程： 設(shè)集合設(shè)集合S存放已求出其最短路徑的頂點(diǎn)，則尚未確定存放已求出其最短路徑的頂點(diǎn)，則尚未確定最短路徑的頂點(diǎn)集合是最短路徑的頂點(diǎn)集合是V-S，逐步擴(kuò)充集合逐步擴(kuò)充集合S ，直到直到S=V。 約定約定S中頂點(diǎn)涂

34、成中頂點(diǎn)涂成紅色紅色，V-S中頂點(diǎn)涂成中頂點(diǎn)涂成藍(lán)色藍(lán)色。 算法初始時(shí)，紅點(diǎn)集中只有源點(diǎn)；以后的每一步都算法初始時(shí)，紅點(diǎn)集中只有源點(diǎn)；以后的每一步都從從當(dāng)前藍(lán)點(diǎn)集中選擇一個(gè)最短路徑最小的藍(lán)點(diǎn)當(dāng)前藍(lán)點(diǎn)集中選擇一個(gè)最短路徑最小的藍(lán)點(diǎn)來擴(kuò)充紅點(diǎn)來擴(kuò)充紅點(diǎn)集集；算法直到圖中的所有頂點(diǎn)都涂成紅色時(shí)終止算法直到圖中的所有頂點(diǎn)都涂成紅色時(shí)終止。 Dijkstra算法的動(dòng)態(tài)執(zhí)行情況算法的動(dòng)態(tài)執(zhí)行情況12534101006020503010有向網(wǎng)絡(luò)有向網(wǎng)絡(luò)G=(V,E)G=(V,E)4循環(huán)循環(huán)初始化初始化紅點(diǎn)集紅點(diǎn)集 S 4 D1 D2 D3 D4 D5 20 0 60 14，3 20 0 3024，3，5 2

35、0 0 30 34，3，5，1 20 0 3044，3，5，1，2 20 0 30 3512第32頁/共42頁33問題定義問題定義生成樹：生成樹： 設(shè)設(shè)G=(V, E)是一個(gè)邊帶權(quán)的無向連通圖是一個(gè)邊帶權(quán)的無向連通圖。G的生成樹是的生成樹是無向樹無向樹S=(V,T), 。以下用以下用T表示表示S。如果如果W: E實(shí)數(shù)實(shí)數(shù)是是G的權(quán)函數(shù)的權(quán)函數(shù)，T的權(quán)值定為的權(quán)值定為 。最小生成樹：最小生成樹： G的最小生成樹是的最小生成樹是W(T)最小的最小的G的生成樹的生成樹。問題定義：?jiǎn)栴}定義： 給定邊帶權(quán)的無向連通圖給定邊帶權(quán)的無向連通圖G=(V, E)，求出求出G的最小生成的最小生成樹。樹。Tv)(u

36、,vu,W W(T)(E ET T 第33頁/共42頁34 1254634653126123456123TE= TV=1TE=(1,3) TV=1,3 TE=(1,3),(3,6) TV=1,3,6 TE=(1,3),(3,6),(4,6) TV=1,3,6,4 TE=(1,3),(3,6), (4,6),(2,3) TV=1,3,6,4,2 TE=(1,3),(3,6), (4,6),(2,3),(2,5) TV=1,3,6,4,2,5 在構(gòu)造最小生成樹的過程中頂點(diǎn)集與邊集的變化情況在構(gòu)造最小生成樹的過程中頂點(diǎn)集與邊集的變化情況：1.1.構(gòu)造最小生成樹的方法構(gòu)造最小生成樹的方法Prim算法算

37、法 對(duì)下圖所示的連通網(wǎng)絡(luò)對(duì)下圖所示的連通網(wǎng)絡(luò)G，用，用普里姆普里姆(Prim)算法算法求求G的的最小生成樹最小生成樹T 。在算法執(zhí)行過程中，依次加入在算法執(zhí)行過程中，依次加入T的邊集的邊集TE和頂點(diǎn)集和頂點(diǎn)集TV？ 55457第34頁/共42頁35 1254631416185691911262112345656111416TE= TE=(2,3)TE=(2,3),(3,4)TE=(2,3),(3,4),(4,6)TE=(2,3),(3,4), (4，6),(1,5)TE=(2,3),(3,4), (4，6),(1,5),(1,2)在構(gòu)造最小生成樹中的過程中邊集的變化情況在構(gòu)造最小生成樹中的過程

38、中邊集的變化情況：2.2.構(gòu)造最小生成樹的方法構(gòu)造最小生成樹的方法Kruskal算法算法對(duì)下圖所示的連通網(wǎng)絡(luò)對(duì)下圖所示的連通網(wǎng)絡(luò)G，用，用克魯斯卡爾克魯斯卡爾( (Kruskal) )算法算法求求G的最小生成樹的最小生成樹T 。 在算法執(zhí)行過程中，依次加入在算法執(zhí)行過程中，依次加入T的的邊集邊集TE中的邊中的邊？ 第35頁/共42頁36 Disjoint Sets）并查集并查集是一種抽象數(shù)據(jù)類型。是一種抽象數(shù)據(jù)類型。并查集并查集的數(shù)學(xué)模型是若干個(gè)不相交的動(dòng)態(tài)集合的數(shù)學(xué)模型是若干個(gè)不相交的動(dòng)態(tài)集合的集合的集合S=A，B，支持以下的運(yùn)算支持以下的運(yùn)算：MakeSet(A,x): 構(gòu)造一個(gè)取名為構(gòu)造

39、一個(gè)取名為A的集合的集合， 它只包含一個(gè)元素它只包含一個(gè)元素x; ;Union(A,B): 將集合將集合A和和B合并合并, , 其結(jié)果取名為其結(jié)果取名為A 或或B; ;Find-Set(x): 找出元素找出元素x所在集合所在集合, , 并返回該集合的名字。并返回該集合的名字。第36頁/共42頁37并查集的一個(gè)并查集的一個(gè)應(yīng)用應(yīng)用是確定集合上的等價(jià)關(guān)系是確定集合上的等價(jià)關(guān)系。例例：S=10,20,30,40,50,60,70，要求作出要求作出S的等價(jià)劃的等價(jià)劃分滿足給定的等價(jià)性條件分滿足給定的等價(jià)性條件： 1 1020，5060，3040，1040。 先將先將S的每一個(gè)元素看成一個(gè)等價(jià)類，然后順序地的每一個(gè)元素看成一個(gè)等價(jià)類，然后順序地處理所列的條件處理所列的條件。沒處理完一個(gè)條件，所得到的相沒處理完一個(gè)條件，所得到的相應(yīng)的等價(jià)類列表如下應(yīng)的等價(jià)類列表如下：1020 10,2030,