基于距離的線路數據反推算法

郁文斌

（北京全路通信信號研究設計院集團有限公司，北京 100070）

1 概述

線路數據配置的設計與實現是高鐵信號產品基于線路數據進行計算的前提。目前高鐵信號地面安全產品，如無線閉塞中心、臨時限速服務器、列控中心等，對于線路數據配置的有關距離的計算比較多，但是在數據設計和數據測試時，對于龐大的工程數據，需要根據輸入點和距其相對距離得到對應的輸出點。這些如果由人工進行計算，工作量巨大，尤其是目前高鐵營業里程超4萬km，對于任何設備提供商，這些數據的計算如果僅由人工來完成，是無法想象的。因此需要提供輔助工具以自動化的形式來實現，提供一種有效的算法是必要且非常有意義的。

2 引用算法介紹

以基于距離的線路數據處理算法和基于散列的長鏈算法為基礎進行設計，建立在此兩種算法的基礎上設計一種新的算法。本文介紹的反推算法是上述兩種算法的實際應用。

2.1 基于距離的線路數據處理算法

根據文獻[1]，基于距離的線路數據處理算法目的是提供給數據配置用戶對于線路數據配置規則的制定，而不是由研發用戶固化到軟件中，使得數據配置靈活且統一。同時，對研發用戶屏蔽了數據配置規則，使線路數據計算根據用戶需求由給定的輸入點輸出距離線路邏輯數據起點的相對距離，獲取到與線路數據相關的大小比較、范圍判斷、距離計算的參數。本文的算法仍舊是對工程數據配置的處理，因此，對于數據配置，本文直接引用文獻[1]的結論。文獻[1]中的下列定義仍舊是本文的基礎：

定義1.工程規定的正向線路方向（DIR），也是其他方向定義的基準或者參考方向，與DIR同向，以SAME_DIRECTION標記，與DIR反向，以CONVERSE_DIRECTION標記；

定義2.數據配置方向（UCDIR），其涉及到分段配置方向，段內數據配置方向；

定義3.用戶計算方向（USDIR），也就是運行的實際方向；

定義4.長鏈的配置起點（LCS），與方向無關，帶有長鏈標志；

定義5.長鏈的配置終點（LCE），與方向無關，不帶長鏈標志；

定義6.長鏈的配置長度（LCL）；

定義7.USDIR方向，線路的邏輯第一個分段（LLS）；

定義8.USDIR方向，線路的邏輯最后一個分段（LLE）；

定義9.USDIR方向，分段內的邏輯起點（LSS）；

定義10.USDIR方向，分段內的邏輯終點（LSE）；

定義11.USDIR方向，長鏈的邏輯起點（LFS）；

定義12.USDIR方向，長鏈的邏輯終點（LFE）。

2.2 基于散列的長鏈算法

根據文獻[2]，輸入點和距輸入點相對距離的輸出點均可能落入長鏈范圍，需要進行長鏈點的處理和計算，同時進行長鏈標志的判斷和校驗，文獻[2]提供的散列算法可以解決此問題。

3 基于距離的反推算法

如果是普通的線路計算，根據輸入點PI和距輸入點的相對距離D獲取輸出點PO，僅僅通過簡單的數學邏輯運算即可實現。但是，鐵路的線路數據存在工程的復雜性，具有不同里程標系而造成的分段及里程標系轉換，而且還有斷鏈，其中長鏈的處理也增加計算的復雜度，同時，列車運行可以以線路的正向和反向兩個方向運行，從而使得線路數據的處理和計算復雜度增加。

例如，在列車運行方向上，如果輸入點是一個邏輯分段起點，若要獲取距離其反向1 m的輸出點，即相對距離-1的輸出點，此點已落入了其后方段中。如果輸入點是一個長鏈的邏輯起點后方1 m的里程點，若要獲取其前方1 m的輸出點，即相對距離+1的輸出點，此點已落入此長鏈范圍內，即輸出點具有長鏈標志。因此，通過常規的數學運算不可能實現距離的計算，需要設計一種新的算法來解決此問題。

3.1 場景分析

分析上述的例子，如果以正向思維根據PI和D兩個參數推導出輸出點PO，難度比較大。不妨進行逆向思維考慮，假設已經獲取PO點，那么根據文獻[1]，z(PO)－z(PI)=D。

1）如果z(PO)>z(PI),D>0，在線路邏輯方向上，PO位于PI前方。

2）如果z(PO)=z(PI),D=0，在線路邏輯方向上，PO與PI重疊。

3）如果z(PO)

根據位置的不同，定義分段i，段內長鏈為ni，區間分類數為ci(ni)，總共場景數為qi(ni)。

考慮一個分段，根據區間的不同分為以下幾種情況。

1）如果1個線路只有1個分段，分段內無長鏈，則分為段邏輯起點外、段內、段邏輯終點外3個區間，加上段邏輯起點和段邏輯終點，分為5種情況。c0(0)=3，場景數為q0(0)=5。

2）如果一個線路只有一個分段，分段內有一個長鏈，那么可以分為段邏輯起點外、段內長鏈邏輯起點外、段內長鏈范圍內、段內長鏈邏輯終點外、段邏輯終點外5個區間，加上段邏輯起點、段邏輯終點、長鏈邏輯起點、長鏈邏輯終點，分為9種情況。c0(1)=5，場景數為q0(1)=9。

