基于流行學習LPP算法與Dijkstra算法結合的交通路徑控制研究

摘 要：隨著現代交通控制技術和科學技術的發展，多種優良的智能算法被應用于交通路徑規劃控制。最短路徑計算是智能交通中的最基礎環節，在智能交通中起著至關重要的作用。目前的最短路徑算法主要有4種[1]，即Dijkstra算法、A*算法、BellmanFord算法、雙向分層啟發式算法，每一種算法都有不同的執行標準。而文章提出一種LPP與最短路徑算法結合，在保持準確的實現交通路徑規劃的同時很好的解決算法時間長的問題。通過仿真實驗證明該算法有效率，容易實現，適合大范圍路徑的計算。

關鍵詞：城市交通控制；路徑測量；LPP算法；Dijkstra算法；最優路徑

1 引言

交通控制中，最為基礎是路徑測量，隨著現代交通控制技術和科學技術的發展，多種優良的智能算法被應用于交通路徑規劃控制中[2-4]，如PCA結合LPP法、零空間LDA法、偽逆LDA 法、正則法LDA等[5-6]。然而，這些算法受到算法求取離散值分類的影響，在計算速度上很慢。為此，本文提出一種LPP算法與最短路徑算法結合，在保持準確的實現交通路徑規劃的同時很好的解決算法時間長的問題。

2 流形學習算法中的LPP算法

流形學習的目標是發現嵌入在高維數據空間中的低維流形結構，LPP（Locality Preserving Projections），又叫局部保持投影，是非線性方法拉普拉斯特征映射（Laplacian Eigenmap）的線性近似，它既能獲得新的數據樣本點較低維度的投影，又能保持原始數據非線性的流形特征。就其本質特點，它是一種能較好地保持非線性流形中局部數據特征的線性流形學習算法，目標是保證原始數據空間上相鄰的數據點在投影后的空間上也保持相應的相鄰關系。

3 算法改進和實現

結合兩個算法的方法是基于以上LPP的基本算法和Dijkstra最短路徑算法設計混合而成。Dijkstra是一個適用于所有弧的權為非負的最短路徑算法，與LPP結合適用于交通路徑優化。Dijkstra算法主要思想如下：

Dijkstra算法是一個按路徑長度遞增的次序產生最短路徑的算法，在每一環節都選擇局部最優解以期望產生一個最優解。它在構建路徑網絡中，設置了每條道路的花費，該算法在每一環節都選擇花費最小的節點進行，從而產生最優路徑解。

3.1 算法設計

3.1.1 設置一個輔助向量dist[]，其每一分量表示為dist[i]，其意思是已經找到的最短路徑的長度，而且是從初始點v0到達每一個終點vi的當前最短路徑的長度。其的初始狀態為：若從初始點v0到終點vi有弧，則dist[i]是該弧的權值，否則dist[i]為∞。

3.1.2 假設S是已經目前求得的最短路徑的終點集合，當按路徑長度遞增的規則來求出每條最短路徑時可知，下一條最短路徑可能是弧（v0，vx），可能是途中經過集合S中的某些頂點，然后到達終點Vx的路徑。

4 試驗及結果分析

本實驗基于GIS操作軟件MAPGIS，實驗的對象是的40個和46個重要建筑的坐標，引用本文提出的方法進行交通路徑控制實驗，實驗結果的總輸出為連接這些坐標的最短路徑，并顯示與輸出設備上。由于交通路徑控制的目的之一就是計算最短路徑，本文的流行學習算法應用于這方面較為適合。

圖2所示為實驗結果，原點坐標為任意選取的出發點，以該點建立坐標系，從圖中可以明顯看出所標示的路徑為最優路徑，其中一個明顯的特征就是路徑沒有出現交叉，這是評判一個算法在最優路徑選取中的優劣的標準。本算法無論是在何種地圖中，都能進行全局規劃，從圖中可以看出，其標識的路徑多次出現局部多個坐標選擇的情況，本文的路徑規劃明顯能綜合考慮前后次序關系進行最優選擇。總之，在對地圖中，采用文本設計的方案和提出的方法對隨機選取40個和46個重要建筑坐標的求解過程中，本文提出的改進LPP方法達到了最優路徑測量和選擇的目的。

5 結束語

本論文的主要內容是研究和解決在交通路徑控制的應用問題。本文設計的Dijkstra算法與流形學習算法中的LPP算法結合，適合大范圍路徑的計算，該混合算法更簡結且容易實現。由于改進后的算法每次只從V中取距離最小的一點置于S中，在每次循環中等于把等待處理的點集V作一個特殊的集合來獨立處理，該處理方法保證了每一次循環中使最短路徑的范圍擴大了一個點，從而保證了每一步的最優。從應用時的具體效果來看，本文方案可行。

參考文獻

[1]王林，石劍峰.智能交通系統中幾種最短路徑算法分析[M].2009，4.

[2]Turk M A and Pentland A P.Eigenfaces for recognition.Journal of Cognitive Neuroscience，1991，3（1）： 71-86.

[3]Yong-Il Kim，Moo-Wuk Pyeon，Yang-Dam Eo.Development of hyper-map database for ITS and GIS [J].Computers，Environment and Urban Systems.2000（24）：50-55.

[4]Jon EllisLinda Ho.JDBC3.0 Specification.USA.Sun Microsystems [M].2001：61-77.

[5]Ralf Willenbrock.“City-FCD”-Technology approach towards cost efficient mobile traffic data for TMC based inner urban navigation[EB/OL].Gedas EFCD Workshop.2005.

[6]虞盛超.XML技術在面向數字城市的移動GIS系統中的應用研究[D].北京.北京大學，2002，6：13-23.

[7]Duda R O，Hart P E，Stork D G.Pattern classification[M].2nd ed.Hoboken：Wiley - Interscience，2000.

[8]劉青山，盧漢清，馬頌德.綜述人臉識別中的子空間方法[J].自動化學報，2003，29（6）：900-911.

[9]Ye J，Tao X.Computational and theoretical analysis of 1 space and orthogonal linear discriminant analysis[J].Journal of Machine Learning Research，2006，7：1183-1204.