最短路徑算法加速技術(shù)及其搜索空間分析

最短路徑問題是 GIS 網(wǎng)絡(luò)分析研究和應(yīng)用中的重要問題，其在在線地圖和導(dǎo)航中應(yīng)用廣泛。最短路徑問題的分類多樣 [1-5]，本文主要介紹針對道路網(wǎng)絡(luò)中給定 2 個(gè)頂點(diǎn)之間的最短路徑計(jì)算問題的相關(guān)算法。

1 最短路徑算法加速技術(shù)

近年來，隨著道路網(wǎng)絡(luò)數(shù)據(jù)規(guī)模的增大，一些成熟的加速技術(shù)能高效處理大規(guī)模數(shù)據(jù)的最短路徑算法?；?Delling 等的按照算法時(shí)間階段的分類方法 [6]，本文添加了國內(nèi)外最新最短路徑算法研究成果，將其分為 4 個(gè)階段 ：第一階段是算法理論研究階段(1959年 ~1999 年)，代表算法有 Dijkstra 算法 [2]、雙向搜索算法 [7]、A * 算法 [8] 等 ;第二階段為經(jīng)典最短路徑加速算法階段(1999 年 ~2005 年)，代表算法有 Lanmark 算法(地標(biāo)導(dǎo)向算法 [9])、Reach 算法 [10]、ALT 算法 [11] 等;第三階段是工程算法研究階段(2005 年 ~2008 年)，代表算法包含 Arc-Flag 算法 [12]、HH 算法 [13] 和 REAL 算法 [14] 等 ;第四階段是道路網(wǎng)絡(luò)加速算法階段(2008 年至今)，代表算法有 CH 算法 [15]、SHARC 算法 [16] 及其他算法 [17,18] 等。

在實(shí)際應(yīng)用中，由于減少搜索空間策略比設(shè)計(jì)高效的優(yōu)先隊(duì)列策略提高最短路徑查詢效率的影響要大 [19]，因此眾多加速技術(shù)策略為減少搜索空間。最短路徑算法的研究有眾多成果 [20]，但對于最短路徑的算法加速技術(shù)與搜索空間的研究還有待進(jìn)一步分析。為了研究各個(gè)階段算法的加速比與搜索空間的關(guān)系，本文選取每個(gè)階段的典型方法研究最短路徑算法加速技術(shù)和搜索空間的定量關(guān)系。

Dijkstra 算法是處理最短路徑的經(jīng)典算法，在實(shí)際應(yīng)用中結(jié)合堆或者最小優(yōu)先隊(duì)列來加速查找效率。Dijkstra 算法計(jì)算過程是以起點(diǎn) s 為根向外搜索構(gòu)成最短路徑生成樹，所有搜索空間包含的結(jié)點(diǎn)有 3 種狀態(tài) ：未通達(dá)、已通達(dá)以及確認(rèn)。如果某一結(jié)點(diǎn)已經(jīng)被確認(rèn)，表示存在 1 條從 s 到達(dá)當(dāng)前結(jié)點(diǎn)的最短路徑，當(dāng)終點(diǎn) t被確認(rèn)時(shí)搜索過程結(jié)束。

雙向搜索算法是最短路徑查詢中常用的重要搜索方法，其原理是從起點(diǎn)和終點(diǎn)同時(shí)使用單源最短路徑算法，將起點(diǎn)和終點(diǎn)搜索到的結(jié)點(diǎn)放到同一個(gè)最小優(yōu)先隊(duì)列中進(jìn)行排序，當(dāng)某一個(gè)結(jié)點(diǎn)與起點(diǎn)和終點(diǎn)之間的最短路徑都被計(jì)算出來之后，這 2 條最短路徑的組合就是起點(diǎn)到終點(diǎn)之間的最短路徑。

A* 算法是一種啟發(fā)式搜索算法，在對搜索到的結(jié)點(diǎn)進(jìn)行堆排序時(shí)，使用的不是結(jié)點(diǎn)與起點(diǎn)之間最短路徑的長度，而是估算的從起點(diǎn)到終點(diǎn)并且經(jīng)過該點(diǎn)的最短路徑長度。在權(quán)值為非負(fù)的道路網(wǎng)絡(luò)中，A* 算法在確保最終搜索結(jié)果正確性的同時(shí)，減小了搜索空間，進(jìn)而提高算法效率。

ALT 方法是 Goldberg 等 [11] 在A* 算法基礎(chǔ)上實(shí)現(xiàn)的算法。該方法首先在道路網(wǎng)絡(luò)中選擇若干個(gè)地標(biāo)，計(jì)算網(wǎng)絡(luò)中每個(gè)結(jié)點(diǎn)與地標(biāo)之間的最短路徑長度，將其作為啟發(fā)信息預(yù)先存儲(chǔ)。在最短路徑查詢時(shí)，利用結(jié)點(diǎn)與這些地標(biāo)間最短路徑長度及三角不等式估算搜索結(jié)點(diǎn)與終點(diǎn)之間最短路徑的長度，使用結(jié)點(diǎn)與終點(diǎn)的最短路徑長度作為 A* 算法搜索時(shí)的啟發(fā)信息，從而實(shí)現(xiàn)對搜索空間的裁剪。

Reach 算法是指對于某一個(gè)結(jié)點(diǎn) v，如果以 s 為起點(diǎn)、以 t 為終點(diǎn)的最短路徑經(jīng)過 v，v 在這條最短路徑上的 Reach 可定義為最短路徑上 s 到 v 與 v 到 t 的最小值。結(jié)點(diǎn) v 可以根據(jù)網(wǎng)絡(luò)中所有經(jīng)過該點(diǎn)的最短路徑計(jì)算出多個(gè) Reach 數(shù)值，其中最大的一個(gè)數(shù)值就是 v

更多內(nèi)容請查看pdf