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

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

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

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