計算機(jī)聯(lián)鎖進(jìn)路搜索算法的分析與研究_圖文

1、3蘭州交通大學(xué)自動化與電氣工程學(xué)院碩士研究生, 730070蘭州33蘭州交通大學(xué)自動化與電氣工程學(xué)院教授, 730070蘭州333鐵道科學(xué)研究院通信信號研究所研究實習(xí)員, 100081北京收稿日期:2007201209計算機(jī)聯(lián)鎖進(jìn)路搜索算法的分析與研究陳志穎3董昱33楊柳3李亮333摘要:簡述了計算機(jī)聯(lián)鎖系統(tǒng)中站場型數(shù)據(jù)結(jié)構(gòu)的建立方法, 通過深入研究站場型數(shù)據(jù)結(jié)構(gòu)形狀與二叉樹的相似性, 結(jié)合在實際搜索進(jìn)路過程中總結(jié)的經(jīng)驗, 提出了一種基于站場型數(shù)據(jù)結(jié)構(gòu)的新的進(jìn)路搜索算法。該算法是結(jié)合了二叉樹、四叉鏈表和高度原則的新的進(jìn)路搜索算法。詳細(xì)論述了這種算法, 并給出了完整的描述。關(guān)鍵詞:計算機(jī)聯(lián)鎖,

2、數(shù)據(jù)結(jié)構(gòu), 二叉樹, 進(jìn)路搜索Abstract :The paper outlines t he met hod to build data st ruct ures of railway station yard layout in comp uter interlocking systems. Through st udying t he similarity of data st ruct ure of station yard layout and binary branch t ree and combining experiences form p ractical manual

3、route searching , a new route searching algorit hm was brought forward , which combined binary branch tree , quadric link list , altit ude p rinciple. A complete particular description of t he algorit hm was given. K ey w ords :Comp uterized interlocking , Data st ruct ure , Binary branch tree , sea

4、rch 計算機(jī)聯(lián)鎖系統(tǒng)是鐵路及城市軌道交通信號系統(tǒng)中一個重要的子系統(tǒng), 通進(jìn)路內(nèi)的道岔、信號機(jī)、鎖關(guān)系, 存利用問題, 樹、四叉鏈表和高度原則的新進(jìn)路搜索算法。1 站場型數(shù)據(jù)結(jié)構(gòu)圖1舉例信號平面布置圖如果把信號平面圖中的信號設(shè)備作為信號點圖中的點, 則信號點圖由邊集合和點集合組成, 將這些設(shè)備在信號平面布置圖中的位置進(jìn)行連接, 就可以得到與信號平面布置圖相對應(yīng)的信號點圖。其中, 每個節(jié)點由2部分組成:表示本節(jié)點特性的數(shù)據(jù)域df 和表示相鄰節(jié)點關(guān)系的指針域pf , 即站場。圖2所示 。圖2站場型數(shù)據(jù)結(jié)構(gòu)2搜索算法進(jìn)路就是由若干個信號機(jī)、道岔及道岔位置、軌道區(qū)段組成的車列在車站內(nèi)運行時所經(jīng)過的通路

5、。由始端按鈕和終端按鈕決定的進(jìn)路所有有關(guān)的信息, 包括進(jìn)路類型、進(jìn)路方向、進(jìn)路按鈕、道岔、軌道區(qū)段、敵對信號機(jī)、防護(hù)信號機(jī)等, 建立算法前要對這些信息進(jìn)行搜索。在建立始終端按鈕對集合后, 依次取出每個按鈕對進(jìn)行進(jìn)路搜索。在進(jìn)路搜索過程中可能存在回路, 所以在訪問完某個節(jié)點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的節(jié)點。為了避免重復(fù)訪問, 必須選擇良好的進(jìn)路搜索算法, 下面的進(jìn)路搜索算法結(jié)合了二叉樹、四叉鏈表和高度3項原則。211二叉樹數(shù)據(jù)結(jié)構(gòu)二叉樹是樹的一種, 是非線性數(shù)據(jù)結(jié)構(gòu)。圖3給出了二叉樹的圖形表示及其存儲結(jié)構(gòu)。其中A42007年4月鐵道通信信號April 12007第43卷第4期RA I

