隨機(jī)網(wǎng)絡(luò)中的動(dòng)態(tài)最短路研究.pdf

1、在傳統(tǒng)的最短路徑問題中，假設(shè)網(wǎng)絡(luò)中的權(quán)值是靜態(tài)的、確定的，這些假設(shè)在ITS、計(jì)算機(jī)網(wǎng)絡(luò)與通信等許多應(yīng)用領(lǐng)域是不現(xiàn)實(shí)的。時(shí)變、隨機(jī)網(wǎng)絡(luò)最短路問題突破了傳統(tǒng)的最短路徑問題的局限性，成為ITS的基礎(chǔ)理論。新的現(xiàn)實(shí)問題使得最短路的計(jì)算變得非常困難。 本文針對(duì)出現(xiàn)的新問題及前人研究中存在的問題，重點(diǎn)研究了時(shí)變隨機(jī)網(wǎng)絡(luò)中的最短路問題。本文的工作分為三部分： (1)總結(jié)了前人的研究成果，并指出存在的問題。 (2)從有限覆蓋定理

2、入手，針對(duì)權(quán)值為關(guān)于時(shí)間t的連續(xù)函數(shù)的動(dòng)態(tài)最短路問題，分析某個(gè)時(shí)刻的最短路與該時(shí)刻的鄰域內(nèi)的最短路關(guān)系，求解某個(gè)時(shí)刻從起點(diǎn)到終點(diǎn)的最短路。在求解權(quán)值為連續(xù)函數(shù)的隨機(jī)網(wǎng)絡(luò)在某個(gè)時(shí)刻的動(dòng)態(tài)最短路時(shí)，將關(guān)于時(shí)間的閉區(qū)間劃分為有限個(gè)恰當(dāng)間隔的小區(qū)間，運(yùn)用權(quán)值期望的方法將各小區(qū)間上的權(quán)值函數(shù)轉(zhuǎn)化為離散函數(shù)來解決。 (3)基于蟻群算法設(shè)計(jì)了時(shí)變隨機(jī)網(wǎng)絡(luò)中最短路的算法，實(shí)驗(yàn)證明該算法可以有效的求解隨機(jī)網(wǎng)絡(luò)中實(shí)時(shí)最短路問題。 本文的研究