基于城市路網(wǎng)的最短路徑算法研究與應(yīng)用.pdf

1、現(xiàn)如今，城市規(guī)模擴大，汽車數(shù)量增多，交通擁堵問題成我國亟需解決的重要問題之一。解決城市路網(wǎng)交通擁堵問題的關(guān)鍵技術(shù)在于最短路徑的研究。因此，基于城市路網(wǎng)的最短路徑算法研究具有重要意義。本課題重點研究了求解城市路網(wǎng)最短路徑的Dijkstra算法以及求解K最短路徑的Yen算法，主要工作如下:
　　(1)在存儲城市路網(wǎng)圖方面，鄰接矩陣存儲稀疏圖時，存在數(shù)據(jù)冗余度大的問題，本文提出用鄰接表數(shù)據(jù)結(jié)構(gòu)存儲城市路網(wǎng)圖，降低Dijkstra算法的空

2、間復(fù)雜度。
　　(2)在搜索范圍優(yōu)化方面，Dijkstra算法存在搜索范圍廣、遍歷節(jié)點多，耗時長的問題，本文對橢圓搜索算法、矩形搜索算法優(yōu)化Dijkstra算法的問題進行深入的分析，結(jié)合路網(wǎng)特征給出兩種算法的具體搜索范圍和面積公式。并通過實驗對比分析，證明了采用矩形算法優(yōu)化Dijkstra算法的可行性和高效性。
　　(3)針對Yen算法在求解K最短路徑計算比較復(fù)雜，時間復(fù)雜度高的問題，對Yen算法做了改進。通過引入估價函數(shù)，

3、求解最短路徑時只選取估價值最小的節(jié)點作為最終的偏離節(jié)點，降低了算法的復(fù)雜度。并通過實驗，從算法尋路時間、算法所求的路徑長度及尋路過程中產(chǎn)生的候選路徑數(shù)目方面對比分析了兩種算法，驗證了算法的有效性。
　　(4)基于unity3d和3dsMax，利用了模型優(yōu)化技術(shù)設(shè)計實現(xiàn)了虛擬城市路網(wǎng)尋路系統(tǒng)，將矩形搜索算法和基于啟發(fā)式搜索改進的Yen算法應(yīng)用到虛擬城市路網(wǎng)尋路系統(tǒng)中，并驗證了本文所提觀點在具體應(yīng)用中的高效性和可行性，達到了預(yù)期的尋路