6、L WA Y SIGNALL IN G &COMMUNICA TION Vol 143No 14為根節(jié)點, D , F , G 為葉子節(jié)點。二叉樹的每個節(jié)點至多有2棵子樹, 并且, 二叉樹的子樹有左右之分, 次序不可以顛倒 。圖3二叉樹舉例及其存儲結(jié)構(gòu)圖4二叉樹建模圖二叉樹在存儲過程中采用鏈?zhǔn)酱鎯Y(jié)構(gòu), 其節(jié)點由1個數(shù)據(jù)元素和分別指向其左、右子樹的2個分支構(gòu)成, 表示二叉樹鏈表至少有3個域:數(shù)據(jù)域和左、右指針域。二叉樹的搜索可以采用圖的搜索算法, 例如:深度優(yōu)先搜索, 廣度優(yōu)先搜索。由于站場形狀和二叉樹形狀的相似性, 因此可以先把站場型數(shù)據(jù)結(jié)構(gòu)以二叉樹形式進(jìn)行建立模型, 然后通過圖的搜

7、索方法進(jìn)行搜索。對圖1的二叉樹模型如圖4所示。212四叉鏈表2個部分;指針場用于存放其鄰節(jié)點地址。因此, 通過節(jié)點的指針場可以實現(xiàn)雙向搜索。采用站場型數(shù)據(jù)結(jié)構(gòu)可以大大節(jié)省存儲空間且不必實現(xiàn)編制總進(jìn)路表, 從而減少設(shè)計工作量和避免設(shè)計錯誤, 可以使聯(lián)鎖軟件標(biāo)準(zhǔn)化和定型化。因此, 在計算機(jī)聯(lián)鎖軟件中, 為了便于按進(jìn)路方向搜索, 可以采用一種四叉雙向鏈表結(jié)構(gòu)來描述站場信號平面布置圖。其中每個節(jié)點數(shù)據(jù)域存儲站場信號平面圖中相應(yīng)位置的基本圖形及全部信息。為了描述交分道岔節(jié)點的拓?fù)湫畔? 用4個指針域p 1、p 2、p 3、p 4分別描述節(jié)點間的鄰接關(guān)系(拓?fù)潢P(guān)系信息 , 如圖5所示 。圖5節(jié)點結(jié)構(gòu)在四叉

8、雙向圖形數(shù)據(jù)結(jié)構(gòu)中:對應(yīng)每1個股道, 設(shè)有1個頭節(jié)點h i 和1組信息節(jié)點; h i和該股道上第1個信息節(jié)點指針互指, 在C T 域存有該股道的信息節(jié)點個數(shù); 4個指針域中, p 1表示本節(jié)點與同一股道結(jié)點的左鄰關(guān)系, p 2表示與同一股道節(jié)點的右鄰關(guān)系, p 3表示與不同股道節(jié)點的道岔向上鄰接關(guān)系, p 4表示與不同股道節(jié)點的向下鄰接關(guān)系。通過四叉鏈表, 可以在進(jìn)路搜索過程中提高效率。例如:因在自動搜索進(jìn)路過程中遵循直股優(yōu)先和同類渡線優(yōu)先的原則, 在搜索過程中都需要對每一條進(jìn)路進(jìn)行完全搜索, 但是有了四叉鏈表可以減少無謂的空間和時間的浪費, 這在后面的進(jìn)路流程圖中可以看出。213高度原則按鈕