3）如果一個線路只有一個分段，分段內兩個長鏈，那么可以分為段邏輯起點外、段內第一個長鏈邏輯起點外、段內第一個長鏈范圍內、段內第一個長鏈邏輯終點外且第二個長鏈邏輯起點外、段內第二個長鏈范圍內、段內第二個長鏈邏輯終點外、段邏輯終點外7個區間，加上段邏輯起點、段邏輯終點、第一個長鏈邏輯起點、第一個長鏈邏輯終點，第二個長鏈邏輯起點、第二個長鏈邏輯終點，分為13種情況。c0(2)=7，場景數為q0(2)=13。

4）根據上述規律，以此類推，使用歸納總結法，可以推導出c0(n0)=c0(n0－1)＋2,n0>1,c0(0)=3，場景數q0(n0)=c0(n0)×2－1。因此c0(n0)= 2n0＋3,n0≥0,q0(n0)=4n0＋5,n0≥0。

考慮兩個分段，根據區間的不同分為以下幾種情況。

1）如果一個線路有兩個分段，分段均無長鏈，那么可以分為第一段邏輯起點外、第一段內、第一段邏輯終點外、第二段邏輯起點外、第二段內、第二段邏輯終點外6個區間，加上第一段和第二段的邏輯起點和終點，分為10種情況。場 景 數 為

2）如果一個線路有兩個分段，第一分段內存在長鏈，那么可以分為第一段邏輯起點外、第一段內長鏈邏輯起點外、第一段內長鏈范圍內、第一段內長鏈邏輯終點外、第一段邏輯終點外、第二段邏輯起點外、第二段內、第二段邏輯終點外8個區間，加上第一段和第二段的邏輯起點和終點，第一段長鏈邏輯起點和終點，分為14種情況。場景數

4）根據上述規律，依次類推，對于任意分段數m，對于第i段內任意長鏈數 ，使用歸納總結法，可以建立推導公式：

3.2 算法設計

可以根據公式（2）的e(m,n)對應的場景進行處理，那么只要知道區分公式（1）的d(m,n)對應的分界點值即可，總共需要e(m,n)－d(m,n)個值的分界點，進行計算4種分界距離的計算：段邏輯起點距線路邏輯起點的距離DSS，段邏輯終點距線路邏輯起點的距離DSE，長鏈邏輯起點距線路邏輯起點的距離DLS，長鏈邏輯終點距線路邏輯起點的距離DLE，在此基礎上實現反推計算。

若要獲取DSS、DSE、DLS、DLE，則需使用文獻[1]中如公式（3）～（10）所示。

其中，公式（3）為給定帶有長鏈點返回對應配置的長鏈終點；公式（4）為給定帶有長鏈點返回對應配置的長鏈所在的下標，即線路上的第幾個長鏈點；公式（5）為給定輸入點，返回USDIR方向所在的分段索引；集合（6）為與輸入點同屬一個分段內的所有長鏈配置點，且USDIR方向，在輸入點前方的所有長鏈點；集合（7）為USDIR方向，分段x內的所有長鏈點；公式（8）為輸入點所在段的前方所有段并包含其中所有長鏈點的距離；公式（9）為USDIR方向，輸入點所在段中，距離段邏輯起點并包含長鏈點的距離；公式（10）為USDIR方向，輸入點具有長鏈標志時，對于其距長鏈邏輯起點的距離，根據長鏈散列算法進行實現。

因此，對于任意段i,DSS=s(LSSi)＋f(LSSi),DSE=s(LSEi)＋f(LSEi),DLS=s(LFSi)＋f(LFSi)，結合公式（1）、（2），可以判斷出輸出點落到了公式（2）對應的哪種場景，并且可以獲得對應此種場景中距段邏輯起點的距離，因此可以得到輸出點的里程標具體參數，提供給用戶。

本算法是基于文獻[1-2]設計的線性算法，因此算法復雜度與文獻[1-2]保持一致，為O(m＋n)，m為線路分段數，n為線路長鏈數。

4 算法實現

根據公式（1）～（10）進行算法實現，程序設計邏輯如圖 1所示。

圖1 程序邏輯Fig.1 Program logic diagram

為完成上述程序邏輯，即根據公式（1）～（8）實現算法，需進行功能實現，主要功能如表 1所示。

表 1 算法實現功能列Tab.1 Algorithm implementation function list

5 測試驗證

根據程序實現的線路數據反推算法設計案例進行驗證。設計案例的原則為考慮各種數據配置規則下每種線路分段、段內遞增減、段內長鏈情況，劃分等價類，每種等價類需要對邊界值設定案例，以此檢驗反推算法的邏輯是否正確。設定線路場景案例如表 2所示。

表 2 測試案例場景Tab.2 Test case scenario

根據上述場景，考慮設置輸入點與輸出點所在公式（2）同一場景和不同場景，總共設計案例100個。

測試結果正確，確認算法功能符合預期。

6 總結

本文在基于距離的線路數據處理算法和基于散列的長鏈算法基礎上，提出一種基于距離的線路數據反推算法。給定線路數據上任意的輸入點和距其的相對距離，獲得對應的線路輸出點。擴展了算法的功能，從而擴大線路數據計算的使用范圍。使站內側線映射正線、正線跨線根據已知線路信息推導出計算所需的信息，應用于線路數據設計和自動化測試所需的預期結果計算。

本算法目前主要考慮在數據設計、校驗、測試的使用，可以考慮提供給腳本語言的接口，在軟件開發中直接調用，尤其應用于產品自動化測試的預期結果計算應用，均可以作為對于后續工作的展望。