隨機網絡中的動態(tài)最短路研究.pdf

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

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