算法分析與設(shè)計(jì)(第2版)貪心算法

1、第4章 貪心算法 貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最局部最優(yōu)優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。本章主要知識點(diǎn)： 4.1 活動安排問題 4.2 貪心算法的基本要素 4.3 最優(yōu)裝載 4.4 哈夫曼編碼 4.5 單源最短路徑 4.6 最小生成樹 4.7 多機(jī)調(diào)度問題 4.8 貪心算法的理論基礎(chǔ)4.1 活動安排問

2、題 活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個(gè)簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。問題描述：問題描述： 設(shè)有n個(gè)活動的集合E=1,2,n，其中每個(gè)活動都要求使用同一資源，如演講會場等，而在同一時(shí)間內(nèi)只能有一個(gè)活動使用這一資源。每個(gè)活動i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi，且si fi 。如果選擇了活動i，則它在半開時(shí)間區(qū)間si, fi)內(nèi)占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，

3、當(dāng)sifj或sjfi時(shí)，活動i與活動j相容。算法描述：算法描述：假定各個(gè)活動的結(jié)束時(shí)間f是由小到大排序的。public static int greedySelector(int s, int f, boolean a) int n=s.length-1; /共有n個(gè)活動申請同一個(gè)共享資源 a1=true; /首先滿足最早結(jié)束的活動的申請 int j=1; int count=1; /count個(gè)獲得資源的活動中最后一個(gè)活動是j for (int i=2;i=fj) ai=true; j=i; count+; else ai=false; return count; 由于輸入的活動以其完成時(shí)間

4、的非減序非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間具有最早完成時(shí)間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排的活動留下盡可能多的時(shí)間。即該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動。 算法greedySelector的效率極高。當(dāng)輸入的活動已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時(shí)間完成排序。 i1234567891011Si130535688212fi456789101

5、1121314 例如，例如，設(shè)待安排的11個(gè)活動的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下： 算法算法greedySelector greedySelector 的計(jì)算過程的計(jì)算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當(dāng)前正在檢查相容性的活動。 若被檢查的活動i的開始時(shí)間Si小于最近選擇的活動j的結(jié)束時(shí)間fi，則不選擇活動i，否則選擇活動i加入集合A中。 貪心算法并不總能求得問題的整體最優(yōu)解整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。

6、這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。 值得探討的是，就活動安排而言，用貪心算法是否能保證共享資源的最大利用率呢？如果要求獲得共享資源的最大利用率，如果要求獲得共享資源的最大利用率，同時(shí)滿足最多活動的資源申請，同時(shí)滿足最多活動的資源申請，將如何改進(jìn)算法將如何改進(jìn)算法greedySelector？貪心算法貪心算法greedySelector的正確性證明的正確性證明 對于活動安排問題，greedyselector算法最終確定的相容活動集A的規(guī)模最大。證明：設(shè)E=1,2,n是活動集合，由算法可知，活動1必然包含在一個(gè)最優(yōu)解中。設(shè)AE是關(guān)于E的一個(gè)最優(yōu)解，A中第一個(gè)活動是k。若k=1，則A是以貪心選擇開始的最

7、優(yōu)解；若k1，則設(shè)B=A-k1。因?yàn)閒1fk，故B是最優(yōu)。進(jìn)一步，在做出貪心選擇1后，若A是E是的最優(yōu)解，則A=A-1是E=E-1的最優(yōu)解。否則，如果能找到E的一個(gè)最優(yōu)解B，它包含比A更多的活動，則將活動1加入到B中將產(chǎn)生E的一個(gè)最優(yōu)解，它包含比A更多的活動，這與A的最優(yōu)性矛盾。因此，每一步做出的貪心選擇都將問題化簡為一個(gè)更小的與原問題具有相同性質(zhì)的子問題。4.2 貪心算法的基本要素 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。本節(jié)著重討論可以用貪心算法求解的問題的一般特征。 對于一個(gè)具體的問題，怎么知道是否可用貪心算法，一定能夠?qū)τ谝粋€(gè)具體的問題，怎么知道是否可用貪心算法，一定能夠得到該

8、問題的最優(yōu)解呢得到該問題的最優(yōu)解呢? ? 這個(gè)問題很難給予肯定的回答。這個(gè)問題很難給予肯定的回答。 但是，從許多可以用貪心算法求解的問題中看到這類問題一般但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有具有2 2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 1.貪心選擇性質(zhì)貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動態(tài)規(guī)劃算

