A*進路搜索算法的研究與實現

梁藝凡，譚麗，馮挺

(1.蘭州交通大學自動化與電氣工程學院， 蘭州 730070；2.廣州鐵路(集團)公司，廣東深圳 518000)

1 概述

計算機聯鎖系統是鐵路行車指揮的關鍵系統之一，有著保證行車安全和提高行車效率的重要作用，其主要功能是接受調度計劃進行進路控制，完成作業辦理。進路搜索作為計算機聯鎖系統的核心模塊，直接影響了進路控制的正確、安全、高效性。目前應用于鐵路現場的計算機聯鎖系統有DS6-K5B、EI32-JD、HJ04A等，其進路搜索方法主要采用帶導向標志和優先策略的傳統搜路法，改進的深度優先、廣度優先搜索和Dijkstra算法，以及相關理論研究采用二叉樹遍歷進行搜索等[1]。經現場應用發現，上述方法均搜索效率低、占用資源大。為了提高進路辦理效率，本文研究采用A*算法搜索進路。

2 A*算法

A*算法是用于求解靜態路網中最短路的智能算法，使用啟發函數對待擴展節點進行最優選擇，使得所擴展的節點少于其他同類搜索算法，因此更加高效，加之其啟發函數設計靈活，易于實現的特點，A*算法在智能交通、機器人路徑搜尋等方面有著廣泛應用。車站信號平面布置圖按照接發車方向可以抽象為有向圖，應用A*算法進行路徑搜索是可行的。

A*算法在搜索時將當前待擴展節點保存在open列表中，對其按照啟發函數值進行排序，選擇f值最小的節點壓入closed列表，并產生此節點的所有后繼壓入open中，作為下次的擴展對象。在搜索中不斷更新open和closed列表，以確保當前保存的是已擴展的起始節點到目標節點的最優路徑上的節點[2]。其啟發函數為

f′(n)=g′(n)+h′(n)

式中n——搜索中遇到的任意中間節點；

f′(n)——起始節點經由n到目標節點的估計代價；

g′(n)——起始節點到n的最優路徑的估計代價；

g(n)——起始節點到n的最優路徑的實際代價；

h′(n)——n到目標節點的最優路徑的估計代價；

h(n)——n到目標節點的最優路徑的實際代價。

當h′(n)≤h(n)時，稱h′(n)是可采納的，此時搜索的點數多、效率低，但能確保得到最優解(若存在最優解)[3]。

3 基于A*算法的進路搜索策略

3.1 啟發函數的設計

車站信號平面布置圖主要反映了站場線路的布置和接發車方向，以及主要信號設備的名稱編號和位置。若將道岔和信號機節點抽象為圖的頂點(道岔分岔前、岔后頂點，并置調車信號機用2個頂點表示)，軌道區段則成為連接這些頂點的邊。那么對于特定的接發車方向，可以將信號平面布置圖看作一個有向圖G[4]。G=(V，E)，其中V={v1，v2，…，vn}，為G中頂點的集合；E={e1，e2，…，en}，為G中邊的集合。

設vi為搜索中遇到的任意節點，坐標為(xi，yi)；vj為目標節點，坐標為(xj，yj)。為了滿足h′(n)≤h(n)，保證算法的完備性和最優性，將h′(n)的值定義為兩節點間的歐幾里得距離。考慮到列車沿鋼軌直線走行的限制，令g′(vi)=4*abs(yi-yj)，增強優先擴展的節點和目標節點在同一股道的可能性。則啟發函數為：f′(vi)=g′(vi)+h′(vi)=sqrt((xi-xj)∧2+(yi-yj)∧2)+4*abs(yi-yj)。

根據所設計啟發函數的構造特點，設K為G的距離矩陣，用于存儲G中所有節點兩兩間的f′(n)值。K滿足kij=d(vi，vj)，其中i≥0，j≤n-1；對于i=j，有kij=0；且滿足d(vi，vj)=d(vj，vi)，即kij=kji，K為對稱矩陣[5]。對待擴展節點排序時，通過讀取K的部分值即可得到待擴展節點的f′(n)值，總體上節省了程序執行時間。

3.2 數據結構的實現

