ACM程序設計基礎之貪心法PPT教學課件

1、 貪心法在解決問題的策略上目光短淺，只根據(jù)當貪心法在解決問題的策略上目光短淺，只根據(jù)當前已有的信息就做出選擇，而且一旦做出了選擇，前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結果，這個選擇都不會改變。換言不管將來有什么結果，這個選擇都不會改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。擇只是在某種意義上的局部最優(yōu)。 這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（Optimal Solution），但通常能獲得近似最優(yōu)解），但通常能獲得近似最優(yōu)解（Near-Optimal

2、 Solution）。）。1 貪心法的設計思想貪心法的設計思想 第1頁/共54頁例：用貪心法求解付款問題。例：用貪心法求解付款問題。假設有面值為假設有面值為5元、元、2元、元、1元、元、5角、角、2角、角、1角的貨幣，需角的貨幣，需要找給顧客要找給顧客4元元6角現(xiàn)金，為使付出角現(xiàn)金，為使付出的貨幣的數(shù)量最少，首的貨幣的數(shù)量最少，首先選出先選出1張面值不超過張面值不超過4元元6角的最大面值的貨幣，即角的最大面值的貨幣，即2元，元，再選出再選出1張面值不超過張面值不超過2元元6角的最大面值的貨幣，即角的最大面值的貨幣，即2元，元，再選出再選出1張面值不超過張面值不超過6角的最大面值的貨幣，即角的最

3、大面值的貨幣，即5角，再選角，再選出出1張面值不超過張面值不超過1角的最大面值的貨幣，即角的最大面值的貨幣，即1角，總共付出角，總共付出4張貨幣。張貨幣。第2頁/共54頁 在付款問題每一步的貪心選擇中，在不超過應付款金額的條件下，只選擇面值最大的貨幣，而不去考慮在后面看來這種選擇是否合理，而且它還不會改變決定：一旦選出了一張貨幣，就永遠選定。付款問題的貪心選擇策略是盡可能使付出的貨幣最快地滿足支付要求，其目的是使付出的貨幣張數(shù)最慢地增加，這正體現(xiàn)了貪心法的設計思想。第3頁/共54頁貪心法求解的問題的特征：貪心法求解的問題的特征：（1）最優(yōu)子結構性質 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱

4、此當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質，也稱此問題滿足最優(yōu)性原理。問題具有最優(yōu)子結構性質，也稱此問題滿足最優(yōu)性原理。（2）貪心選擇性質 所謂貪心選擇性質是指問題的整體最優(yōu)解可以通過一所謂貪心選擇性質是指問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來得到。系列局部最優(yōu)的選擇，即貪心選擇來得到。v 動態(tài)規(guī)劃法通常以自底向上的方式求解各個子問題，而貪心法則通常以自頂向下的方式做出一系列的貪心選擇。第4頁/共54頁2 貪心法的求解過程貪心法的求解過程 用貪心法求解問題應該考慮如下幾個方面：（1）候選集合C：為了構造問題的解決方案，有一個候選集合C作為問題的可

5、能解，即問題的最終解均取自于候選集合C。例如，在付款問題中，各種面值的貨幣構成候選集合。（2）解集合S：隨著貪心選擇的進行，解集合S不斷擴展，直到構成一個滿足問題的完整解。例如，在付款問題中，已付出的貨幣構成解集合。第5頁/共54頁 （3）解決函數(shù)solution：檢查解集合S是否構成問題的完整解。例如，在付款問題中，解決函數(shù)是已付出的貨幣金額恰好等于應付款。 （4）選擇函數(shù)select：即貪心策略，這是貪心法的關鍵，它指出哪個候選對象最有希望構成問題的解，選擇函數(shù)通常和目標函數(shù)有關。例如，在付款問題中，貪心策略就是在候選集合中選擇面值最大的貨幣。 （5）可行函數(shù)feasible：檢查解集合中

