最優路徑算法在交通地理信息系統中的運用分析

胡衛榮

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

城市化建設步伐加快，交通壓力一直困擾著城市交通發展，在這種情況，交通地理信息系統積極應用最優路徑算法。在交通地理信息系統及時在收集城市交通數據與存儲管理數據，詳細分析數據，協調城市交通空間基礎上，最優路徑算法協助交通地理信息系統，能夠將地圖靈活變大或者縮小，并增加圖層控制功能，及時進行地理信息查詢服務，進一步完善交通信息查詢模式，保證為公眾提供實時準確的交通信息。不僅如此，最優路徑算法還能夠對站點覆蓋率進行準確計算，科學分析交通緩沖區，為公眾了解交通信息提供更多方便。

1 交通地理信息系統中最優路徑算法設計思路

最優路徑算法在交通地理信息系統中的應用，針對其具體特點與交通地理信息系統需要，積極進行優化設計。基本設計思路中，在交通地理信息系統中，設置好網絡標號，以點（dj、pj）為中心，涉及起源點s、節點j之間的長度，此為dj，若s、j點之間無距離，則將其稱之為零路。起點s、節點j相互連通中最短路徑為pj。由此為設計載體，計算兩點之間最優路徑。

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

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

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

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

2 最優路徑算法進一步優化

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

3 最優路徑算法中的直線優化運用

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

3.1 對比搜索過程的優勢

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

3.2 直線優化應用范圍

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

4 結束語

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