聯鎖程序需要大量的靜態數據為基礎，對數據庫的構建，一般有進路表型數據結構和站場型數據結構。進路表型數據結構的優點是搜路方便，根據操作命令從總進路表中選取即可；缺點是總進路表編制繁瑣、容易出錯，占用存儲空間大，修改困難[6]。站場型數據結構的優點是動態生成進路表，占用存儲空間小，容易修改；缺點是進路辦理約束多，程序實現復雜，搜索耗時多。

綜合兩者的優點，當由于平行渡線而產生多條進路時，將確定的基本進路編制成“基本進路表”，再采用更適合A*算法的改進的站場型數據結構進行其余進路的搜索。在搜索時若判定始終端在基本進路表中，則直接讀取進路；否則采用A*搜路算法搜索進路。這樣沖淡了上述兩種數據結構各自的優缺點，既簡化了A*搜路算法程序，保留了站場型數據結構的優點，又僅是對基本進路進行進路表編制，占用存儲空間較小。

3.3 A*進路搜索算法的搜索流程

進路搜索程序需要完成的具體任務如下：

(1)按下進路始終端按鈕后只能選出一條基本進路，要選擇變通進路需人工按壓變通按鈕[7]；

(2)檢查所選出進路的敵對進路是否建立；

(3)若能建立進路，在與該進路有關的所有變量模塊中設置占用標志，即鎖閉敵對進路；

(4)指明與進路相關道岔的位置；

(5)形成一個進路表供聯鎖處理程序使用。