9、法的主要區(qū)別?；疽?，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 對于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證對于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解

10、。3.貪心算法與動態(tài)規(guī)劃算法的差異貪心算法與動態(tài)規(guī)劃算法的差異 貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是是2類算法的一個(gè)共同點(diǎn)。但是，對于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該類算法的一個(gè)共同點(diǎn)。但是，對于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動態(tài)規(guī)劃算法求解選用貪心算法還是動態(tài)規(guī)劃算法求解? 是否能用動態(tài)規(guī)劃算法求解是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解的問題也能用貪心算法求解? 下面研究下面研究2個(gè)經(jīng)典的組合優(yōu)化問題，并個(gè)經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主要差別。以此說明貪心算法與動態(tài)規(guī)劃算法的主要差

11、別。0-1背包問題：背包問題： 給定給定n種物品和一個(gè)背包。物品種物品和一個(gè)背包。物品i的重量是的重量是Wi，其價(jià)值為，其價(jià)值為Vi，背，背包的容量為包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大的總價(jià)值最大? 在選擇裝入背包的物品時(shí)，對每種物品在選擇裝入背包的物品時(shí)，對每種物品i i只有只有2 2種種選擇，即裝入背包或不裝入背包。不能將物品選擇，即裝入背包或不裝入背包。不能將物品i i裝入背裝入背包多次，也不能只裝入部分的物品包多次，也不能只裝入部分的物品i i。目標(biāo)：約束條件：niiixv1maxnixCxwiniii1

12、,1 , 01背包問題：背包問題： 與與0-1背包問題類似，所不同的是在選擇物品背包問題類似，所不同的是在選擇物品i裝入背包時(shí)，可裝入背包時(shí)，可以選擇物品以選擇物品i的一部分，而不一定要全部裝入背包，的一部分，而不一定要全部裝入背包，1in。 這這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。背包問題卻不能用貪心算法求解。 目標(biāo)：約束條件：niiixv1maxnixCxwiniii1,1 , 01用貪心算法解背包問題的基本步驟：用貪心算法解背包問題的基本步驟： 首

