基于二叉树的站场信号平面进路搜索

基于二叉树的站场信号平面进路搜索

在计算机锁闭系统和分散自律组织的集中系统中，必须根据现场的信号方案来确定车站的进入清单。进路搜索是这些系统的核心部分之一。如何高效、方便、准确地进行进路搜索是一个关键的问题。从前曾提出的基于二叉树的进路搜索方法和基于图的进路搜索方法,均存在一定的不足,前者由于站场数据模块不完全具有二叉树的特点,存在适应性方面的不足;后者具有较高的复杂性。因此,在分析站场信号平面图的基础上,提出对站场信号平面图建立有向无环图模型,并且在有向无环图中动态生成二叉树,进而遍历二叉树,最终求得进路的方法。1数据结构1.1叉树的结构二叉树(binarytree)t是有限个元素的集合(可以为空)。当二叉树非空时,其中有一个称为根的元素,余下的元素(如果有的话)被组成2个二叉树,分别称为t的左子树和右子树,结构图如图1所示。二叉树最常用的描述方法是链式存储结构,它是指用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。链表中每个结点由3个域组成,除了数据域外,还有2个指针域,分别给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储结构如图2所示。其中,data域存放某结点的数据信息,lchild与rchild分别存放指向左孩子和右孩子的指针。当左孩子或右孩子不存在时,相应指针域值为空(用符号∧或Null表示)。1.2树内种dag一个无环的有向图称作有向无环图(directedacyclinegraph),简称为DAG图,它是一类比树更一般的特殊有向图,如图3所示。DAG图有2个主要特点:①图中的结点可以通过有向边连接;②如果存在一个有向路径从结点a连接到结点b,那么,必然不存在一个可以从结点b连接到结点a的有向路径。2网络结构分析与建模2.1信号设备的设置图4所示为一个典型的车站信号平面布置图的一部分。站场股道的中垂线把站场分成左、右2个咽喉。在2个咽喉区内建模的方法是相同的。下面只对1个咽喉区进行讨论。一个铁路站场中需要控制的信号设备主要有信号机、与道岔相关联的转辙机和轨道电路。车站信号平面中有3种设备类型:信号机、道岔和区段。进路主要的组成设备也是这3种。2.2有向无环图求解在站场信号平面布置图中的信号机、道岔端点、区段端点中提取关键结点,可以将信号平面布置图简化为如图5所示的站场示意图。以图5为例,在左咽喉区进行接车作业时,以图中关键结点为顶头,以连接关键结点的设备(道岔或区段)为弧、以下行方向作为有向无环图弧的方向,建立站场的有向无环图模型(图6)。这样将进路搜索问题等价于在一个有向无环图中,可搜索一个源点到汇点之间的所有路径。例如东郊方面到5股道的接车进路,就等价于从顶点S到M的路径(图6存在S-H-G-F-L-M的路径)。直接求解有向无环图两点之间所有路径较为复杂,而且通过观察发现,在站场基础上建立的有向无环图有其特殊性。在不存在三开道岔或更为复杂的交叉设备的情况下,有向无环图中顶点的出度数小于等于2。这样的有向无环图与二叉树存在相似性和关联性。因此,现提出一种在有向无环图中动态建立二叉树,再对二叉树进行遍历,从而求出顶点之间的所有路径,也就是进路的方法。3基于根控制进路的搜索下面以东郊方面向各股道接车进路为例说明进路搜索算法。选择进路的起点S,作为二叉树的根,并作为当前结点,若当前结点的出度数为2,则第1条弧所指向的顶点为其左孩子,第2条弧所指向的顶点为其右孩子,若当前结点的出度数为1,则弧所指向的顶点为其左孩子,若当前结点的出度数为0,则其为叶子结点,再选择子结点为当前结点,以此类推,建立以S为根的二叉树(图6)。遍历以S为根的二叉树,从根结点到叶子结点的路径,就是东郊方面到各股道的进路。二叉树遍历的访问顺序有3种:先序遍历、中序遍历和后序遍历。本系统采用先序遍历,它的递归过程为:若二叉树为空,遍历结束;否则,首先访问根结点,再遍历根结点的左子树,最后遍历根结点的右子树。进路自动生成搜索算法如下。1.建立1个空栈stack1用于保存搜索路径,设置根结点为当前结点。2.判断二叉树BiTree是否为空,如果为空,则遍历结束。3.将当前结点的数据域压入栈stack1的栈顶。4.判断当前结点是否是叶子结点,如果是叶子结点,保存栈stack1的内容(当前栈stack1的内容为一条进路)。5.访问结点的左子树。6.访问结点的右子树。7.栈stack1的栈顶元素出栈。图8是对图4所示的车站信号平面布置图进行进路搜索所得的2条进路。图8中a)表示关键点S到关键点R的路径,S-H-G-E-I-O-P-R表示东郊方面至4股道的接车进路。结合图4可以得到进路股道区段为:7DG、11-13DG、9-15DG、17-23DG、19-27DG、4G。图8b)表示关键点S到关键点Q的路径,即S-H-G-E-I-O-P-Q,其表示东郊方面至Ⅱ股道的接车进路。结合图4可以得到进路股道区段为:7DG、11-13DG、9-15DG、17-23DG、19-27DG、ⅡG。其他进路以此类推,可以得到整个车站进路信息。4适应性和时间复杂度该进路搜索算法具有以下优点:1.适用性强。由于车站结构复杂,如果直接使用二叉树进行对车站描述无法满足要求,而使用有向无环图对车站拓扑结构进行描述,可以较好地满足要求,使得算法具有较强的适应性。2.时间复杂度低。由于二叉树搜索算法本身具有相对于图搜索算法较低的时间复杂度,使得本文提出的进路搜索算法具有较低的时间复杂度。这种算法在基于M