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

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

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

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