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

郁文斌

（北京全路通信信號(hào)研究設(shè)計(jì)院集團(tuán)有限公司，北京 100070）

1 概述

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

2 引用算法介紹

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

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

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

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

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

定義3.用戶計(jì)算方向（USDIR），也就是運(yùn)行的實(shí)際方向；

定義4.長(zhǎng)鏈的配置起點(diǎn)（LCS），與方向無(wú)關(guān)，帶有長(zhǎng)鏈標(biāo)志；

定義5.長(zhǎng)鏈的配置終點(diǎn)（LCE），與方向無(wú)關(guān)，不帶長(zhǎng)鏈標(biāo)志；

定義6.長(zhǎng)鏈的配置長(zhǎng)度（LCL）；

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

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

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

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

定義11.USDIR方向，長(zhǎng)鏈的邏輯起點(diǎn)（LFS）；

定義12.USDIR方向，長(zhǎng)鏈的邏輯終點(diǎn)（LFE）。

2.2 基于散列的長(zhǎng)鏈算法

根據(jù)文獻(xiàn)[2]，輸入點(diǎn)和距輸入點(diǎn)相對(duì)距離的輸出點(diǎn)均可能落入長(zhǎng)鏈范圍，需要進(jìn)行長(zhǎng)鏈點(diǎn)的處理和計(jì)算，同時(shí)進(jìn)行長(zhǎng)鏈標(biāo)志的判斷和校驗(yàn)，文獻(xiàn)[2]提供的散列算法可以解決此問(wèn)題。

3 基于距離的反推算法

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

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

3.1 場(chǎng)景分析

分析上述的例子，如果以正向思維根據(jù)PI和D兩個(gè)參數(shù)推導(dǎo)出輸出點(diǎn)PO，難度比較大。不妨進(jìn)行逆向思維考慮，假設(shè)已經(jīng)獲取PO點(diǎn)，那么根據(jù)文獻(xiàn)[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)長(zhǎng)鏈為ni，區(qū)間分類數(shù)為ci(ni)，總共場(chǎng)景數(shù)為qi(ni)。

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

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

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

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

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

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

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

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

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

3.2 算法設(shè)計(jì)

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

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

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

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

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

4 算法實(shí)現(xiàn)

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

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

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

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

5 測(cè)試驗(yàn)證

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

表 2 測(cè)試案例場(chǎng)景Tab.2 Test case scenario

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

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

6 總結(jié)

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

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