基于深度優先的鐵路站場圖遍歷算法研究

馬新宇MA Xin-yu

（武漢鐵路橋梁職業學院，武漢 430090）

1 鐵路站場數據結構

鐵路車站信號設備通常由信號機、軌道區段、道岔、絕緣節等組成，且他們相互之間存在連接關系。信號機是一種用來表示固定信號意義的設備，對鐵路運輸生產起到指引作用。道岔設備存在于鐵路區間或鐵路車站，主要用來改變列車的運行方向。軌道電路通常安裝在鐵路車站內，用來檢查某一區段是否空閑，通常我們使用軌道絕緣將軌道電路劃分為不同的區段，用以檢測軌道電路是否被列車占用。

我們以車站中心線為界，將車站劃分為左右兩個部分，分別稱為上行咽喉區域和下行咽喉區域。上行方面對應的是下行咽喉，下行方面對應的是上行咽喉。兩個咽喉區的拓撲模型建立方法是完全相同的，故只需討論其中一個咽喉區即可。將信號機、道岔、軌道區段等鐵路站場圖元按照一定的順序和規則連接起來，那么它們在站場中所處的位置及相互關系構成站場的設備數據結構，如圖1 所示。

圖1 站場數據結構

2 鐵路車站站場數據拓撲建模

2.1 站場有向圖拓撲結構

我們運用計算機讀取鐵路車站信號設備之間的連接關系從而實現對鐵路車站站場圖的遍歷。然而原始的站場圖無法直接被計算機識別，需要對其進行數據轉換，在此我們運用計算機圖論相關知識進行拓撲建模。一個有向圖G 通常表示為G=（V，E），其中，G 表示一個圖，集合V={v1，v2，…，vn}是包含n 個頂點的集合，集合E={e1，e2，…em}是包含m 條邊的集合，每一條邊ei都是集合V 的二元素子集{vi，vj}。如果把信號設備看作圖中的各個節點，信號設備之間的連接關系看作圖中的邊，那么整個站場網絡就可以被抽象成一個有向圖G=（V，E），其中V 表示信號設備集合，E 表示信號設備之間的連接關系集合。

盡管站場圖中各設備的連接沒有方向，但是車站的進路是有方向的。通過對鐵路站場的進路信息數據的研究發現，站場的進路辦理可以劃分為不同的咽喉進行。為加快計算機的運算速率，降低站場拓撲數據構建的復雜度，我們將站場有向圖依據咽喉不同，并根據進路的方向性將站場圖按照下行方向建立模型，劃分為兩個規模較小的站場有向圖，依次構建拓撲數據。所構建的左咽喉區的有向圖模型如圖2 所示。

2.2 站場有向圖鄰接矩陣

生成有向圖之后，即確定了站場圖中設備之間的連接關系，接下來需要將有向圖進一步轉換為計算機可直接讀取識別的數據，再利用圖論的知識對站場圖元數據進行搜索。對有向圖中的數據存儲我們使用圖的鄰接矩陣實現。圖的鄰接矩陣不但可以表示有向圖中各個頂點之間是否有路徑直接連通，還可以表示兩頂點之間的有向圖的方向。在有向圖G 中，圖的節點集合V={v1，v2，…vn}，則鄰接矩陣表示為A=（aij）n×n，若aij=1，則表示vi有指向vj的邊；若aij=0，則表示vi無指向vj的邊。按照此中計算方法，得出圖2 中的左咽喉區有向圖拓撲圖的部分鄰接矩陣如圖3所示。

圖2 左咽喉區有向圖拓撲模型

圖3 左咽喉區有向圖鄰接矩陣（部分）

3 進路搜索算法研究與實現

3.1 深度優先算法

通過建立站場信號平面布置圖拓撲結構，我們可以將抽象的圖元信息數據轉換為相對具體的有向圖模型，將各個設備間的連接關系轉換為可供計算機讀取的數據信息，以便計算機可以快速讀取和識別。本文選擇了以鄰接矩陣法來進行有向圖數據的存儲。運用深度優先搜索方法來進行站場圖元數據的遍歷。

