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

1、3蘭州交通大學(xué)自動(dòng)化與電氣工程學(xué)院碩士研究生, 730070蘭州33蘭州交通大學(xué)自動(dòng)化與電氣工程學(xué)院教授, 730070蘭州333鐵道科學(xué)研究院通信信號(hào)研究所研究實(shí)習(xí)員, 100081北京收稿日期:2007201209計(jì)算機(jī)聯(lián)鎖進(jìn)路搜索算法的分析與研究陳志穎3董昱33楊柳3李亮333摘要:簡(jiǎn)述了計(jì)算機(jī)聯(lián)鎖系統(tǒng)中站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)的建立方法, 通過深入研究站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)形狀與二叉樹的相似性, 結(jié)合在實(shí)際搜索進(jìn)路過程中總結(jié)的經(jīng)驗(yàn), 提出了一種基于站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)的新的進(jìn)路搜索算法。該算法是結(jié)合了二叉樹、四叉鏈表和高度原則的新的進(jìn)路搜索算法。詳細(xì)論述了這種算法, 并給出了完整的描述。關(guān)鍵詞:計(jì)算機(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ì)算機(jī)聯(lián)鎖系統(tǒng)是鐵路及城市軌道交通信號(hào)系統(tǒng)中一個(gè)重要的子系統(tǒng), 通進(jìn)路內(nèi)的道岔、信號(hào)機(jī)、鎖關(guān)系, 存利用問題, 樹、四叉鏈表和高度原則的新進(jìn)路搜索算法。1 站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)圖1舉例信號(hào)平面布置圖如果把信號(hào)平面圖中的信號(hào)設(shè)備作為信號(hào)點(diǎn)圖中的點(diǎn), 則信號(hào)點(diǎn)圖由邊集合和點(diǎn)集合組成, 將這些設(shè)備在信號(hào)平面布置圖中的位置進(jìn)行連接, 就可以得到與信號(hào)平面布置圖相對(duì)應(yīng)的信號(hào)點(diǎn)圖。其中, 每個(gè)節(jié)點(diǎn)由2部分組成:表示本節(jié)點(diǎn)特性的數(shù)據(jù)域df 和表示相鄰節(jié)點(diǎn)關(guān)系的指針域pf , 即站場(chǎng)。圖2所示 。圖2站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)2搜索算法進(jìn)路就是由若干個(gè)信號(hào)機(jī)、道岔及道岔位置、軌道區(qū)段組成的車列在車站內(nèi)運(yùn)行時(shí)所經(jīng)過的通路

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

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

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

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

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

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

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

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