6、加入一個候選對象是否可行，即解集合擴展后是否滿足約束條件。例如，在付款問題中，可行函數(shù)是每一步選擇的貨幣和已付出的貨幣相加不超過應付款。 第6頁/共54頁貪心法的一般過程Greedy(C) /C是問題的輸入集合即候選集合 S= ; /初始解集合為空集 while (not solution(S) /集合S沒有構成問題的一個解 x=select(C); /在候選集合C中做貪心選擇 if feasible(S, x) /判斷集合S中加入x后的解是否可行 S=S+x; C=C-x; return S;第7頁/共54頁例例1 1、 活動安排問題活動安排問題 活動安排問題就是要在所給的活動集合中選出最大

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

8、jfi時，活動i與活動j相容。第9頁/共54頁例例1 1、 活動安排問題活動安排問題在下面所給出的解活動安排問題的貪心算法greedySelectorgreedySelector : int greedySelector(int s, int f, bool a) int n=strlen(s)-1; a1=true; int j=1; int count=1; for (int i=2;i=f j) ai=true; j=i; count+; else ai=false; return count; 各活動的起始時間和結各活動的起始時間和結束時間存儲于數(shù)組束時間存儲于數(shù)組s s和和f f中且

9、按結束時間的非減中且按結束時間的非減序排列序排列 第10頁/共54頁例例1 1、 活動安排問題活動安排問題 由于輸入的活動以其完成時間的非減序非減序排列，所以算法greedySelectorgreedySelector每次總是選擇具有最早具有最早完成時間完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩使剩余的可安排時間段極大化余的可安排時間段極大化，以便安排盡可能多的相容活動。 算法greedySelectorgreedySelector的效率極高。當輸入的活動已按結束時間的非減序排列，算法只需O(n)O(n)

10、的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)O(nlogn)的時間重排。 第11頁/共54頁例例1 1、活動安排問題、活動安排問題 例：例：設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下：i12345678910 11Si130535688212fi4567891011121314第12頁/共54頁例例1 1、 活動安排問題活動安排問題 算法算法greedySelector greedySelector 的計算過程的計算過程如左圖所示。圖中每行相應于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白

11、長條表示的活動是當前正在檢查相容性的活動。第13頁/共54頁例例1 1、 活動安排問題活動安排問題 若被檢查的活動i的開始時間Si小于最近選擇的活動j的結束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。 貪心算法并不總能求得問題的整體最優(yōu)解整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結論可以用數(shù)學歸納法證明。第14頁/共54頁3 3、貪心算法的基本要素、貪心算法的基本要素 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。 但是，從許

12、多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質：貪心選擇性質貪心選擇性質和最優(yōu)子結構性質最優(yōu)子結構性質。 第15頁/共54頁3 3 貪心算法的基本要素貪心算法的基本要素1.1.貪心選擇性質貪心選擇性質 所謂貪心選擇性質貪心選擇性質是指所求問題的整體最優(yōu)解整體最優(yōu)解可以通過一系列局部最優(yōu)局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 動態(tài)規(guī)劃算法通常以自底向上自底向上的方式解各子問題，而貪心算法則通常以自頂向下自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 對于一

13、個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。第16頁/共54頁3 3 貪心算法的基本要素貪心算法的基本要素2.2.最優(yōu)子結構性質最優(yōu)子結構性質 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。 第17頁/共54頁第18頁/共54頁貪心與動態(tài)規(guī)劃 【例】在一個NM的方格陣中，每一格子賦予一個數(shù)（即為權）。規(guī)定每次移動時只能向上或向右。現(xiàn)試找出一條路徑，使其從左下角至右上角所經(jīng)過的權之和最大。 貪心：1 3 4 6 動規(guī)：1 2 10 6 局

14、部最優(yōu)解VS全局最優(yōu)解3461210第19頁/共54頁例例2、 背包問題背包問題 給定給定n種物品和一個容量為種物品和一個容量為C的背包，物的背包，物品品i的重量是的重量是wi，其價值為，其價值為vi，背包問題是如何，背包問題是如何選擇裝入背包的物品，使得裝入背包中物品的選擇裝入背包的物品，使得裝入背包中物品的總價值最大總價值最大? 第20頁/共54頁 0-10-1背包問題：背包問題： 給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大? 在選擇裝入背包的物品時，對每種物品在選擇裝入背包的物品時，對每種物品i i只

15、有只有2 2種選擇，即種選擇，即裝入背包或不裝入背包。不能將物品裝入背包或不裝入背包。不能將物品i i裝入背包多次，也不能只裝入背包多次，也不能只裝入部分的物品裝入部分的物品i i。第21頁/共54頁 背包問題：背包問題： 與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品可以選擇物品i i的一部分的一部分，而不一定要全部裝入背包，1in。 這2類問題都具有最優(yōu)子結構最優(yōu)子結構性質，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。 第22頁/共54頁 于是，背包問題歸結為尋找一個滿足約束條于是，背包問題歸結為尋找一個滿足約束條件式件式7.1，并使