設起始節點為S，目標節點為M，X為搜索中遇到的任意節點，搜索范圍為：{xM

圖1 A*進路搜索算法搜路流程

4 實驗及算法性能分析

4.1 實驗平臺搭建

計算機聯鎖系統軟件用于實現人機界面信息處理、基本聯鎖控制及執行、自動檢測與診斷等功能。為方便實現，在保證核心功能的前提下，用Visual C++6.0進行編程，實現了簡化的計算機聯鎖軟件，設備狀態通過變量設置虛擬實現。通過此仿真軟件辦理列、調車進路，驗證A*進路搜索算法的可行性；并在同一臺PC機上實現兩個聯鎖仿真軟件，兩者僅在進路搜索程序上有所區別，分別使用A*搜路算法和傳統搜路法。編寫測試代碼分別對兩者的進路辦理時間進行測試顯示，比對算法效率。

對各設備的結構體定義中，除了包括節點ID號、空間坐標、左右節點ID號等體現鏈接關系的信息外，還要對其各種特性用“0”“1”碼分別描述，得出每個節點十六進制的特性編碼，用來反映設備的狀態及確定所辦進路性質、能否建立進路等。

對open列表采用最小二叉堆(class BinaryHeap)來實現，最小二叉堆很容易找到最小元素，并在移除最小元素時仍然保持為一個有效最小二叉堆[8]。將closed列表定義為一個一維變長數組，用vector來實現。對矩陣K采用壓縮存儲的方法，只將K的下三角中的元素按行優先的順序存儲在一個一維數組double heur[ ]中，讓每兩個對稱的元素共享一個存儲空間，節約近一半的存儲空間。

實驗界面如圖2所示，圖中白光帶表示已選出進路，此時X4信號機開放，亮綠燈。道岔狀態如圖左上角所示，進路所經過的道岔均已鎖閉，為紅燈。圖3為點擊菜單“進路表”后彈出的窗口，記錄了所辦進路的進路表。實驗證明，A*搜路算法能夠快速正確的搜出所需基本進路，自動生成進路表。

圖2 聯鎖仿真軟件上位機顯示

圖3 進路表窗口

4.2 算法性能分析

目前常用的幾種進路搜索方法中，Dijkstra算法性能較好，傳統搜路法應用最為廣泛。Dijkstra算法毫無選擇地向四周擴展，遍歷計算的節點很多，搜索效率較低。若圖的節點數為n，邊數為m，邊的權值為c，搜索效率較高的基于Bucket優先級隊列的Dijkstra算法的時間復雜度為O(m+nc)，而A*算法的時間復雜度為O(n′)，n′為A*算法搜索中擴展的節點數，效率明顯優于Dijkstra算法，且A*算法遍歷保存的節點數量不多，節省存儲空間[9]。現將A*搜路算法與傳統搜路法從以下幾個方面進行比較，詳細分析A*搜路算法的性能。

(1)有效性

傳統搜路方法經過多年實踐驗證，其有效性不言而喻。A*搜路算法使用歐幾里得距離作為估價值，必然小于或等于實際距離，滿足可采納性，能夠得到最優解。且經實驗驗證，A*搜路算法能夠搜出所需的基本進路，證明了其可行與準確，即有效。

(2)高效性

圖4 兩種算法多次辦理同一進路的時間曲線

由于聯鎖軟件的高實時性，使用微秒級精確度的QueryPerformanceCounter函數來測試進路辦理時間，為便于記錄，將換算結果換算為毫秒輸出。實驗結果如圖4、圖5的MATLAB擬合曲線所示。圖4為多次辦理同一條進路(D4-XⅠ)兩者的用時曲線；圖5為辦理多條不同進路兩者的用時曲線。由圖4可見，傳統搜路法由于擴展節點多，遍歷節點的累積時間差較大，相較之下，A*搜路算法的搜索時間更加穩定。由圖5

可見，當所辦進路經過多個對向道岔時，兩者時間相差較大，A*搜路算法效率明顯高于傳統搜路法；當所辦進路經過對向道岔不多時，兩者時間相差不大，A*搜路算法效率仍然高于傳統搜路法；當所辦進路不經過對向道岔時，兩者時間相差不大，A*搜路算法效率有時會低于傳統搜路法。由此可得，當站場復雜，咽喉區道岔數量多，平行進路多時A*搜路算法的高效性會更加突出；當站場簡單時，A*搜路算法較傳統搜路法高效性優勢體現不大。

圖5 兩種算法辦理多條進路的時間曲線

(3)占用空間

在靜態數據的存儲上，除了所需的共同基礎數據，傳統搜路法需要存儲道岔類型、渡線類型等數據，A*搜路算法需要存儲各節點f′(n)值，兩者相差不大；對于搜索過程中所產生的動態存儲空間，傳統搜路法搜索時遍歷的節點數要多于A*搜路算法，在所辦進路復雜時尤為明顯。總體來說，A*搜路算法更加節省存儲空間。

(4)可靠性

一個有效的算法其可靠性要通過程序的完善和強壯性來實現，A*搜路算法的程序編寫還不夠精良，和已經實際運行很多年的傳統搜路法相比，A*搜路算法的可靠性還需要在實際應用中不斷完善增強。但在滿足仿真實驗平臺的需求上，A*搜路算法的可靠性已達到預期效果。

(5)通用性

傳統搜路法和A*搜路算法均基于站場型數據結構，修改容易，可移植性強；通過對多個不同的站場圖進行實驗，用A*搜路算法均能準確的搜出所需基本進路，其通用性得到了驗證。

5 結論

由于A*算法本身的高效性及啟發函數的設計而具有的完備性，使得其應用于車站進路搜索成為可能。經實驗驗證和分析，采用滿足進路搜索需求的A*算法能夠快速準確的搜出所需基本進路，動態生成進路表。綜合各種性能的優劣，總體來說，A*進路搜索算法在很多方面都優于或等同于傳統搜路法，而其不足之處在當前的仿真實驗環境下也能夠克服，達到了提高進路辦理效率的目的。

[1] 文武臣，王曉明.計算機聯鎖的數據結構及進路搜索算法[J].重慶工學院學報：自然科學版，2008，22(6):51-53.

[2] George F.LUGER.人工智能[M].史忠植，等，譯.北京:機械工業出版社，2006:96-103.

[3] 劉浩，鮑遠律.A*算法在矢量地圖最優路徑搜索中的應用[J].計算機仿真，2008，25(4):253-256.

[4] 王曉明，郭進，姚琨嵐.鐵路車站信號選路中圖論應用的研究[J].鐵道學報，1989，11(2):52-57.

[5] 李明哲.圖論及其算法[M].北京:機械工業出版社，2010.

[6] 趙志熙.計算機聯鎖系統技術[M].北京:中國鐵道出版社，2008.

[7] 王瑞峰.鐵路信號運營基礎[M].北京:中國鐵道出版社，2008:85-93.

[8] Michael MAIN， Walter SAVITCH.數據結構與面向對象程序設計[M].劉東，張麗，譯.北京:清華大學出版社，2007:480-484.

[9] B V Cherkassky， A V Goldberg and Tomasz Radzik. Shortest paths algorithms: Theory and Experimental Evaluation[R]. Technical Report 9321480， Computer Science Department， Stanford University， 1993.