13、先計(jì)算每種物品單位重量的價(jià)值首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇，然后，依貪心選擇策略，將盡可能多的單位重量價(jià)值最高的物品裝入背包。若將這種策略，將盡可能多的單位重量價(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過背包的容量物品全部裝入背包后，背包內(nèi)的物品總重量未超過背包的容量C，則選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包。依此策略則選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。一直地進(jìn)行下去，直到背包裝滿為止。 注意背包問題的基本特征是，可以將一件物品的一部分裝入背注意背包問題的基本特征是，可

14、以將一件物品的一部分裝入背包。從而保證了背包可以完全裝滿。包。從而保證了背包可以完全裝滿。public static float knapsack(float c,float w, float v,float x) int n=v.length; Element d = new Element n; for (int i = 0; i n; i+) di = new Element(wi,vi,i); MergeSort.mergeSort(d); int i; float opt=0; for (i=0;in;i+) xi=0; for (i=0;ic) break; xdi.i=1; op

15、t+=di.v; c-=di.w; if (in) xdi.i=c/di.w; opt+=xdi.i*di.v; return opt; 算法算法knapsackknapsack的主要計(jì)算時(shí)間在的主要計(jì)算時(shí)間在于將各種物品依其于將各種物品依其單位重量的價(jià)值從單位重量的價(jià)值從大到小排序。因此，大到小排序。因此，算法的計(jì)算時(shí)間上算法的計(jì)算時(shí)間上界為界為O O（nlognnlogn）。當(dāng)然，）。當(dāng)然，為了證明算法的正為了證明算法的正確性，還必須證明確性，還必須證明背包問題具有貪心背包問題具有貪心選擇性質(zhì)。選擇性質(zhì)。 對于對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解背包問題，貪心選擇之所以不能得到

16、最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮上，在考慮0-1背包問題時(shí)，應(yīng)比較選擇該物品和不選擇背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃導(dǎo)出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。算法求解的另一重要特征。 實(shí)際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解實(shí)

17、際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。背包問題。 示例示例w 10 20 30 v 60 100 120 123123c 500-1背包背包x 0 1 1 123獲得最大價(jià)值是獲得最大價(jià)值是220 背包背包x 1 1 2/3 123獲得最大價(jià)值是獲得最大價(jià)值是2404.3 最優(yōu)裝載 有一批集裝箱要裝上一艘載重量為有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱的輪船。其中集裝箱i的重的重量為量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。將盡可能多的集裝箱裝上輪船。1. 算法描述算法描

18、述 最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。目標(biāo)：約束條件：niiixv1maxnixCxwiniii1,1 , 01public static float loading(float c, float w, int x) int n=w.length; /集裝箱個(gè)數(shù) Element d = new Element n; for (int i = 0; i n; i+) di = new Element(wi,i); MergeSort.mergeSo

19、rt(d); /對各個(gè)集裝箱按重量由小到大排序 float opt=0; /已經(jīng)上船的集裝箱總重量 for (int i = 0; i n; i+) xi = 0; /所有集裝箱均在船下 for (int i = 0; i n & di.w = c; i+) /第i個(gè)集裝箱可上船 xdi.i = 1; /集裝箱i上船 opt+=di.w; c -= di.w; return opt;public static class element implements comparable float w; int i; public element(folat ww, int ii) w=ww

20、; i=ii; public int compareto(object x) float aw=(element) x).w; if(w1時(shí)，取時(shí)，取y1=1，yk=0，yi=xi，1in，ik，則，則 w1y1+w2y2+wnyn=w1-wk+ w1x1+w2x2+wnxn w1x1+w2x2+wnxnc因此，因此，(y1,y2,yn)是所給最優(yōu)裝載問題的可行解。是所給最優(yōu)裝載問題的可行解。 另外，由于另外，由于 y1+y2+yn=x1+x2+xn，故，故(y1,y2,yn)是滿是滿足貪心選擇性質(zhì)的最優(yōu)解。足貪心選擇性質(zhì)的最優(yōu)解。 從而我們證明了最優(yōu)裝載問題具有貪心選擇性質(zhì)。從而我們證明了最

21、優(yōu)裝載問題具有貪心選擇性質(zhì)。3. 最優(yōu)子結(jié)構(gòu)性質(zhì)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)性質(zhì)（最優(yōu)裝載問題求解算法的正確性證明）（最優(yōu)裝載問題求解算法的正確性證明） 假設(shè)假設(shè)(x1,x2,xn)是最優(yōu)裝載問題的滿足貪心選擇性質(zhì)的一個(gè)是最優(yōu)裝載問題的滿足貪心選擇性質(zhì)的一個(gè)最優(yōu)解，則最優(yōu)解，則x1=1，且，且(x2,x3,xn)是輪船載重量為是輪船載重量為c-w1，待裝集裝箱，待裝集裝箱為為(2,3,n) 時(shí)相應(yīng)最優(yōu)裝載問題的最優(yōu)解。時(shí)相應(yīng)最優(yōu)裝載問題的最優(yōu)解。4.4 哈夫曼編碼 哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在的編碼方法。其壓縮率通常在

22、20%90%之間。哈夫曼之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。串表示各字符的最優(yōu)表示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。字符以較長的編碼，可以大大縮短總碼長。 字符 a b c d e f 頻率 45 13 12 16 9 5 定長碼 000 001 010 011 100 101 變長碼 0 101 100 111 1101 11001. 前綴碼前綴碼 對每一個(gè)字符規(guī)定一個(gè)對每一個(gè)字符規(guī)定一個(gè)0,

23、1串作為其代碼，并要求任串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。這種編碼稱為一字符的代碼都不是其他字符代碼的前綴。這種編碼稱為前綴碼。前綴碼。(前綴碼的優(yōu)點(diǎn)前綴碼的優(yōu)點(diǎn)?) 編碼的前綴性質(zhì)可以使譯碼方法非常簡單。編碼的前綴性質(zhì)可以使譯碼方法非常簡單。 表示最優(yōu)前綴碼的二叉樹總是一棵二叉樹，其中不含表示最優(yōu)前綴碼的二叉樹總是一棵二叉樹，其中不含僅有一個(gè)孩子的結(jié)點(diǎn)。僅有一個(gè)孩子的結(jié)點(diǎn)。 對于給定的編碼字符集對于給定的編碼字符集C及其頻率分布及其頻率分布f，f(c)是字符是字符c的頻率，的頻率，C的一個(gè)前綴碼方案是一棵二叉樹的一個(gè)前綴碼方案是一棵二叉樹T，字符，字符c在在T中的深

