資源描述:
《中國(guó)數(shù)學(xué)建模-編程交流-貪婪算法_2》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、中國(guó)數(shù)學(xué)建模-編程交流-貪婪算法├數(shù)學(xué)思想├編程交流├學(xué)術(shù)雜談├EnglishFanswh-ee重登錄隱身用戶控制面板搜索風(fēng)格論壇狀態(tài)論壇展區(qū)社區(qū)服務(wù)社區(qū)休閑網(wǎng)站首頁退出>>VC++,C,Perl,Asp...編程學(xué)習(xí),算法介紹.我的收件箱(0)中國(guó)數(shù)學(xué)建?!鷮W(xué)術(shù)區(qū)→編程交流→貪婪算法您是本帖的第890個(gè)閱讀者*貼子主題:貪婪算法b等級(jí):職業(yè)俠客文章:470積分:956門派:黑客帝國(guó)注冊(cè):2003-8-28第11樓1.3.6最小耗費(fèi)生成樹在例1-2及1-3中已考察過這個(gè)問題。因?yàn)榫哂衝個(gè)頂點(diǎn)的無向網(wǎng)絡(luò)G的每個(gè)生成樹剛好具有n-1條邊,所以問題是用某種方法選擇n-1條邊使
2、它們形成G的最小生成樹。至少可以采用三種不同的貪婪策略來選擇這n-1條邊。這三種求解最小生成樹的貪婪算法策略是:Kruskal算法,Prim算法和Sollin算法。1.Kruskal算法(1)算法思想Kruskal算法每次選擇n-1條邊,所使用的貪婪準(zhǔn)則是:從剩下的邊中選擇一條不會(huì)產(chǎn)生環(huán)路的具有最小耗費(fèi)的邊加入已選擇的邊的集合中。注意到所選取的邊若產(chǎn)生環(huán)路則不可能形成一棵生成樹。Kruskal算法分e步,其中e是網(wǎng)絡(luò)中邊的數(shù)目。按耗費(fèi)遞增的順序來考慮這e條邊,每次考慮一條邊。當(dāng)考慮某條邊時(shí),若將其加入到已選邊的集合中會(huì)出現(xiàn)環(huán)路,則將其拋棄,否則,將它選入??疾靾D1-12a中
3、的網(wǎng)絡(luò)。初始時(shí)沒有任何邊被選擇。圖13-12b顯示了各節(jié)點(diǎn)的當(dāng)前狀態(tài)。邊(1,6)是最先選入的邊,它被加入到欲構(gòu)建的生成樹中,得到圖13-12c。下一步選擇邊(3,4)并將其加入樹中(如圖13-12d所示)。然后考慮邊(2,7),將它加入樹中并不會(huì)產(chǎn)生環(huán)路,于是便得到圖13-12e。下一步考慮邊(2,3)并將其加入樹中(如圖13-12f所示)。在其余還未考慮的邊中,(7,4)具有最小耗費(fèi),因此先考慮它,將它加入正在創(chuàng)建的樹中會(huì)產(chǎn)生環(huán)路,所以將其丟棄。此后將邊(5,4)加入樹中,得到的樹如圖13-12g所示。下一步考慮邊(7,5),由于會(huì)產(chǎn)生環(huán)路,將其丟棄。最后考慮邊(6,5
4、)并將其加入樹中,產(chǎn)生了一棵生成樹,其耗費(fèi)為99。圖1-13給出了Kruskal算法的偽代碼。//在一個(gè)具有n個(gè)頂點(diǎn)的網(wǎng)絡(luò)中找到一棵最小生成樹令T為所選邊的集合,初始化T=令E為網(wǎng)絡(luò)中邊的集合while(E≠)&&(
5、T
6、≠n-1){令(u,v)為E中代價(jià)最小的邊E=E-{(u,v)}//從E中刪除邊if((u,v)加入T中不會(huì)產(chǎn)生環(huán)路)將(u,v)加入T}if(
7、T
8、==n-1)T是最小耗費(fèi)生成樹else網(wǎng)絡(luò)不是互連的,不能找到生成樹圖13-13Kruskao算法的偽代碼(2)正確性證明利用前述裝載問題所用的轉(zhuǎn)化技術(shù)可以證明圖13-13的貪婪算法總能建立一棵最小耗費(fèi)生成樹
9、。需要證明以下兩點(diǎn):1)只要存在生成樹,Kruskal算法總能產(chǎn)生一棵生成樹;2)產(chǎn)生的生成樹具有最小耗費(fèi)。令G為任意加權(quán)無向圖(即G是一個(gè)無向網(wǎng)絡(luò))。從12.11.3節(jié)可知當(dāng)且僅當(dāng)一個(gè)無向圖連通時(shí)它有生成樹。而且在Kruskal算法中被拒絕(丟棄)的邊是那些會(huì)產(chǎn)生環(huán)路的邊。刪除連通圖環(huán)路中的一條邊所形成的圖仍是連通圖,因此如果G在開始時(shí)是連通的,則T與E中的邊總能形成一個(gè)連通圖。也就是若G開始時(shí)是連通的,算法不會(huì)終止于E=和
10、T
11、
12、有n-1條邊。如果T=U,則T就具有最小耗費(fèi),那么不必再證明下去。因此假設(shè)T≠U,令k(k>0)為在T中而不在U中的邊的個(gè)數(shù),當(dāng)然k也是在U中而不在T中的邊的數(shù)目。通過把U變換為T來證明U與T具有相同的耗費(fèi),這種轉(zhuǎn)化可在k步內(nèi)完成。每一步使在T而不在U中的邊的數(shù)目剛好減1。而且U的耗費(fèi)不會(huì)因?yàn)檗D(zhuǎn)化而改變。經(jīng)過k步的轉(zhuǎn)化得到的U將與原來的U具有相同的耗費(fèi),且轉(zhuǎn)化后U中的邊就是T中的邊。由此可知,T具有最小耗費(fèi)。每步轉(zhuǎn)化包括從T中移一條邊e到U中,并從U中移出一條邊f(xié)。邊e與f的選取按如下方式進(jìn)行:1)令e是在T中而不在U中的具有最小耗費(fèi)的邊。由于k>0,這條邊肯定存在。2)當(dāng)
13、把e加入U(xiǎn)時(shí),則會(huì)形成唯一的一條環(huán)路。令f為這條環(huán)路上不在T中的任意一條邊。由于T中不含環(huán)路,因此所形成的環(huán)路中至少有一條邊不在T中。從e與f的選擇方法中可以看出,V=U+{e}-{f}是一棵生成樹,且T中恰有k-1條邊不在V中出現(xiàn)?,F(xiàn)在來證明V的耗費(fèi)與U的相同。顯然,V的耗費(fèi)等于U的耗費(fèi)加上邊e的耗費(fèi)再減去邊f(xié)的耗費(fèi)。若e的耗費(fèi)比f的小,則生成樹V的耗費(fèi)比U的耗費(fèi)小,這是不可能的。如果e的耗費(fèi)高于f,在Kruskal算法中f會(huì)在e之前被考慮。由于f不在T中,Kruskal算法在考慮f能否加入T時(shí)已將f丟棄,因此f