基于NoSQL的路網(wǎng)最短路徑查詢及優(yōu)化

殷鵬

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

【關(guān)鍵詞】NoSQL A* 算法 最短路徑 Ne04j

1 引言

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

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

2.1 A*算法

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

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

（1）把起點(diǎn)加入Open列表中。

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

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

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

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

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

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

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

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

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

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

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

3.1 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的優(yōu)化

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

通過(guò)對(duì)存儲(chǔ)結(jié)構(gòu)的分析，選擇鄰接表來(lái)存儲(chǔ)較大規(guī)模的路網(wǎng)數(shù)據(jù)。

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

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

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

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

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

4 實(shí)驗(yàn)驗(yàn)證

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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