24、度是中的深度是DT(c)，即，即c的前綴碼編碼長度，則的前綴碼編碼長度，則 平均碼長定義為：平均碼長定義為： 使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集字符集C的最優(yōu)前綴碼。的最優(yōu)前綴碼。)()()(cdcfTBTCc2. 構(gòu)造哈夫曼編碼構(gòu)造哈夫曼編碼 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。稱為哈夫曼編碼。 哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。 算法以算法以|C|個(gè)葉結(jié)點(diǎn)開始，執(zhí)行個(gè)

25、葉結(jié)點(diǎn)開始，執(zhí)行|C|1次的次的“合并合并”運(yùn)算后產(chǎn)生最運(yùn)算后產(chǎn)生最終所要求的樹終所要求的樹T。private class huffman implements comparable bintree tree; float weight; private huffman(bintree tt, float ww) tree=tt; weight=ww; public int compareto(object x) float xw=(huffman) x).weight; if(weightxw) return -1; if(weight=xw) return 0; return 1;publ

26、ic static bintree huffmantree(float f) int n=f.length; huffman w=new huffmann+1; bintree zero=new bintree(); for(int i=0; in; i+) bintree x=new bintree(); x.maketree=(new myinteger(i), zero, zero); wi+1=new huffman(x, fi); minheap h=new minheap(); h.initilize(w, n); for(int i=0; in; i+) huffman x=(h

27、uffman) h.removemin(); huffman y=(huffman) h.removemin(); bintree z=new bintree(); z.maketree(null, x.tree, y.tree); huffman t=new huffman(z, x.weight+y.weight); h.put(t); return (huffman) h.removemin().tree;public static bintree huffmantree(float f) int n=f.length; huffman w=new huffmann+1; bintree

28、 zero=new bintree(); for(int i=0; in; i+) bintree x=new bintree(); x.maketree=(new myinteger(i), zero, zero); wi+1=new huffman(x, fi); minheap h=new minheap(); h.initilize(w, n); for(int i=0; in; i+) huffman x=(huffman) h.removemin(); huffman y=(huffman) h.removemin(); bintree z=new bintree(); z.mak

29、etree(null, x.tree, y.tree); huffman t=new huffman(z, x.weight+y.weight); h.put(t); return (huffman) h.removemin().tree;typedef struct node float weight; struct node *lchild, *rchild; treenodetype;typedef struct float w; treenodetype *p;leafptype;int makehuffmantree(treenodetype *t, float w, int n)