9、的節(jié)點在站場圖中有的在同一個坐標(biāo)線上(縱坐標(biāo)相同 , 有的不在同一縱坐標(biāo)上, 根據(jù)辦理進(jìn)路時按鈕的高度不同建立節(jié)點高度數(shù)據(jù)庫, 把相應(yīng)的節(jié)點縱坐標(biāo)存儲起來, 這樣在辦理進(jìn)路時, 可, 滿足后輩節(jié)點低1始端節(jié)點低于目標(biāo)節(jié)點, 滿足后輩節(jié)點高于始端節(jié)點進(jìn)行搜索。31始端節(jié)點等于目標(biāo)節(jié)點, 滿足后輩節(jié)點等于始端節(jié)點進(jìn)行搜索。例如:圖1中假設(shè)辦理D 7至S 3的調(diào)車進(jìn)路, 首先看目標(biāo)節(jié)點與始端節(jié)點的縱坐標(biāo)位置, 應(yīng)為S 3的縱坐標(biāo)大于D 7的縱坐標(biāo), 所以在搜索中不斷比較后輩節(jié)點與始端節(jié)點的高度差, 為正值時(向上搜索 繼續(xù), 否則返回。3算法建立311術(shù)語與符號的定義11對向道岔:沿搜索方向使1個軌

10、道分為2個軌道的道岔。21渡線:指連接2個平行軌道之間的軌道。31起始節(jié)點K 0:按發(fā)車方向進(jìn)行搜索的指定起始節(jié)點。41中間節(jié)點K i :與變更按鈕相對應(yīng)的指定節(jié)點。51目標(biāo)節(jié)點K g :按發(fā)車方向進(jìn)行搜索時所要找到的最終指定節(jié)點。G 用于存放目標(biāo)節(jié)點。61后繼節(jié)點K c :在站場圖的數(shù)據(jù)結(jié)構(gòu)中, 有方向的直線箭頭所指的節(jié)點。71后繼直節(jié)點K z :在站場圖的數(shù)據(jù)結(jié)構(gòu)中道岔節(jié)點直股方向的后繼節(jié)點。5RA IL WA Y SIGNALL IN G &COMMUN ICA TION Vol 143No 142007 圖6進(jìn)路搜索流程圖81后繼彎節(jié)點K w :在站場圖的數(shù)據(jù)結(jié)構(gòu)中道岔節(jié)點彎股

11、方向的后繼節(jié)點。91死節(jié)點K d :在站場圖的數(shù)據(jù)結(jié)構(gòu)中沒有后繼節(jié)點的節(jié)點。101渡線類型Cro ssing 2Line :用于存放渡線的類型,其值有撇型“/”和捺型“”。L :存放渡線類型。111彎股優(yōu)先標(biāo)志Sid 2ingPriority :在搜索中遇到道岔時是否要沿彎股進(jìn)行搜索。121堆棧S :用來存放起始、中間、目標(biāo)節(jié)點。131堆棧S1:用來存放搜索過程中需要考察的節(jié)點。141堆棧S2:用來存放搜索過程中需要保存的路徑上的節(jié)點。151P1:程中起始節(jié)點, 的節(jié)點的縱坐標(biāo)。161P2:用來存放搜索過程中目標(biāo)節(jié)點的縱坐標(biāo)。171D :存放節(jié)點的比較差值。181堆棧S3:用來存放起始、中間、

12、目標(biāo)節(jié)點的縱坐標(biāo)。312流程圖的建立進(jìn)路搜索流程圖如圖6所示。313算法比較與分析該算法是從建立節(jié)點序列開始, 流程圖中核心的部分是搜索的條件判斷, 通過對節(jié)點的性質(zhì)(死節(jié)點、對向道岔、征用標(biāo)志 進(jìn)行判斷, 并且利用二叉樹建立節(jié)點關(guān)系, 通過高度原則進(jìn)行進(jìn)路搜索, 從而建立了進(jìn)路搜索的新方法。舉例分析:如圖7所示, 搜索D 7至S 3進(jìn)路, 在舊的算法中多搜索了一步, 即在D 13的進(jìn)棧和出棧時需占用內(nèi)存和耗費時間, 箭頭方向為搜索的順序; 新算法對二叉樹節(jié)點的搜索如圖8所示, 它達(dá)到了節(jié)省空間和時間的效果。當(dāng)對于比較大的站場來說搜索進(jìn)路用改進(jìn)的算法會達(dá)到更好的效果 。圖7進(jìn)路搜索圖(舊算法 圖8節(jié)點搜索圖(新算法4結(jié)論在工程實踐中, 條件往往不完全符合理想狀態(tài)。因此, 根據(jù)實際狀況所設(shè)計的算法和原有的模型進(jìn)行結(jié)合可以產(chǎn)生新的算法, 達(dá)到事半功倍的效果。