動(dòng)態(tài)環(huán)境下最短路徑樹算法的分析與研究.pdf

1、隨著傳感器技術(shù)，通信技術(shù)，計(jì)算機(jī)技術(shù)的不斷發(fā)展，在現(xiàn)實(shí)生活和實(shí)際應(yīng)用中，最短路徑問題都起著非常重要的作用。如在交通網(wǎng)絡(luò)中，需要找到最佳的行車路線，使得快速到達(dá)目的地。在物流配送中，物流公司不僅要考慮物流的速度還要考慮物流的成本，這些現(xiàn)實(shí)問題都可以通過建模，最終形式化為最短路徑的問題，從而利用經(jīng)典的算法來解決實(shí)際的問題。
　　近些年，對(duì)最短路徑樹的問題被廣泛研究，已得到很多成熟穩(wěn)定的靜態(tài)算法，然而，隨著網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)需求的變化，這些

2、算法已無法滿足動(dòng)態(tài)網(wǎng)絡(luò)的需求。動(dòng)態(tài)網(wǎng)絡(luò)的狀態(tài)會(huì)隨著時(shí)間發(fā)生變化，如果要得到最短路徑，那么實(shí)時(shí)的變化就要頻繁的重新計(jì)算最短路徑，反復(fù)地計(jì)算不僅消耗大量時(shí)間，也會(huì)導(dǎo)致最短路徑樹的頻繁變化，最終使得最短路徑樹變得極其不穩(wěn)定。
　　本文通過對(duì)以往動(dòng)態(tài)算法的分析提出了不穩(wěn)定邊的概念，對(duì)不穩(wěn)定邊進(jìn)行分析和統(tǒng)計(jì)，通過記錄頻繁變化的不穩(wěn)定邊并盡可能避免將其加入最短路徑樹中，從而能夠高效地減少邊變化帶來的操作。為此，我們提出了一種穩(wěn)定的最短路徑樹構(gòu)

3、造算法，該算法與以往算法相比，能使構(gòu)造的路徑樹在動(dòng)態(tài)網(wǎng)絡(luò)上更穩(wěn)定，即更新最短路徑樹所需的操作數(shù)更少。為了測(cè)試該算法的性能，我們?cè)陔S機(jī)網(wǎng)絡(luò)環(huán)境中進(jìn)行了科學(xué)的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的動(dòng)態(tài)最短路徑樹算法相比，本文的算法可以得到更穩(wěn)定的最短路徑樹，并在更新時(shí)間上改進(jìn)了57.24％，在結(jié)點(diǎn)更新次數(shù)上降低了43.6％。另外，實(shí)驗(yàn)中大約60％的隨機(jī)實(shí)例可以得到精確解，在計(jì)算最短路徑樹權(quán)重上我們的算法會(huì)有點(diǎn)誤差，但是整個(gè)解的誤差可以控制在2％以內(nèi)。