30、leafptype node2n-1; int i; for(i=0; ilchild=nodei.p-rchild=NULL; for(i=0; ilchild=node0.p; noden+i.p-rchild=node1.p; if(i=n-2) break; temp=node0; node0=noden-i+1; noden-i+1=temp; temp=node1; node1=noden+i; noden+i=temp; return noden+i;3. 哈夫曼算法的正確性哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有貪要證明哈夫曼算法的正確性，只要證

31、明最優(yōu)前綴碼問題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。(1)貪心選擇性質(zhì)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)4.5 單源最短路徑 給定帶權(quán)有向圖給定帶權(quán)有向圖G =(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其他各頂中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其他各頂點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個(gè)問題通點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。常稱為單源最短路徑問題。1. 算法基本思想算法基本思想 Dijkstra

32、算法是解單源最短路徑問題的貪心算法。算法是解單源最短路徑問題的貪心算法。 設(shè)置頂點(diǎn)集合設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)并不斷地作貪心選擇來擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。初始時(shí)，當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。初始時(shí)，S中僅含有源。設(shè)中僅含有源。設(shè)u是是G的某一個(gè)頂點(diǎn)，把從源到的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過且中間只經(jīng)過S中頂中頂點(diǎn)的路稱為從源到點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所記錄當(dāng)前每個(gè)頂點(diǎn)所對應(yīng)的最短特殊路徑長度。對應(yīng)的最短特殊路徑長度。Dijkstra算

33、法每次從算法每次從V-S中取出具有最短中取出具有最短特殊路長度的頂點(diǎn)特殊路長度的頂點(diǎn)u，將，將u添加到添加到S中，同時(shí)對數(shù)組中，同時(shí)對數(shù)組dist作必要的修改。作必要的修改。一旦一旦S包含了所有包含了所有V中頂點(diǎn)，中頂點(diǎn)，dist就記錄了從源到所有其他頂點(diǎn)之間就記錄了從源到所有其他頂點(diǎn)之間的最短路徑長度。的最短路徑長度。 例如，對右圖中的有向例如，對右圖中的有向圖，應(yīng)用圖，應(yīng)用Dijkstra算法計(jì)算算法計(jì)算從源頂點(diǎn)從源頂點(diǎn)1到其他頂點(diǎn)間最到其他頂點(diǎn)間最短路徑的過程如下表所示。短路徑的過程如下表所示。迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist

34、5dist5初始初始1-10maxint301001 11,2210-160301002 21,2,4410-15030-2903 31,2,4,3310-150-330-2604 41,2,4,3,5510-150-330-260-4public static void dijstra(int v, folat a, folat dist, int prev) n=dist.length-1; if(vn) return; boolean s=new booleann+1; for(int i=1; i=n; i+) disti=avi; si=false; if(disti=float.M

35、AX-VALUE) previ=0; else previ=v; distv=0; sv=true; for(i=1; in; i+) float temp=float.MAX-VALUE; int u=v; for(int j=1; j=n; j+) if(!sj&distjtemp) u=j; temp=distj; su=true; for(j=1; j=n; j+) if(!sj&(aujfolat.MAX-VALUE) float newdist=distu+auj; if(newdistdistj) distj=newdist; prevj=u; 2. 算法的正確性

36、和計(jì)算復(fù)雜性算法的正確性和計(jì)算復(fù)雜性(1) 貪心選擇性質(zhì)貪心選擇性質(zhì)(2) 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)(3) 計(jì)算復(fù)雜性計(jì)算復(fù)雜性 對于具有對于具有n個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要算法的主循環(huán)體需要 時(shí)間。這個(gè)循環(huán)時(shí)間。這個(gè)循環(huán)需要執(zhí)行需要執(zhí)行n-1次，所以完成循環(huán)需要次，所以完成循環(huán)需要 時(shí)間。算法的其余部分所需時(shí)間。算法的其余部分所需要時(shí)間不超過要時(shí)間不超過 。)(nO)(2nO)(2nO4.6 最小代價(jià)生成樹 設(shè)設(shè)G =(V,E)是無向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。是

37、無向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊中每條邊(v,w)的權(quán)為的權(quán)為cvw。如果。如果G的子圖的子圖G是一棵包含是一棵包含G的所有頂點(diǎn)的樹，則的所有頂點(diǎn)的樹，則稱稱G為為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費(fèi)。的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費(fèi)。在在G的所有生成樹中，耗費(fèi)最小的生成樹稱為的所有生成樹中，耗費(fèi)最小的生成樹稱為G的最小生成樹。的最小生成樹。 網(wǎng)絡(luò)的最小生成樹在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)網(wǎng)絡(luò)的最小生成樹在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)的權(quán)cvw表示建立城市表示建立城市v

38、和城市和城市w之間的通信線路所需的費(fèi)用，則最小生成樹就給出了建立之間的通信線路所需的費(fèi)用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。 1.最小生成樹性質(zhì)最小生成樹性質(zhì) 用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹的有效算法。用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹的有效算法。Prim算法和算法和Kruskal算法是應(yīng)用貪心算法設(shè)計(jì)策略的例子。這算法是應(yīng)用貪心算法設(shè)計(jì)策略的例子。這2個(gè)算個(gè)算法做貪心選擇的方式不同，但它們都利用了的最小生成樹性質(zhì)：法做貪心選擇的方式不同，但它們都利用了的最小生成樹性質(zhì)： 設(shè)設(shè)G=(V,E)是連通帶權(quán)圖，是連通帶權(quán)圖，U是是V的真子集。

