计算机联锁进路搜索算法的分析与研究

1、3兰州交通大学自动化与电气工程学院硕士研究生, 730070兰州33兰州交通大学自动化与电气工程学院教授, 730070兰州333铁道科学研究院通信信号研究所研究实习员, 100081北京收稿日期:2007201209计算机联锁进路搜索算法的分析与研究陈志颖3董昱33杨柳3李亮333摘要:简述了计算机联锁系统中站场型数据结构的建立方法, 通过深入研究站场型数据结构形状与二叉树的相似性, 结合在实际搜索进路过程中总结的经验, 提出了一种基于站场型数据结构的新的进路搜索算法。该算法是结合了二叉树、四叉链表和高度原则的新的进路搜索算法。详细论述了这种算法, 并给出了完整的描述。关键词:计算机联锁,

2、数据结构, 二叉树, 进路搜索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 计算机联锁系统是铁路及城市轨道交通信号系统中一个重要的子系统, 通进路内的道岔、信号机、锁关系, 存利用问题, 树、四叉链表和高度原则的新进路搜索算法。1 站场型数据结构图1举例信号平面布置图如果把信号平面图中的信号设备作为信号点图中的点, 则信号点图由边集合和点集合组成, 将这些设备在信号平面布置图中的位置进行连接, 就可以得到与信号平面布置图相对应的信号点图。其中, 每个节点由2部分组成:表示本节点特性的数据域df 和表示相邻节点关系的指针域pf , 即站场。图2所示 。图2站场型数据结构2搜索算法进路就是由若干个信号机、道岔及道岔位置、轨道区段组成的车列在车站内运行时所经过的通路

5、。由始端按钮和终端按钮决定的进路所有有关的信息, 包括进路类型、进路方向、进路按钮、道岔、轨道区段、敌对信号机、防护信号机等, 建立算法前要对这些信息进行搜索。在建立始终端按钮对集合后, 依次取出每个按钮对进行进路搜索。在进路搜索过程中可能存在回路, 所以在访问完某个节点之后可能会沿着某些边又回到了曾经访问过的节点。为了避免重复访问, 必须选择良好的进路搜索算法, 下面的进路搜索算法结合了二叉树、四叉链表和高度3项原则。211二叉树数据结构二叉树是树的一种, 是非线性数据结构。图3给出了二叉树的图形表示及其存储结构。其中A42007年4月铁道通信信号April 12007第43卷第4期RA I

6、L WA Y SIGNALL IN G &COMMUNICA TION Vol 143No 14为根节点, D , F , G 为叶子节点。二叉树的每个节点至多有2棵子树, 并且, 二叉树的子树有左右之分, 次序不可以颠倒 。图3二叉树举例及其存储结构图4二叉树建模图二叉树在存储过程中采用链式存储结构, 其节点由1个数据元素和分别指向其左、右子树的2个分支构成, 表示二叉树链表至少有3个域:数据域和左、右指针域。二叉树的搜索可以采用图的搜索算法, 例如:深度优先搜索, 广度优先搜索。由于站场形状和二叉树形状的相似性, 因此可以先把站场型数据结构以二叉树形式进行建立模型, 然后通过图的搜

