殷鵬

摘要 最短路徑問題一直是計算機學科的研究熱點。傳統(tǒng)的關系數(shù)據(jù)庫在實現(xiàn)路網(wǎng)的最短路徑查詢時，大量用到表連接查詢，耗費時間。本文提出一種基于Ne04j數(shù)據(jù)庫的路網(wǎng)最短路徑查詢和優(yōu)化方法?；贜e04j數(shù)據(jù)庫的特性以及A+算法的特點，從存儲結構、隊列優(yōu)化、搜索算法三方面對A*算法進行優(yōu)化，提出一種適用于圖數(shù)據(jù)庫的雙向搜索A*算法。最后對其改進效果進行實驗驗證，改進算法提高了查詢效率。

【關鍵詞】NoSQL A* 算法 最短路徑 Ne04j

1 引言

路網(wǎng)的最短路徑問題一直是計算機與交通領域的研究熱點。在以往的研究中，路網(wǎng)的信息主要在傳統(tǒng)的關系數(shù)據(jù)庫中以二維表的形式來存儲數(shù)據(jù)。關系型數(shù)據(jù)庫更關注實體內(nèi)部的屬性，這種存儲結構在實現(xiàn)圖的最短路徑算法時，為了描述實體之間的關系，必須通過外鍵對多個表進行連接查詢，耗費時間。隨著圖數(shù)據(jù)庫、文檔數(shù)據(jù)庫等適合不同數(shù)據(jù)模型的NoSQL數(shù)據(jù)庫的發(fā)展，為路網(wǎng)數(shù)據(jù)模型提供了新的存儲方式。NoSQL全稱為Not OnlySQL，意即“不僅僅是SQL”，泛指非關系型的數(shù)據(jù)庫。Ne04j是NoSQL數(shù)據(jù)庫中的一種以圖的形式存儲數(shù)據(jù)的圖形數(shù)據(jù)庫，具有成熟數(shù)據(jù)庫的所有特性。Ne04j設計的初衷就是為了高效的表示實體間的關系，其存儲形式更符合以圖為數(shù)據(jù)模型的路網(wǎng)。在Ne04j中，用一個鍵值對的雙向列表來保存實體和關系的屬性。節(jié)點的關系直接存儲在其定義域中，查找節(jié)點關系的時間復雜度為0（1），對于存在大量關系的圖形數(shù)據(jù)的查詢速度更快。Ne04j還提供了深度優(yōu)先搜索、廣度優(yōu)先搜索、最短路徑、迪杰斯特拉等多種圖的搜索算法，因此Ne04j尤其適用于道路交通網(wǎng)絡、地圖等方面。本文基于Ne04j數(shù)據(jù)庫對路網(wǎng)最短路徑的查詢和優(yōu)化進行研究。針對Ne04j數(shù)據(jù)庫數(shù)據(jù)的存儲特性以及A*算法的特點，提出一種適用于圖數(shù)據(jù)庫的A*算法，對其改進效果進行實驗驗證。

2 基于圖數(shù)據(jù)庫的路網(wǎng)最短路徑查詢

2.1 A*算法

A*算法作為一種最短路徑算法，建立在Di kstra算法基礎上。為了解決Dij kstra算法盲目搜索的問題，A*算法采用了估價函數(shù)作為輔助搜索信息，進行有目的的搜索，減少搜索時節(jié)點的數(shù)目，縮小搜索規(guī)模。

A*算法在初始化時創(chuàng)建Open列表和Close列表，然后執(zhí)行下列步驟：

（1）把起點加入Open列表中。

（2）遍歷Open列表，找到估計值f（n）最小的節(jié)點n，如果它不是目的節(jié)點，就把它作為當前處理的節(jié)點，把該節(jié)點從Open列表中刪除，加入Close列表中。

（3）對節(jié)點n的所有子節(jié)點c進行遍歷，如果Close列表中有c節(jié)點，則忽略它，繼續(xù)遍歷下一個子節(jié)點，否則做如下操作：

①如果子節(jié)點c不在Open列表中，把它加入，并將n設置為子節(jié)點c的父節(jié)點，計算f，g，h值。

②如果子節(jié)點c已在Open列表中，且原估價值f大于f（c），則修改f=f（c），同時將n設置為c的父節(jié)點。

（4）重復（2），（3）步，直到目的節(jié)點加入了Open列表中，表示找到路徑;或者Open列表為空，表示路徑不存在。