39、如果的真子集。如果(u,v) E，且，且u U，v V-U，且在所有這樣的邊中，且在所有這樣的邊中，(u,v)的權(quán)的權(quán)cuv最小，那么最小，那么一定存在一定存在G的一棵最小生成樹，它以的一棵最小生成樹，它以(u,v)為其中一條邊。這個(gè)性質(zhì)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為有時(shí)也稱為MST性質(zhì)。性質(zhì)。 1. 最小生成樹性質(zhì)最小生成樹性質(zhì) 用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹的有效算法。用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹的有效算法。Prim算法和算法和Kruskal算法是應(yīng)用貪心算法設(shè)計(jì)策略的例子。這算法是應(yīng)用貪心算法設(shè)計(jì)策略的例子。這2個(gè)算個(gè)算法做貪心選擇的方式不同，但它們都利用了的

40、最小生成樹性質(zhì)：法做貪心選擇的方式不同，但它們都利用了的最小生成樹性質(zhì)： 設(shè)設(shè)G=(V,E)是連通帶權(quán)圖，是連通帶權(quán)圖，U是是V的真子集。如果的真子集。如果(u,v) E，且，且u U，v V-U，且在所有這樣的邊中，且在所有這樣的邊中，(u,v)的權(quán)的權(quán)cuv最小，那么最小，那么一定存在一定存在G的一棵最小生成樹，它以的一棵最小生成樹，它以(u,v)為其中一條邊。這個(gè)性質(zhì)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為有時(shí)也稱為MST性質(zhì)。性質(zhì)。 在在MST性質(zhì)中，邊性質(zhì)中，邊(u, v)是這樣一條邊：是這樣一條邊： (u, v)=mincij i U，j V-U于是，于是，MST性質(zhì)可描述為：性質(zhì)可描述為

41、： 在兩個(gè)不相交的集合之間的各種連接方案中，具有最小代價(jià)的在兩個(gè)不相交的集合之間的各種連接方案中，具有最小代價(jià)的連接（邊）必然在某一最小代價(jià)生成樹中。連接（邊）必然在某一最小代價(jià)生成樹中。2. Prim算法算法 設(shè)設(shè)G=(V,E)是連通帶權(quán)圖，是連通帶權(quán)圖，V=1,2,n。 構(gòu)造構(gòu)造G的最小生成樹的的最小生成樹的Prim算法的基本思想是：首先置算法的基本思想是：首先置S=1，然后，只要然后，只要S是是V的真子集，就作如下的貪心選擇：選取滿足條件的真子集，就作如下的貪心選擇：選取滿足條件i S，j V-S，且，且cij最小的邊，將頂點(diǎn)最小的邊，將頂點(diǎn)j添加到添加到S中。這個(gè)過程一中。這個(gè)過程一直

42、進(jìn)行到直進(jìn)行到S=V時(shí)為止。時(shí)為止。 在這個(gè)過程中選取到的所有邊恰好構(gòu)成在這個(gè)過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。的一棵最小生成樹。 利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合容易證明，上述算法中的邊集合T始終包始終包含含G的某棵最小生成樹中的邊。因此，在的某棵最小生成樹中的邊。因此，在算法結(jié)束時(shí)，算法結(jié)束時(shí)，T中的所有邊構(gòu)成中的所有邊構(gòu)成G的一棵的一棵最小生成樹。最小生成樹。 例如，對于右圖中的帶權(quán)圖，按例如，對于右圖中的帶權(quán)圖，按Prim算法選取邊的過程如下頁圖所示。算法選取邊的過程如下頁圖所示。public static void

43、 prim(int n, floatc) float lowcost=new floatn+1; int closest=new intn+1; boolean s=new booleann+1; s1=true; /頂點(diǎn)頂點(diǎn)1進(jìn)入進(jìn)入S for(int i=2; i=n; i+) lowcosti=c1i; closesti=1; si=false; /頂點(diǎn)頂點(diǎn)i在在V-S中中 for(int i=1; in; i+) float min=float.MAX-VALUE; int j=1; for(int k=2; k=n; k+) /在在S和和V-S之間求小之間求小 if(lowcostkmin)&(!sk) min=lowcostk; j=k; system.out.println(j+”,”+closestj); sj=true; /頂點(diǎn)頂點(diǎn)j進(jìn)入進(jìn)入S for(int k=2; k=n; k+) if(cjklowcostk)&(!sk) lowcostk=cjk; closestk=j; lowcostk是S中各頂點(diǎn)到頂點(diǎn)k的最小邊的權(quán),由于j的進(jìn)入可能要修改 在上述在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出