深度優先搜索算法又稱為DFS 算法，是一種從始端節點起按樹結構的某一支不斷加深搜索深度，從一條道走到黑的搜索方法。相對于廣度優先搜索算法而言，深度優先搜索算法在運算過程中所消耗的內存比較小，且在搜索的過程中對搜索的方向可以做一定的優化和限制，比如在搜索道岔節點時，可以規定在搜索過程中是以定位優先搜索還是以反位優先搜索，增大搜索到目標節點的概率。但是深度優先搜索方法也存在一定的弊端，在搜索的過程中如果在某一支路上找不到目標節點時，需要回溯到上一支路進行搜索，導致有時找到目標節點需要花費較多的時間。

3.2 算法的實現

3.2.1 符號定義

①數組Arr：存儲站場信號平面布置圖中的信號設備信息；

②數組Mar：存放鄰接矩陣；

③XN、XA、i、j：變量；

④數組ST：存放始端設備名稱；

⑤數組EN：存放終端設備名稱；

⑥XA、XN：用來存放當前設備的坐標。

3.2.2 算法描述

由于對左右咽喉區的建模方法完全一致，本文以左側咽喉區域為例進行有向圖的計算機存儲方法介紹。首先逐一對數組Arr 中的設備數據進行遍歷，讀取當前設備Arr[i]，依次分別讀取當前設備Arr[i]的前端、后端以及側端連接設備，將上述設備讀取到EN 中。查找在Arr 中EN 的下標j，讀取Arr[i]的X 坐標XA、EN 的X 坐標XN，對比XA和XN 的大小，如果XA>XN，表示Arr[i]在EN 的右端，則鄰接數組Mar[i][j]的值改為1；如果XAXN，表示Arr[i]在EN 的右端，則鄰接數組Mar[j][i]的值改為1；如果XA

①初始化狀態變量i=j=0、fro=beh=sid=true。

②讀取Arr 中下標為i 的設備Arr[i]。

③判斷Arr [i]的前端連接設備是否為空且狀態變量fro 的值不為真，如果是轉到⑤，否則轉到④。

④讀取Arr[i]的前端設備為EN，將狀態變量fro 的值改為假，用以標記當前設備前端連接設備已被訪問過。轉到?。

⑤判斷Arr [i]的后端連接設備是否為空且狀態變量beh 的值不為真，如果是轉到⑦，否則轉到⑥。

⑥讀取Arr[i]的后端設備為EN，將狀態變量beh 的值改為假，用以標記當前設備后端連接設備已被訪問過。轉到?。

⑦判斷Arr [i]的側端連接設備是否為空且狀態變量sid 的值不為真，如果是轉到⑨，否則轉到⑧。

⑧讀取Arr[i]的側端設備為EN，將狀態變量sid 的值改為假，用以標記當前設備側端連接設備已被訪問過。跳轉到?。

⑨i 的值自增1。

⑩判斷Arr 中下標為i 的元素是否為空。如果是，轉到?，否則轉到①。

?在數組Arr 中讀取EN 的下標j。

?讀取EN 的X 坐標XN；Arr[i]的X 坐標XA。

?判斷EN 和Arr[i]的坐標大小，如果XN>XA 轉到?，否則轉到?。

?將鄰接數組Mar[j][i]的值改為1。轉到④。

?將鄰接數組Mar[i][j]的值改為1。轉到④。

?初始化變量i=0；j=0。

?i 值是否小于Mar 數組長度，如果是轉到?，否則轉到?。

?j 值是否小于鄰接數組Mar 的長度，如果是，轉到?，否則轉到?。

?i 的值加1。

?Mar[i][j]的值是否為1，如果是，轉到?，否則轉到?。

?在Arr 中讀取i 的設備，存放到數組ST 中。

?在Arr 中讀取j 的設備，存放到數組EN 中。轉到?。

?j 值自增1。轉到?。

?結束。

按照上述方法計算左側咽喉區域的圖元數據如表1所示。

表1 小橋站左咽喉區設備圖元數據

4 結語

在實際的鐵路運輸生產環境中，具體采用哪一種站場數據拓撲結構存儲、選用何種搜索算法需要根據車站的實際情況、設備的多少有針對性的設計。但無論采用何種方法，都要堅持提高搜索效率、節省存儲空間、使用便捷等原則，保證算法高效、數據結構存儲合理、邏輯清晰等要求。本文通過對鐵路車站站場圖設備布置情況進行分析，運用計算機圖論的相關知識將車站信號平面布置圖抽象分為拓撲圖結構，設計了適用于鐵路車站站場圖的進路搜索算法，算法設計上提高了內存空間利用率，也提高了遍歷效率。