基于有向图的进路搜索算法研究与设计

本文在分析铁路车站信号设备分布特性的基础上，以有向 图形式对站场网络拓扑结构进行描述，建立了进路搜索拓扑结 构，并以铁路车站进路操作要求为约束条件，对深度优先搜索 DFS算法加以改进，提出了一种适用于铁路车站实际情况进路 搜索算法。
为某铁路车站的局部信号平面布置图。由图1可见，铁路车站 站场是由各个信号设备按照一定的连接方式组成的设备网络。 若将各信号设备抽象为设备节点集合N={n1,n2,n3,...,ni}， 各信号设备之间的连接关系抽象为对应的逻辑边集合E ={e1,e2,e3,... ,ei}，则可将铁路车站信号设备网络整体抽象 为无向图G=(N,E)。
图1 某铁路车站的局部信号平面布置图
·69·
基于有向图的进路搜索算法研究与设计 肖 蒙，等
图2 局部站场的拓扑结构图 1.2 信号设备节点的数据结构
由图2可见，沿节点间指向，对向道岔的后续设备节点数 为2个，其他信号设备节点的后续设备节点数均为1个，即图中 节点最多有2个后续节点。若将节点后续指向边与节点属性一 并建立数据结构，则信号设备节点ni的数据结构可包括1个数 据域Data和2个指针域pfz、pfw。其中，数据域Data用于保存 表述该信号设备属性的数据及进路搜索程序所需的一些标志， 指针域pfz、pfw用于保存后续设备节点的指针。当后续设备不 存在时，对应指针域值为空。
efficiency and the security of objectives route ensure the traffic safety significantly. In this paper, the network topology and
node model of the railway station yard are established，based on the similarity between station yard and direct graph. Then，
免出现迂回进路，本文采用深度优先搜索策略。即在进路搜索 中遇到对向道岔(分叉)时，约定优先搜索道岔后的直股分支。 2.3 搜索约束条件
在铁路车站的进路办理中，当只指定起始与终止信号设备 节点时，不能出现平行进路和迂回进路[1]。因此进路搜索策略 并不能直接使用一般的深度优先搜索算法，必须对深度优先搜 索算法进行修改，加入一些约束条件后使得其适用于铁路站场 进路搜索的实际情况。
2 进路搜索算法的设计 2.1 搜索拓扑结构的建立
对有向图G`，当从指定起始信号设备节点ns出发搜索目标 路径时，可视为对以ns为顶点的一个有向无环子图G`*进行遍 历操作。G’*可描述为G`*=( N*,E` *)∈G`。
以图2为例，当选定D15节点为起始信号设备节点时，可到 一个有向无环子图G`*如图3所示。
《自动化与仪器仪表》2012年第6期(总第164期)
基于有向图的进路搜索算法研究与设计*
肖 蒙1，宁海安2，赵志荣3 (1.兰州交通大学自动化与电气工程学院 兰州，730070)
(2.北京国交信通科技发展公司 北京，100011) (3.兰州铁路局银川电务段 银川，750011)
摘 要:进路搜索是铁路车站计算机联锁系统的基本功能，其运行效率及所得目标进路的安全性对于保证行车安全意
为了避免在对向道岔设置有导向标志时仍会出现迂回进路 的情况，可再设置按同类渡线搜索的约束条件[5]。渡线是指连 接两个平行股道之间的斜形轨道。这里将股道间渡线按其铺设 方式分为撇形渡线和捺形渡线。在搜索过程中，若只经由同类 的渡线搜索，就不致搜出绕弯的迂回进路。 2.4 进路搜索算法
在对有向无环图G`*采用深度优先搜索策略的基础上，将 上述搜索约束条件加入后，就可以得到进路搜索算法。 2.4.1术语及符号定义
对有向无环子图G`*的遍历一般有两种方式，即深度优先 搜索DFS(Depth First Search)和广度优先搜索BFS(Breadth First Search)遍历。DFS遍历类似于树的先根遍历，是树的先 根遍历的推广。BFS遍历类似于树的按层次遍历的过程。两种 遍历方式的搜索效率与所采用的存储结构直接相关，且时间复 杂度相当，区别仅在于对节点的访问顺序不同[4]。
区域报警控制器使用803l型单片机来实现其控制功能，各 个单片机的串行性接口经过RS-485数据总线，接至监控主机上 面的串行性接口，经过串行通讯来跟监控主机进行联系，并将 控制器传输过来的信息数据进行处理和显示。
区域报警控制器跟现场模块和探测器之间，要经过现场那 些信号二总线来进行连接。要依照保护性探测区域所有的现场 设备，来选取区域报警控制器应有的探测总容量，现场设备有 如下部分:编码型的消火栓按键、手动型报警按键、输入／输 出的模块、智能型感烟、感温探测器的输入模块等。
义重大。本文通过对铁路车站站场图与有向图的相似性进行研究，建立其网络拓扑结构与节点模型，结合深度优先遍历
来自百度文库
算法和搜索约束条件，提出一种适用于铁路车站实际情况的进路搜索算法，并给出了完整的描述。
关键词:进路搜索;有向图;深度优先遍历;搜索约束条件
Abstract:Route searching is the basic functions of computer interlocking system of railway stations，and its operating
业和站内调车作业。为防止列车冲突，保证行车安全，需要为 作业中的列车建立具有防护性的封闭空间，并与其他作业保持 安全间隔。该封闭空间即为进路。
随着铁路运输的信息化、智能化，计算机联锁技术已广泛 在铁路车站信号控制领域使用。进路的处理是铁路车站计算机 联锁系统的主要功能。进路处理功能实质是通过对信号机、道 岔、轨道区段等信号设备的联锁监控得以实现的[1]。进路的建 立需要根据操作命令，得到相应路径，并检查该路径所涉及的 轨道区段是否空闲、道岔位置是否正确以及是否与其他进路冲 突等联锁条件。
进路搜索操作是从给定的起始信号设备出发，搜索出到达 给定的终止信号设备之间的路径，并将该路径所包括的各信号 设备及各信号设备之间的前后关系作为进路表保存，供后续进 路处理功能使用。可见，进路搜索存在方向性[2]。根据铁路车 站信号设备编码原则，若将信号设备间的连接关系统一设为上 行指向(左指向)或下行指向(右指向)，则逻辑边E、无向图G可 演变为有向边E`={e`1,e`2,e`3,..., e`i}和有向图G`=(N,E`)。
本文探究的建筑物是一栋16层的办公楼，高达56米，建筑 面积达25000m2，其地下车库面积为3000m2，地上所有楼层都是 工作间。配电室内设有气体性的灭火系统，次建筑属于一类的 高层建筑，也就是一级火灾的报警重点保护对象。
《自动化与仪器仪表》2012年第6期(总第164期)
针对建筑特点，并根据国家相关规定，现场设备需要进 行下列设置:地上楼层是工作间，应设置好感烟型探测器。地 下车库应该按照火灾特点，选取感温型探测器;在每一楼层的 疏散出口，按照规定，设置一定数量的手动型火灾报警摁钮， 用以进行人工报警[3]。在每一个消火栓的位置，设置好手动编 码型的消火栓摁钮，有三个作用:对于手动编码型消火栓摁钮 上的启泵信号，使用信号灯来显示;经过信号二总线把火警信 号传递到区域机，于区域机上显示出消火栓位置;经过接连至 手动编码型消火栓摁钮的启泵直接线路，用摁钮直接进行消火 栓泵的启动。在配电室内安装气体型的灭火系统，并设置好声 光指示和对应按钮，使得气体喷洒的设备可以自动进行联动运 行。在排烟、防烟风机和消防水泵的控制设备普遍安排总线编 码型的控制模块，还需将一个手动直接控制型的装置设置于消 防中心内，并显示出联动控制设备所有的动作情况信号。设置 在现场的监视模块可以显示出安全信号阀、报警阀和水流指示 器的工作状态。现场设置的总线编码，作用是控制通风系统及 时停止，并将有关位置的防火阀及时关闭;设置声光警报器， 提醒楼内人员及时疏散和灭火．
参考文献 [1] DIN VDE 0833-3-2009.火灾,入侵和拦劫报警系统.第3部分:入侵
和拦截报警系统的要求[S]. [2] ISO 7240-7-2011.火灾探测和报警系统.第7部分:使用散射光,透
射光或电离作用的尖形烟雾探测器[S]. [3] DIN VDE 0833-2-2009.火灾,侵入和拦截报警系统.第2部分:火警
considering the Depth First Search Algorithm and the searching constraints，a algorithm of route searching was proposed and also
actual suitable for the railway station，with complete description.
Key words:route searching;direct graph;depth first search;searching constraints
中图法分类号:TP311
文献标志码:A
文章编号:1001-9227(2012)-06-0069-03
0 引言 铁路车站的基本作业包括与区间之间的列车接发、通过作
区域报警控制器的作用是:显示出火警探测器的部位编 号，并在同一时间发送声光性的报警信号。显示的内容非常直 观清晰，工作人员确认比较方便。
对于某些意义比较特殊而重要的气体性喷洒设备，区域报 警控制器会提供独立的联动性编程空阀和控制密码，并给予对 应的声光来指示，使气体性喷洒设备得到更为严密的监控． 3.3 现场设备的设计及选型
当起始与终止信号设备节点间存在平行的路径时，需事先 根据车站作业情况确定其中一条是基本路径。若基本路径经由 对向道岔的岔后弯股分支，则需在该道岔节点数据域中设置导 向标志。在进路搜索过程中每遇到对向道岔节点，首先检查该 节点是否有导向标志，若没有，则按岔后直股优先搜索的策略 搜索;若有，则按岔后弯股优先搜索的策略搜索。
图3 以D15节点为起始节点的有向无环子图
2.2 搜索策略分析 当对G’*进行遍历操作中，若遍历到的当前节点即为终止
信号设备节点Nz时，则当前路径即为目标进路R。目标进路应 包括相关信号设备节点及各信号设备节点之间的前后关系[3]。 目标进路R可描述为R={ns(es`),...,ni(ei`),...,nz(ez`)}∈ G`*，其中ns，es`分别为目标进路中间的相关信号设备节点及 其后续指向边。
考虑到铁路站场有向图拓扑结构及车站进路特点，并为避
·70·
图4 进路搜索算法流程图 （下转第73页）
主程序又包括初始化、数据的收集、转换和巡检等几个部分。 子主程序包括:延时程序、显示程序、故障处理程序、异常报 警程序、消防报警程序、数据分析程序、据测器的编码读取程 序等各种子程序。中断服务这种子程序为:8031定时器会定两 秒的中断时间，执行键盘对程序进行扫描。此程序可以检查出 内部故障。值班工作人员可以作模拟性操作，能有效防止故障 的产生。
现设定信号设备间的连接关系为下行指向，可建立图2所 示局部站场的拓扑结构图。
1 铁路车站站场分析及建模 1.1 站场信号设备的网络拓扑结构
铁路车站信号设备主要包括信号机、道岔、轨道区段、侵 限绝缘等，且各信号设备之间存在前后的物理连接关系。图1
收稿日期:2012作者简介:肖蒙(1974-)，男，湖北孝感人，副教授，博 士研究生，研究方向为交通信息工程及控制。 *基金项目:铁道部科技研究开发计划重点课题 (2012X003-B)、甘肃省自然科学基金资助项目(1112RJZA040)。
(1)对向道岔:沿节点连接指向使股道一分为二的道岔; (2)搜索指针pC:在搜索过程中用于指向当前节点的指针; (3)节点指针域pfz:指向岔后直股(非道岔节点)连接的后 续节点; (4)节点指针域pfw:指向岔后弯股连接的后续节点(非道岔 节点的此指针域值为空); (5)堆栈Sn:用于存放当前搜索过程中所经由的节点; (6)堆栈Sd:用于存放当前搜索过程中所经由的还未遍历其 另一分支的对向道岔节点。 2.4.2算法流程图与文字描述