（5）最后從目的節(jié)點沿著父節(jié)點移動回到起始節(jié)點，就得到了最短路徑。

在A*算法的實現(xiàn)過程中，估價函數(shù)的計算公式為f（n）=g（n）+h（n），其中，g（n）代表從起始節(jié)點到當前節(jié)點n的路徑代價，h（n）代表從當前節(jié)點n到目的節(jié)點的估計路徑代價。估價函數(shù)對算法的性能有很大的影響，好的估價函數(shù)可以減少搜索節(jié)點，加快搜索速度。因此，A*算法改進的關鍵問題就是如何設計估價函數(shù)讓其接近真實路徑長度，通過減少搜索節(jié)點的個數(shù)來降低資源消耗。h（n）通常用距離長度作為參考值，但僅通過距離選取來優(yōu)化估價函數(shù)仍有很大的局限性，網(wǎng)絡特征的結構優(yōu)化與限制條件都會影響算法的效率。此外，改變搜索策略也可以提高效率。

2.2 基于Ne04j的路網(wǎng)最短路徑查詢性能分析

將相同的路網(wǎng)數(shù)據(jù)源分別導入關系型數(shù)據(jù)庫PostgreSQL和圖形數(shù)據(jù)庫Ne04j中，隨機選取了220對點分別測試A*算法在兩種數(shù)據(jù)庫中的查詢速度。實驗中，通過調(diào)節(jié)可用內(nèi)存，改變Ne04j對象緩沖區(qū)的配置參數(shù)，發(fā)現(xiàn)內(nèi)存的變化與高速緩存的變化對Ne04j的性能影響最大;內(nèi)存改變對PostgreSQL的影響不明顯，不需要通過微調(diào)優(yōu)化性能。實驗中，通過使用多線程多次執(zhí)行查詢請求的方式，研究兩種數(shù)據(jù)庫在查詢時間和內(nèi)存消耗方面的差異。實驗結果顯示，在使用更多內(nèi)存的前提下，Ne04j對路網(wǎng)的最短路徑查詢計算速度更快。與PostgreSQL不同的是，Ne04j每次查詢時可以共享內(nèi)存中已有的數(shù)據(jù)，只加載當前請求查詢的數(shù)據(jù)。這樣在熱啟動時可以用較少的時間獲得查詢結果，查詢速率優(yōu)于PostgreSQL數(shù)據(jù)庫。但如果線程數(shù)量增多，多個線程執(zhí)行不同的查詢，Ne04j會消耗更多的內(nèi)存，計算速度也會下降。因此，Ne04j并不適合對大型運輸網(wǎng)絡做全圖遍歷，這樣只會加重內(nèi)存消耗。而在存儲數(shù)據(jù)規(guī)模較小的網(wǎng)絡時，Ne04j是個很好的選擇。在內(nèi)存可用的情況下，Ne04j這種圖形數(shù)據(jù)庫更適合做最短路徑查詢。

3 基于圖數(shù)據(jù)庫的A*算法仃化

Ne04j在遍歷路網(wǎng)時擁有較快的速度，但是在路徑搜索時會占用更多的內(nèi)存。因此A*算法優(yōu)化的主要方面就是如何能縮小搜索范圍，減少遍歷節(jié)點的數(shù)量，以降低內(nèi)存消耗。

3.1 數(shù)據(jù)存儲結構的優(yōu)化

為了簡化操作，便于實現(xiàn)算法，需要為路網(wǎng)選擇合適的存儲結構。如表1所示，對比了圖的四種存儲結構。

通過對存儲結構的分析，選擇鄰接表來存儲較大規(guī)模的路網(wǎng)數(shù)據(jù)。

3.2 隊列排序優(yōu)化策略

在A*算法中選取最小估價值時，涉及到大量對Open列表和Close列表的操作。在路網(wǎng)中反復遍歷含有大量節(jié)點的列表會耗費大量時間。如果采用基本的順序結構存儲列表，在做刪除操作時要大量移動元素，效率不高。為了便于查找最小估價值節(jié)點，可以用小根堆作為Open列表的存儲結構，堆頂元素即為最小估價值，查找的時間復雜度為0（1）。刪除堆頂元素后，重新調(diào)整為小根堆所需要的時間與查找最小估價值的時間相比可以忽略，因此，采用小根堆的存儲方式可以大大提高查找效率。

3.3 雙向搜索A*算法優(yōu)化

