低代價(jià)最短路徑樹快速算法的時(shí)間復(fù)雜度研究.pdf_第1頁(yè)
已閱讀1頁(yè),還剩54頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、多播是一種群組通信的手段,要求將信息從一個(gè)數(shù)據(jù)源同時(shí)傳送到多個(gè)目的地。構(gòu)造多播樹是解決多播路由問題的常用方法。有3種不同類型的多播樹:基于數(shù)據(jù)源的樹、Steiner樹和基于中心的樹。這些不同類型的樹中具有代表性的是基于源的最短路徑樹(shortest path tree,簡(jiǎn)稱SPT)和Steiner樹。SPT最主要的優(yōu)點(diǎn)就是它使得源結(jié)點(diǎn)到每個(gè)目的結(jié)點(diǎn)的時(shí)延最小;而Steiner樹則使得所有連接的消耗總和最小,最大限度地共享帶寬,如果網(wǎng)絡(luò)

2、中除源結(jié)點(diǎn)外的每個(gè)結(jié)點(diǎn)都是目的結(jié)點(diǎn),這棵樹就是最小生成樹(minimum spanning tree,簡(jiǎn)稱MST)。 在給定的網(wǎng)絡(luò)中,構(gòu)造從源結(jié)點(diǎn)到其他目的結(jié)點(diǎn)的多播樹,幾乎不可能使它同時(shí)達(dá)到最小延時(shí)和最小總消耗,因此,一些學(xué)者研究構(gòu)造滿足指定時(shí)延限制的Steiner樹。當(dāng)網(wǎng)絡(luò)變得足夠大時(shí),從源結(jié)點(diǎn)到一些目的結(jié)點(diǎn)的最短路徑常常不只一條,而由此構(gòu)成的SPT也就不是惟一的。在眾多的SPT中,每棵樹的總消耗也不盡相同。因而,有必要研究

3、如何降低SPT的總消耗問題。 最優(yōu)最短路徑樹算法SBPT(shortest best path tree),是通過在構(gòu)造SPT的過程中采用貪心策略選擇最短路徑,使所構(gòu)造的生成樹的總消耗得以降低。該算法的時(shí)間復(fù)雜度較高而不適合大型網(wǎng)絡(luò)求解。驅(qū)動(dòng)多播路由算法DDMC(destination—driven multicasting),是通過使目的結(jié)點(diǎn)之間盡可能共享路徑來降低多播樹的總消耗。驅(qū)動(dòng)最短路徑樹算法DDSP (destinat

4、ion-drivenshortest path)采用Dijkstra算法路徑遞增的基本思想,并結(jié)合DDMC算法目的結(jié)點(diǎn)共享路徑的方法,當(dāng)源結(jié)點(diǎn)到某結(jié)點(diǎn)的最短路徑不惟一時(shí),總是選擇一條與其他目的結(jié)點(diǎn)的共享路徑最長(zhǎng)的最短路徑,從而降低所構(gòu)造SPT的總消耗。它因而適合計(jì)算目的結(jié)點(diǎn)數(shù)較多的最短路徑樹。 低代價(jià)最短路徑樹的快速算法FLSPT(fast low—cost shortest path tree)是在DDSP算法的基礎(chǔ)上進(jìn)行改進(jìn)

5、,它構(gòu)造的多播樹與DDSP算法構(gòu)造的多播樹具有相同性能,但時(shí)間復(fù)雜度比DDSP算法要低。 仔細(xì)研究FLSPT算法可以發(fā)現(xiàn),在Q集合中選擇了距源點(diǎn)S的路徑最小的點(diǎn)u后,如果不把該u點(diǎn)從Q集合中刪除掉,就會(huì)出現(xiàn)死循環(huán);同時(shí),如果u是目的結(jié)點(diǎn),如果不把該結(jié)點(diǎn)從目的結(jié)點(diǎn)集合里刪除也會(huì)出現(xiàn)死循環(huán)。 因此,必須在算法中加兩語(yǔ)句:Delete u from Q和Delete u from D。 同時(shí),F(xiàn)LSPT在分析時(shí)間復(fù)雜度

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論