基于二叉樹的站場(chǎng)信號(hào)平面進(jìn)路搜索

在計(jì)算機(jī)鎖閉系統(tǒng)和分散自律組織的集中系統(tǒng)中，必須根據(jù)現(xiàn)場(chǎng)的信號(hào)方案來確定車站的進(jìn)入清單。進(jìn)路搜索是這些系統(tǒng)的核心部分之一。如何高效、方便、準(zhǔn)確地進(jìn)行進(jìn)路搜索是一個(gè)關(guān)鍵的問題。從前曾提出的基于二叉樹的進(jìn)路搜索方法和基于圖的進(jìn)路搜索方法,均存在一定的不足,前者由于站場(chǎng)數(shù)據(jù)模塊不完全具有二叉樹的特點(diǎn),存在適應(yīng)性方面的不足;后者具有較高的復(fù)雜性。因此,在分析站場(chǎng)信號(hào)平面圖的基礎(chǔ)上,提出對(duì)站場(chǎng)信號(hào)平面圖建立有向無環(huán)圖模型,并且在有向無環(huán)圖中動(dòng)態(tài)生成二叉樹,進(jìn)而遍歷二叉樹,最終求得進(jìn)路的方法。1數(shù)據(jù)結(jié)構(gòu)1.1叉樹的結(jié)構(gòu)二叉樹(binarytree)t是有限個(gè)元素的集合(可以為空)。當(dāng)二叉樹非空時(shí),其中有一個(gè)稱為根的元素,余下的元素(如果有的話)被組成2個(gè)二叉樹,分別稱為t的左子樹和右子樹,結(jié)構(gòu)圖如圖1所示。二叉樹最常用的描述方法是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),它是指用鏈表來表示一棵二叉樹,即用鏈來指示元素的邏輯關(guān)系。鏈表中每個(gè)結(jié)點(diǎn)由3個(gè)域組成,除了數(shù)據(jù)域外,還有2個(gè)指針域,分別給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如圖2所示。其中,data域存放某結(jié)點(diǎn)的數(shù)據(jù)信息,lchild與rchild分別存放指向左孩子和右孩子的指針。當(dāng)左孩子或右孩子不存在時(shí),相應(yīng)指針域值為空(用符號(hào)∧或Null表示)。1.2樹內(nèi)種dag一個(gè)無環(huán)的有向圖稱作有向無環(huán)圖(directedacyclinegraph),簡(jiǎn)稱為DAG圖,它是一類比樹更一般的特殊有向圖,如圖3所示。DAG圖有2個(gè)主要特點(diǎn):①圖中的結(jié)點(diǎn)可以通過有向邊連接;②如果存在一個(gè)有向路徑從結(jié)點(diǎn)a連接到結(jié)點(diǎn)b,那么,必然不存在一個(gè)可以從結(jié)點(diǎn)b連接到結(jié)點(diǎn)a的有向路徑。2網(wǎng)絡(luò)結(jié)構(gòu)分析與建模2.1信號(hào)設(shè)備的設(shè)置圖4所示為一個(gè)典型的車站信號(hào)平面布置圖的一部分。站場(chǎng)股道的中垂線把站場(chǎng)分成左、右2個(gè)咽喉。在2個(gè)咽喉區(qū)內(nèi)建模的方法是相同的。下面只對(duì)1個(gè)咽喉區(qū)進(jìn)行討論。一個(gè)鐵路站場(chǎng)中需要控制的信號(hào)設(shè)備主要有信號(hào)機(jī)、與道岔相關(guān)聯(lián)的轉(zhuǎn)轍機(jī)和軌道電路。車站信號(hào)平面中有3種設(shè)備類型:信號(hào)機(jī)、道岔和區(qū)段。進(jìn)路主要的組成設(shè)備也是這3種。2.2有向無環(huán)圖求解在站場(chǎng)信號(hào)平面布置圖中的信號(hào)機(jī)、道岔端點(diǎn)、區(qū)段端點(diǎn)中提取關(guān)鍵結(jié)點(diǎn),可以將信號(hào)平面布置圖簡(jiǎn)化為如圖5所示的站場(chǎng)示意圖。以圖5為例,在左咽喉區(qū)進(jìn)行接車作業(yè)時(shí),以圖中關(guān)鍵結(jié)點(diǎn)為頂頭,以連接關(guān)鍵結(jié)點(diǎn)的設(shè)備(道岔或區(qū)段)為弧、以下行方向作為有向無環(huán)圖弧的方向,建立站場(chǎng)的有向無環(huán)圖模型(圖6)。這樣將進(jìn)路搜索問題等價(jià)于在一個(gè)有向無環(huán)圖中,可搜索一個(gè)源點(diǎn)到匯點(diǎn)之間的所有路徑。例如東郊方面到5股道的接車進(jìn)路,就等價(jià)于從頂點(diǎn)S到M的路徑(圖6存在S-H-G-F-L-M的路徑)。直接求解有向無環(huán)圖兩點(diǎn)之間所有路徑較為復(fù)雜,而且通過觀察發(fā)現(xiàn),在站場(chǎng)基礎(chǔ)上建立的有向無環(huán)圖有其特殊性。在不存在三開道岔或更為復(fù)雜的交叉設(shè)備的情況下,有向無環(huán)圖中頂點(diǎn)的出度數(shù)小于等于2。這樣的有向無環(huán)圖與二叉樹存在相似性和關(guān)聯(lián)性。因此,現(xiàn)提出一種在有向無環(huán)圖中動(dòng)態(tài)建立二叉樹,再對(duì)二叉樹進(jìn)行遍歷,從而求出頂點(diǎn)之間的所有路徑,也就是進(jìn)路的方法。3基于根控制進(jìn)路的搜索下面以東郊方面向各股道接車進(jìn)路為例說明進(jìn)路搜索算法。選擇進(jìn)路的起點(diǎn)S,作為二叉樹的根,并作為當(dāng)前結(jié)點(diǎn),若當(dāng)前結(jié)點(diǎn)的出度數(shù)為2,則第1條弧所指向的頂點(diǎn)為其左孩子,第2條弧所指向的頂點(diǎn)為其右孩子,若當(dāng)前結(jié)點(diǎn)的出度數(shù)為1,則弧所指向的頂點(diǎn)為其左孩子,若當(dāng)前結(jié)點(diǎn)的出度數(shù)為0,則其為葉子結(jié)點(diǎn),再選擇子結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn),以此類推,建立以S為根的二叉樹(圖6)。遍歷以S為根的二叉樹,從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑,就是東郊方面到各股道的進(jìn)路。二叉樹遍歷的訪問順序有3種:先序遍歷、中序遍歷和后序遍歷。本系統(tǒng)采用先序遍歷,它的遞歸過程為:若二叉樹為空,遍歷結(jié)束;否則,首先訪問根結(jié)點(diǎn),再遍歷根結(jié)點(diǎn)的左子樹,最后遍歷根結(jié)點(diǎn)的右子樹。進(jìn)路自動(dòng)生成搜索算法如下。1.建立1個(gè)空棧stack1用于保存搜索路徑,設(shè)置根結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)。2.判斷二叉樹BiTree是否為空,如果為空,則遍歷結(jié)束。3.將當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域壓入棧stack1的棧頂。4.判斷當(dāng)前結(jié)點(diǎn)是否是葉子結(jié)點(diǎn),如果是葉子結(jié)點(diǎn),保存棧stack1的內(nèi)容(當(dāng)前棧stack1的內(nèi)容為一條進(jìn)路)。5.訪問結(jié)點(diǎn)的左子樹。6.訪問結(jié)點(diǎn)的右子樹。7.棧stack1的棧頂元素出棧。圖8是對(duì)圖4所示的車站信號(hào)平面布置圖進(jìn)行進(jìn)路搜索所得的2條進(jìn)路。圖8中a)表示關(guān)鍵點(diǎn)S到關(guān)鍵點(diǎn)R的路徑,S-H-G-E-I-O-P-R表示東郊方面至4股道的接車進(jìn)路。結(jié)合圖4可以得到進(jìn)路股道區(qū)段為:7DG、11-13DG、9-15DG、17-23DG、19-27DG、4G。圖8b)表示關(guān)鍵點(diǎn)S到關(guān)鍵點(diǎn)Q的路徑,即S-H-G-E-I-O-P-Q,其表示東郊方面至Ⅱ股道的接車進(jìn)路。結(jié)合圖4可以得到進(jìn)路股道區(qū)段為:7DG、11-13DG、9-15DG、17-23DG、19-27DG、ⅡG。其他進(jìn)路以此類推,可以得到整個(gè)車站進(jìn)路信息。4適應(yīng)性和時(shí)間復(fù)雜度該進(jìn)路搜索算法具有以下優(yōu)點(diǎn):1.適用性強(qiáng)。由于車站結(jié)構(gòu)復(fù)雜,如果直接使用二叉樹進(jìn)行對(duì)車站描述無法滿足要求,而使用有向無環(huán)圖對(duì)車站拓?fù)浣Y(jié)構(gòu)進(jìn)行描述,可以較好地滿足要求,使得算法具有較強(qiáng)的適應(yīng)性。2.時(shí)間復(fù)雜度低。由于二叉樹搜索算法本身具有相對(duì)于圖搜索算法較低的時(shí)間復(fù)雜度,使得本文提出的進(jìn)路搜索算法具有較低的時(shí)間復(fù)雜度。這種算法在基于M