基于城市路網的最短路徑算法研究與應用.pdf

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

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

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