最優(yōu)路徑算法在交通地理信息系統(tǒng)中的運用分析

胡衛(wèi)榮

北京晶眾智慧交通科技股份有限公司 北京 100012

城市化建設(shè)步伐加快，交通壓力一直困擾著城市交通發(fā)展，在這種情況，交通地理信息系統(tǒng)積極應(yīng)用最優(yōu)路徑算法。在交通地理信息系統(tǒng)及時在收集城市交通數(shù)據(jù)與存儲管理數(shù)據(jù)，詳細分析數(shù)據(jù)，協(xié)調(diào)城市交通空間基礎(chǔ)上，最優(yōu)路徑算法協(xié)助交通地理信息系統(tǒng)，能夠?qū)⒌貓D靈活變大或者縮小，并增加圖層控制功能，及時進行地理信息查詢服務(wù)，進一步完善交通信息查詢模式，保證為公眾提供實時準確的交通信息。不僅如此，最優(yōu)路徑算法還能夠?qū)φ军c覆蓋率進行準確計算，科學(xué)分析交通緩沖區(qū)，為公眾了解交通信息提供更多方便。

1 交通地理信息系統(tǒng)中最優(yōu)路徑算法設(shè)計思路

最優(yōu)路徑算法在交通地理信息系統(tǒng)中的應(yīng)用，針對其具體特點與交通地理信息系統(tǒng)需要，積極進行優(yōu)化設(shè)計?；驹O(shè)計思路中，在交通地理信息系統(tǒng)中，設(shè)置好網(wǎng)絡(luò)標號，以點（dj、pj）為中心，涉及起源點s、節(jié)點j之間的長度，此為dj，若s、j點之間無距離，則將其稱之為零路。起點s、節(jié)點j相互連通中最短路徑為pj。由此為設(shè)計載體，計算兩點之間最優(yōu)路徑。

第一，提前將節(jié)點進行初始化處理。所有點的值均設(shè)置為空值，其中起始點除外的節(jié)點，dj在初始狀態(tài)相當于無窮大，pj則代表任意點的任意值。將起源點s進行標記，并調(diào)整為s=k，不需要標注其他點[1]。

第二，將已標記節(jié)點進行統(tǒng)計，以k為代表，該點與其相連接的沒有進行標記的節(jié)點，以j為代表，計算兩者之間的距離，并得到：dj=min[dj,dk+1kj]，計算公式中，直接連接的距離為1kj。

第三，根據(jù)交通地理信息系統(tǒng)提供的信息，將下一節(jié)點提前選取完畢，其中dj的選擇一定要符合未標記、最小要求。節(jié)點的選擇公式如下di=min[dj,未標記點總和j]作為已標記點i，其在交通地理信息系統(tǒng)中，屬于路徑最優(yōu)與最短點。連接節(jié)點i與其之前節(jié)點，結(jié)合已標記節(jié)點，連接之前節(jié)點j*，這期間，之前階段與當前節(jié)點是同等關(guān)系。

第四，根據(jù)當前標志的節(jié)點，將節(jié)點途徑位置全部納入到標記點中，及時完成最優(yōu)路徑計算，并得到最終地理想路徑。

2 最優(yōu)路徑算法進一步優(yōu)化

最優(yōu)路徑算法在交通地理信息系統(tǒng)中的應(yīng)用，根據(jù)其設(shè)計思路進一步簡化，將標記點劃分為未標記、永久標記與臨時標記，方便最優(yōu)路徑計算與資料整理。初始化狀態(tài)下，所有點均屬于未標記類型，根據(jù)交通地理信息系統(tǒng)的搜索以及統(tǒng)計分析，選擇出接近最短路徑的點，設(shè)置為臨時標記，因為最優(yōu)路徑計算具有循環(huán)性特點，所以臨時標記點是計算參考的關(guān)鍵點。在搜索中尋找最優(yōu)路徑位置，并標注出最短位置，此標記類型為永久標記[2]。在循環(huán)標記過程中，不斷增加臨時標記點，將最優(yōu)路徑所有點均標記完畢，最優(yōu)路徑算法運行結(jié)束。改變臨時標記無序存儲的不足，打破最優(yōu)路徑算法運行瓶頸，可以更迅速地鎖定需要搜索節(jié)點，不需要將全部臨時標注一一過濾[3]。以最短路徑為出發(fā)點將臨時標記節(jié)點進行排序，減少臨時標記過濾時間與數(shù)量，從而更快的得到最終的目標節(jié)點。