在Ne04j中，關系可以從兩個方向進行遍歷，因此本文提出了一種動態(tài)雙向搜索算法，通過改變搜索方式對A*算法做出優(yōu)化，以減少內(nèi)存消耗。雙向搜索就是將搜索分為正向搜索和反向搜索，正向搜索時，把反向的當前搜索節(jié)點看作臨時目的節(jié)點，從Open列表中選擇估價值最小的點向后搜索到達節(jié)點T;切換為反正搜索時，把正向的當前搜索節(jié)點T看作臨時目的節(jié)點，從反向Open列表中選擇估價值最小的點向前搜索。正反向搜索反復迭代，直到正向和反向搜索的當前節(jié)點為同一節(jié)點時結束。

理論上雙向搜索是從兩個方向均勻同步進行，直到起始節(jié)點和目的節(jié)點的中心相遇。但在實際路網(wǎng)中節(jié)點的分布密度不同，起點和目的節(jié)點所在路網(wǎng)的可達程度也不一樣。雙向搜索相遇的節(jié)點不一定在最短路徑的幾何中心。因此，算法的關鍵是如何選擇切換標準，盡可能讓最佳節(jié)點在中間相遇。本文提出了使用基于比較雙向最佳節(jié)點估價值的思想，通過比較正反向Open列表分別相對于起點和目的節(jié)點的最小估計值，來決定切換方向。若正向搜索取出Open列表中最佳節(jié)點的估計值小于反向搜索最佳節(jié)點的估計值，說明正向搜索更接近返回路徑的中心位置，則切換到反向進行搜索，讓反向搜索逐漸向最佳路徑的幾何中心靠攏，最終正反向搜索在中間位置相遇。

4 實驗驗證

本次實驗首先選取了十組數(shù)據(jù)，對A*算法和隊列排序優(yōu)化后的A*算法的查詢效率進行測試，結果如圖l所示。

通過折線圖分析得出，當搜索節(jié)點較少時，優(yōu)化后的算法耗費時間較長。主要原因是小根堆在插入到Open表時需要查找位置，刪除堆頂元素后需要堆調(diào)整，因此耗費了一些時間。但是隨著路徑節(jié)點數(shù)的增多，搜索范圍變大，使用小根堆作為排序數(shù)據(jù)結構的優(yōu)勢慢慢體現(xiàn)了出來。

實驗中按照路徑距離隨機選取了六組數(shù)據(jù)，對A*算法和優(yōu)化后的雙向搜索A*算法的查詢效率和內(nèi)存消耗進行測試。實驗結果顯示雙向搜索A*算法加載內(nèi)存少于A*算法，降低了內(nèi)存消耗。通過圖2所示的實驗結果得出，優(yōu)化后的雙向搜索A*算法的搜索節(jié)點數(shù)比A*大大減少。但第三組實驗中雙向搜索A*算法比原A*算法多了36個搜索節(jié)點，這是由兩種方法尋路路徑不同導致的，其他組實驗的最短路徑結果與A*算法相同或相近，證明雙向搜索A*算法在保證較高精度前提下，提高了查詢效率。

5 結語

本文基于NoSQL數(shù)據(jù)庫對路網(wǎng)最短路徑查詢及優(yōu)化問題進行了研究。分析了圖形數(shù)據(jù)庫Ne04j的特點以及與關系數(shù)據(jù)庫的差異。在兩種存儲平臺下實現(xiàn)路網(wǎng)最短路徑查詢，從查詢效率以及內(nèi)存消耗等方面進行比較，分析了Ne04j在查詢最短路徑時的優(yōu)點與不足?；贜e04j數(shù)據(jù)庫的特性以及A*算法的特點，對A*算法進行了優(yōu)化。通過實驗驗證，改進算法提高了查詢效率。

參考文獻

[1]李曉華，王士猛，楊曉春，于戈，基于緩存技術的路網(wǎng)最短路徑查詢[J].東北大學學報（自然科學版），2014，35 （02）：199—203.

[2]廖志芳，陳亮名，彭志文，李嚴冰，基于節(jié)點壓縮的尋徑優(yōu)化算法[J].計算機應用與軟件，2017，34 （11）：241-246.

[3]宋寶燕，張永普，單曉歡.Spark-GraphX框架下的大規(guī)模加權圖最短路徑查詢[J].遼寧大學學報（自然科學版），2017， 44 （04）： 289-29 3+284.

[4]姜代紅，戴磊.Dijkstra算法在嵌入式GIS中的改進與研究[J].計算機工程與應用，2011， 47 （31）： 209-211.