16、目標函數(shù)式，并使目標函數(shù)式7.2達到最大的解向量達到最大的解向量X=(x1, x2, , xn)。設xi表示物品i裝入背包的情況，根據(jù)問題的要求，有如下約束條件和目標函數(shù)： )1 (101nixCxwiniii（式（式7.1）niiixv1max（式（式7.2）第23頁/共54頁至少有三種看似合理的貪心策略： （1）選擇價值最大的物品，因為這可以盡可能快地增加背包的總價值。但是，雖然每一步選擇獲得了背包價值的極大增長，但背包容量卻可能消耗得太快，使得裝入背包的物品個數(shù)減少，從而不能保證目標函數(shù)達到最大。 （2）選擇重量最輕的物品，因為這可以裝入盡可能多的物品，從而增加背包的總價值。但是，雖然每

17、一步選擇使背包的容量消耗得慢了，但背包的價值卻沒能保證迅速增長，從而不能保證目標函數(shù)達到最大。 （3）選擇單位重量價值最大的物品，在背包價值增長和背包容量消耗兩者之間尋找平衡。第24頁/共54頁 應用第三種貪心策略，每次從物品集合中選擇單位重量價值最大的物品，如果其重量小于背包容量，就可以把它裝入，并將背包容量減去該物品的重量，然后我們就面臨了一個最優(yōu)子問題它同樣是背包問題，只不過背包容量減少了，物品集合減少了。因此背包問題具有最優(yōu)子結構性質。 第25頁/共54頁60 120 50 背包 180 190 200(a) 三個物品及背包 (b) 貪心策略1 (c) 貪心策略2 (d) 貪心策略3

18、50 30 10 20 20 3020/30 20 1010/20 30 10例如，有3個物品，其重量分別是20, 30, 10，價值分別為60, 120, 50，背包的容量為50，應用三種貪心策略裝入背包的物品和獲得的價值如圖所示。第26頁/共54頁 設背包容量為C，共有n個物品，物品重量存放在數(shù)組wn中，價值存放在數(shù)組vn中，問題的解存放在數(shù)組xn中。 1改變數(shù)組改變數(shù)組w和和v的排列順序，使其按單位重量價值的排列順序，使其按單位重量價值vi/wi降序排列；降序排列；2將數(shù)組將數(shù)組xn初始化為初始化為0； /初始化解向量初始化解向量3i=1; 循環(huán)直到循環(huán)直到(wiC) 1 xi=1; /

19、將第將第i個物品放入背包個物品放入背包 2 C=C-wi; 3 i+;5. xi=C/wi;算法的時間主要消耗在將各種物品依其單位重量的價值從算法的時間主要消耗在將各種物品依其單位重量的價值從大到小排序。因此，其時間復雜性為大到小排序。因此，其時間復雜性為O(nlog2n)。第27頁/共54頁#include #include #include #include #include #include #include #include #include #include using namespace std;using namespace std;struct thingstruct thin

20、g double wi,vi,vwi; double wi,vi,vwi;an10000;an10000;int cmp(thing i,thing j)int cmp(thing i,thing j) return i.vwi j.vwi; return i.vwi j.vwi; int main()int main() int n,c; int n,c; while(cinnc)while(cinnc) for(int i=0;in;i+) for(int i=0;iani.wiani.vi; cinani.wiani.vi; ani.vwi=ani.vi/ani.wi; ani.vwi=

21、ani.vi/ani.wi; sort(an,an+n,cmp); sort(an,an+n,cmp); int step=0; int step=0; double cost=0; double cost=0; for(int i=0;in;i+) for(int i=0;i=c) if(step=c) break; break; if(c-step)=ani.wi) if(c-step)=ani.wi) step += ani.wi; step += ani.wi; cost += ani.vi; cost += ani.vi; else else cost += ani.vwi cost

22、 += ani.vwi* *(c-(c-step);step); step=c; step=c; coutcostendl; coutcostendl; return 0; return 0; 第28頁/共54頁 對于0-10-1背包問題背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。由此就導出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法求解的另一重要特征。 實際上也是如此，動態(tài)規(guī)劃算法的確可

23、以有效地解0-1背包問題。 第29頁/共54頁#include #include #include #include #include #include #include #include #include #include using namespace std;using namespace std;struct thingstruct thing int wi,vi; int wi,vi;an10000;an10000; intint dpdp10000;10000;intint main() main() intint n,cn,c; ; while( while(cincinnc)n

