基于距離的線路數(shù)據(jù)反推算法

郁文斌

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

1 概述

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

2 引用算法介紹

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

2.1 基于距離的線路數(shù)據(jù)處理算法

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

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

定義2.數(shù)據(jù)配置方向（UCDIR），其涉及到分段配置方向，段內(nèi)數(shù)據(jù)配置方向；

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

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

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

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

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

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

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

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

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

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

2.2 基于散列的長鏈算法

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

3 基于距離的反推算法

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

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

3.1 場景分析

分析上述的例子，如果以正向思維根據(jù)PI和D兩個參數(shù)推導(dǎo)出輸出點PO，難度比較大。不妨進行逆向思維考慮，假設(shè)已經(jīng)獲取PO點，那么根據(jù)文獻[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)

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

考慮一個分段，根據(jù)區(qū)間的不同分為以下幾種情況。

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

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

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

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

考慮兩個分段，根據(jù)區(qū)間的不同分為以下幾種情況。

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

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

4）根據(jù)上述規(guī)律，依次類推，對于任意分段數(shù)m，對于第i段內(nèi)任意長鏈數(shù) ，使用歸納總結(jié)法，可以建立推導(dǎo)公式：

3.2 算法設(shè)計

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

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

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

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

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

4 算法實現(xiàn)

根據(jù)公式（1）～（10）進行算法實現(xiàn)，程序設(shè)計邏輯如圖 1所示。

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

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

表 1 算法實現(xiàn)功能列Tab.1 Algorithm implementation function list

5 測試驗證

根據(jù)程序?qū)崿F(xiàn)的線路數(shù)據(jù)反推算法設(shè)計案例進行驗證。設(shè)計案例的原則為考慮各種數(shù)據(jù)配置規(guī)則下每種線路分段、段內(nèi)遞增減、段內(nèi)長鏈情況，劃分等價類，每種等價類需要對邊界值設(shè)定案例，以此檢驗反推算法的邏輯是否正確。設(shè)定線路場景案例如表 2所示。

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

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

測試結(jié)果正確，確認算法功能符合預(yù)期。

6 總結(jié)

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

本算法目前主要考慮在數(shù)據(jù)設(shè)計、校驗、測試的使用，可以考慮提供給腳本語言的接口，在軟件開發(fā)中直接調(diào)用，尤其應(yīng)用于產(chǎn)品自動化測試的預(yù)期結(jié)果計算應(yīng)用，均可以作為對于后續(xù)工作的展望。