3 最優(yōu)路徑算法中的直線優(yōu)化運用

針對最優(yōu)路徑算法在交通地理信息系統(tǒng)中的應(yīng)用，采取直線優(yōu)化的方式，將最優(yōu)路徑中的搜索范圍有效縮減，減少冗余搜索，迅速確定目標節(jié)點。在平面網(wǎng)絡(luò)基礎(chǔ)上，起源點與臨時標記點之間的距離，屬于臨時標記點重要屬性值，同時目標點與臨時標記點之間的距離同樣屬于臨時標記點屬性值。結(jié)合臨時標記點屬性值為永久標記點的選取重要依據(jù)，永久標記點盡可能選擇屬性值中的最小值。最優(yōu)路徑算法的直線優(yōu)化升級，將搜索手段進行智能化處理，不僅節(jié)點數(shù)量明顯減少，同時在很大程度上將搜索速度加快。

3.1 對比搜索過程的優(yōu)勢

最優(yōu)路徑算法的直線優(yōu)化處理，改變原有算法應(yīng)用期間，以起源點作為基礎(chǔ)圓心，隨后搜索過程中會生成很多同心圓，但是在過程中并沒有對終點位置或者方向有過多地考慮，從圓心開始進行搜索，搜索速度與概率并相對較慢。但是直線優(yōu)化后的最優(yōu)路徑算法，其在終點搜索期間，會設(shè)定終點、起源點之間的臨時點作為搜索焦點，形成同心橢圓搜索路徑，搜索速度明顯加快。結(jié)合測試可以發(fā)現(xiàn)，整個搜索中，所有搜索目的均迅速集中在終點，根據(jù)臨時節(jié)點的引導(dǎo)，搜索節(jié)點減少，搜索效率更高。

3.2 直線優(yōu)化應(yīng)用范圍

最優(yōu)路徑算法中，直線優(yōu)化處理后，相對原有算法，非常適用于弧長度計算，尤其是權(quán)值以網(wǎng)絡(luò)中弧為主。設(shè)定網(wǎng)絡(luò)系統(tǒng)這個整體為一個平面，在這個平面通過起源點、臨時節(jié)點等計算最短路徑。交通地理信息系統(tǒng)中，直線優(yōu)化的最優(yōu)路徑算法更適合小范圍地理搜索。在不同方面將搜索范圍與速度進行了明顯調(diào)整。以起源點為中心，在系統(tǒng)運行過程中逐漸向網(wǎng)絡(luò)邊界靠近，忽略掉不必要節(jié)點，以最快速度完成系統(tǒng)搜索。從節(jié)點數(shù)量上來講，直線優(yōu)化節(jié)點數(shù)量減少基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)以及交通地理信息系統(tǒng)運行，及時進行差異性分析，調(diào)整更加靈活，搜索更加便利。在相同范圍條件下，若起源點與終結(jié)點之間并不是連通狀態(tài)，則需要將搜索范圍調(diào)整到全部，節(jié)點不能作為終結(jié)點之間的媒介，而是全面性搜索。提前對節(jié)點數(shù)進行確定，根據(jù)節(jié)點數(shù)去確定計算最短與最優(yōu)距離的數(shù)值，積極進行最優(yōu)路徑計算。

4 結(jié)束語

綜上所述，交通地理信息中積極應(yīng)用最優(yōu)路徑算法，其不僅能夠幫助交通地理信息實現(xiàn)疊層搜索，同時在很多方面提高交通地理信息系統(tǒng)信息收縮與數(shù)據(jù)處理的效率。當然在實際應(yīng)用中，根據(jù)交通地理信息需要，及時對最優(yōu)路徑算法進行升級處理，其中直線優(yōu)化方式的實用性更高，搜索速度更快，具有非常大的應(yīng)用空間。