24、c) for( for(intint i i=0;i=0;ianani i.wiwianani i.vi;.vi; memsetmemset(dp,0,sizeof(dp,0,sizeof(dpdp);); for( for(intint i i=0;i=0;i=an=ani i.wi;jwi;j-)-) dpdpj=max(j=max(dpdpj,j,dpdpj-anj-ani i.wiwi+an+ani i.vi);.vi); coutcoutdpdpccendlendl; ; return 0; return 0; 第30頁/共54頁 例例3 3 最優(yōu)裝載最優(yōu)裝載 有一批集裝箱要裝上一艘

25、載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。1.1.算法描述算法描述最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁。 第31頁/共54頁最優(yōu)裝載最優(yōu)裝載2.2.貪心選擇性質貪心選擇性質 可以證明最優(yōu)裝載問題具有貪心選擇性質。 3.3.最優(yōu)子結構性質最優(yōu)子結構性質最優(yōu)裝載問題具有最優(yōu)子結構性質。由最優(yōu)裝載問題的貪心選擇性質和最優(yōu)子結構性質，容易證明算法loadingloading的正確性。算法loadingloading的主要計算量在于將集裝箱依其重量從小到

26、大排序，故算法所需的計算時間為 O(nlogn)O(nlogn)。 第32頁/共54頁 例例4 4、 單源最短路徑單源最短路徑給定帶權有向圖G =(V,E)，其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱為源源?，F(xiàn)在要計算從源到所有其他各頂點的最短最短路長度路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短單源最短路徑問題路徑問題。1.1.算法基本思想算法基本思想( (迪科斯徹算法) )Dijkstra算法是解單源最短路徑問題的貪心算法。第33頁/共54頁 例例4 4、 單源最短路徑單源最短路徑其基本思想基本思想是，設置頂點集合S并不斷地作貪心選擇貪心選擇來擴充這個集合

27、。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其他頂點之間的最短路徑長度。第34頁/共54頁 例例4 4、 單源最短路徑單源最短路徑例如例如，對右圖中的有向圖，應用Dijkstra算法計算從源頂點1到其他頂點間最短路徑的過程列在下頁的表中。第35頁/共54頁

28、例例4 4、 單源最短路徑單源最短路徑迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5初始初始1-10maxint301001 11,221060301002 21,2,44105030903 31,2,4,33105030604 41,2,4,3,5510503060Dijkstra算法的迭代過程： 第36頁/共54頁 4 4 單源最短路徑單源最短路徑2.2.算法的正確性和計算復雜性算法的正確性和計算復雜性(1)貪心選擇性質(2)最優(yōu)子結構性質(3)計算復雜性對于具有n個頂點和e條邊的帶權有向圖，如果用帶權鄰接矩陣表示這個圖，那么Di

29、jkstra算法的主循環(huán)體需要 時間。這個循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要 時間。算法的其余部分所需要時間不超過 。)(nO)(2nO)(2nO第37頁/共54頁 5 5 最小生成樹最小生成樹 設G =(V,E)是無向連通帶權圖，即一個網(wǎng)絡網(wǎng)絡。E中每條邊(v,w)的權為cvw。如果G的子圖G是一棵包含G的所有頂點的樹，則稱G為G的生成樹。生成樹上各邊權的總和稱為該生成樹的耗費耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹最小生成樹。網(wǎng)絡的最小生成樹在實際中有廣泛應用。例如例如，在設計通信網(wǎng)絡時，用圖的頂點表示城市，用邊(v,w)的權cvw表示建立城市v和城市w之間的通信線

30、路所需的費用，則最小生成樹就給出了建立通信網(wǎng)絡的最經(jīng)濟的方案。 第38頁/共54頁 6 6 最小生成樹最小生成樹1.1.最小生成樹性質最小生成樹性質用貪心算法設計策略可以設計出構造最小生成樹的有效算法。本節(jié)介紹的構造最小生成樹的PrimPrim算法算法和KruskalKruskal算法算法都可以看作是應用貪心算法設計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質最小生成樹性質：設G=(V,E)是連通帶權圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊

31、。這個性質有時也稱為MSTMST性質性質。 第39頁/共54頁 5 5 最小生成樹最小生成樹2.Prim2.Prim算法算法 設G=(V,E)是連通帶權圖，V=1,2,n。構造G的最小生成樹的Prim算法的基本思想基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的貪心選擇貪心選擇：選取滿足條件iS，jV-S，且cij最小的邊，將頂點j添加到S中。這個過程一直進行到S=V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹最小生成樹。 第40頁/共54頁 5 5 最小生成樹最小生成樹利用最小生成樹性質和數(shù)學歸納法容易證明，上述算法中的邊集合邊集合T T始始終包含終包含G G的

32、某棵最小生成的某棵最小生成樹中的邊樹中的邊。因此，在算法結束時，T中的所有邊構成G的一棵最小生成樹。 例如例如，對于右圖中的帶權圖，按PrimPrim算法算法選取邊的過程如下頁圖所示。第41頁/共54頁 5 5 最小生成樹最小生成樹第42頁/共54頁 5 5 最小生成樹最小生成樹在上述Prim算法中，還應當考慮如何有效地找出如何有效地找出滿足條件滿足條件i i S,jS,j V-SV-S，且權，且權cijcij最小的邊最小的邊(i,j)(i,j)。實現(xiàn)這個目的的較簡單的辦法是設置2個數(shù)組closest和lowcost。在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點j，然后

33、根據(jù)數(shù)組closest選取邊(j,closestj)，最后將j添加到S中，并對closest和lowcost作必要的修改。用這個辦法實現(xiàn)的Prim算法所需的計算時間計算時間為 )(2nO第43頁/共54頁 5 5 最小生成樹最小生成樹3.Kruskal3.Kruskal算法算法Kruskal算法構造G的最小生成樹的基本思想基本思想是，首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權從小到大排序。然后從第一條邊開始，依邊權遞增的順序查看每一條邊，并按下述方法連接2個不同的連通分支：當查看到第k條邊(v,w)時，如果端點v和w分別是當前2個不同的連通分支T1和T2中的頂點時，就用邊(v,w

34、)將T1和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看第k+1條邊。這個過程一直進行到只剩下一個連通分支時為止。 第44頁/共54頁 5 5 最小生成樹最小生成樹例如，例如，對前面的連通帶權圖，按Kruskal算法順序得到的最小生成樹上的邊如下圖所示。第45頁/共54頁 5 5 最小生成樹最小生成樹關于集合的一些基本運算集合的一些基本運算可用于實現(xiàn)Kruskal算法。 按權的遞增順序查看等價于對優(yōu)先隊列優(yōu)先隊列執(zhí)行removeMinremoveMin運算?？梢杂枚讯褜崿F(xiàn)這個優(yōu)先隊列。 對一個由連通分支組成的集合不斷進行修改，需要用到抽象

35、數(shù)據(jù)類型并查集并查集UnionFindUnionFind所支持的基本運算。當圖的邊數(shù)為e時，Kruskal算法所需的計算時間計算時間是 。當 時，Kruskal算法比Prim算法差，但當 時，Kruskal算法卻比Prim算法好得多。)log(eeO)(2ne)(2noe 第46頁/共54頁 鍵盤輸入一個高精度的正整數(shù)鍵盤輸入一個高精度的正整數(shù)N N，去掉其中任意，去掉其中任意S S個數(shù)字后個數(shù)字后剩下的數(shù)字按原左右次序將組成一個新的正整數(shù)。編程對給剩下的數(shù)字按原左右次序將組成一個新的正整數(shù)。編程對給定的定的N N和和S S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。，尋找一種方案使得剩下的數(shù)

36、字組成的新數(shù)最小。 輸入數(shù)據(jù)均不需判錯。輸出應包括所去掉的數(shù)字的位置輸入數(shù)據(jù)均不需判錯。輸出應包括所去掉的數(shù)字的位置和組成的新的正整數(shù)和組成的新的正整數(shù) 例6、刪數(shù)游戲第47頁/共54頁 問題分析問題分析 在位數(shù)固定的前提下，讓高位的數(shù)字盡量小其值就較小，依據(jù)在位數(shù)固定的前提下，讓高位的數(shù)字盡量小其值就較小，依據(jù)此貪婪策略就可以解決這個問題。此貪婪策略就可以解決這個問題。 怎么樣根據(jù)貪婪策略刪除數(shù)字呢？總目標是刪除高位較大的數(shù)怎么樣根據(jù)貪婪策略刪除數(shù)字呢？總目標是刪除高位較大的數(shù)字，具體地相鄰兩位比較若高位比低位大則刪除高位。我們通過字，具體地相鄰兩位比較若高位比低位大則刪除高位。我們通過“枚舉歸納枚舉歸納”設計算法的細節(jié)，看一個實例（設計算法的細節(jié)，看一個實例（s=3） ： n1=“