7、索方法进行搜索。对图1的二叉树模型如图4所示。212四叉链表2个部分;指针场用于存放其邻节点地址。因此, 通过节点的指针场可以实现双向搜索。采用站场型数据结构可以大大节省存储空间且不必实现编制总进路表, 从而减少设计工作量和避免设计错误, 可以使联锁软件标准化和定型化。因此, 在计算机联锁软件中, 为了便于按进路方向搜索, 可以采用一种四叉双向链表结构来描述站场信号平面布置图。其中每个节点数据域存储站场信号平面图中相应位置的基本图形及全部信息。为了描述交分道岔节点的拓扑信息, 用4个指针域p 1、p 2、p 3、p 4分别描述节点间的邻接关系(拓扑关系信息 , 如图5所示 。图5节点结构在四叉

8、双向图形数据结构中:对应每1个股道, 设有1个头节点h i 和1组信息节点; h i和该股道上第1个信息节点指针互指, 在C T 域存有该股道的信息节点个数; 4个指针域中, p 1表示本节点与同一股道结点的左邻关系, p 2表示与同一股道节点的右邻关系, p 3表示与不同股道节点的道岔向上邻接关系, p 4表示与不同股道节点的向下邻接关系。通过四叉链表, 可以在进路搜索过程中提高效率。例如:因在自动搜索进路过程中遵循直股优先和同类渡线优先的原则, 在搜索过程中都需要对每一条进路进行完全搜索, 但是有了四叉链表可以减少无谓的空间和时间的浪费, 这在后面的进路流程图中可以看出。213高度原则按钮

9、的节点在站场图中有的在同一个坐标线上(纵坐标相同 , 有的不在同一纵坐标上, 根据办理进路时按钮的高度不同建立节点高度数据库, 把相应的节点纵坐标存储起来, 这样在办理进路时, 可, 满足后辈节点低1始端节点低于目标节点, 满足后辈节点高于始端节点进行搜索。31始端节点等于目标节点, 满足后辈节点等于始端节点进行搜索。例如:图1中假设办理D 7至S 3的调车进路, 首先看目标节点与始端节点的纵坐标位置, 应为S 3的纵坐标大于D 7的纵坐标, 所以在搜索中不断比较后辈节点与始端节点的高度差, 为正值时(向上搜索 继续, 否则返回。3算法建立311术语与符号的定义11对向道岔:沿搜索方向使1个轨

10、道分为2个轨道的道岔。21渡线:指连接2个平行轨道之间的轨道。31起始节点K 0:按发车方向进行搜索的指定起始节点。41中间节点K i :与变更按钮相对应的指定节点。51目标节点K g :按发车方向进行搜索时所要找到的最终指定节点。G 用于存放目标节点。61后继节点K c :在站场图的数据结构中, 有方向的直线箭头所指的节点。71后继直节点K z :在站场图的数据结构中道岔节点直股方向的后继节点。5RA IL WA Y SIGNALL IN G &COMMUN ICA TION Vol 143No 142007 图6进路搜索流程图81后继弯节点K w :在站场图的数据结构中道岔节点弯股

11、方向的后继节点。91死节点K d :在站场图的数据结构中没有后继节点的节点。101渡线类型Cro ssing 2Line :用于存放渡线的类型,其值有撇型“/”和捺型“”。L :存放渡线类型。111弯股优先标志Sid 2ingPriority :在搜索中遇到道岔时是否要沿弯股进行搜索。121堆栈S :用来存放起始、中间、目标节点。131堆栈S1:用来存放搜索过程中需要考察的节点。141堆栈S2:用来存放搜索过程中需要保存的路径上的节点。151P1:程中起始节点, 的节点的纵坐标。161P2:用来存放搜索过程中目标节点的纵坐标。171D :存放节点的比较差值。181堆栈S3:用来存放起始、中间、

12、目标节点的纵坐标。312流程图的建立进路搜索流程图如图6所示。313算法比较与分析该算法是从建立节点序列开始, 流程图中核心的部分是搜索的条件判断, 通过对节点的性质(死节点、对向道岔、征用标志 进行判断, 并且利用二叉树建立节点关系, 通过高度原则进行进路搜索, 从而建立了进路搜索的新方法。举例分析:如图7所示, 搜索D 7至S 3进路, 在旧的算法中多搜索了一步, 即在D 13的进栈和出栈时需占用内存和耗费时间, 箭头方向为搜索的顺序; 新算法对二叉树节点的搜索如图8所示, 它达到了节省空间和时间的效果。当对于比较大的站场来说搜索进路用改进的算法会达到更好的效果 。图7进路搜索图(旧算法 图8节点搜索图(新算法4结论在工程实践中, 条件往往不完全符合理想状态。因此, 根据实际状况所设计的算法和原有的模型进行结合可以产生新的算法, 达到事半功倍的效果。