>VC++,C,Perl,Asp...編程學(xué)習(xí),算法介紹.我的收件箱">

中國(guó)數(shù)學(xué)建模-編程交流-貪婪算法_2

ID:1223943

大?。?3.50 KB

頁數(shù):15頁

時(shí)間:2017-11-08

中國(guó)數(shù)學(xué)建模-編程交流-貪婪算法_2_第1頁
中國(guó)數(shù)學(xué)建模-編程交流-貪婪算法_2_第2頁
中國(guó)數(shù)學(xué)建模-編程交流-貪婪算法_2_第3頁
中國(guó)數(shù)學(xué)建模-編程交流-貪婪算法_2_第4頁
中國(guó)數(shù)學(xué)建模-編程交流-貪婪算法_2_第5頁
資源描述:

《中國(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

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無此問題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。
关闭