基于邻接表结构的进路搜索算法研究

1、-3400-0引言计算机联锁系统(computer based interlocking ,CBI 是铁路及城市轨道交通信号系统中一个重要的子系统。其主要功能是处理轨道交通进路内的道岔、信号机、轨道电路之间的安全联锁关系,从而提高运输效率、保障行车安全。另外,CBI 系统还接收上层监控系统的控制指令,进行信号设备控制,并向监控系统及其它系统发送有关信号设备的状态信息。计算机联锁系统自动测试软件所需的基础设备数据及联锁表,取决于车站信号平面布置图,即一旦站场设计确定后,对应于车站信号平面布置图的所有测试用基础数据就惟一地确定下来。因此在对计算机联锁系统进行自动测试时,如何准确无误地根据车站信号平

2、面布置图构造出对应的站场静态数据是对联锁系统进行自动测试的关键。计算机联锁系统自动测试软件CAD 子系统体现了计算机辅助设计的思想,为测试用户提供了站场图形的CAD 输入方式,用户可以方便、灵活地录入工程部门提供的铁路信号车站平面布置图中的基本图形单元,快捷地完成站场图的拼贴工作。然后CAD 子系统依据计算机联锁技术条件(铁道部标准,对基于邻接表的车站信号平面布置图的拓扑数据结构进行搜索,生成全部自动测试所需要的站场设备表(例如道岔、区段、信号机、按钮等、计算机联锁表(进路表,并储存于数据库之中。1车站平面布置图的录入与存储CAD 子系统将车站信号平面布置图分解成若干个基本图形单元,并将平面布

3、置图看作是由这些图形单元拼贴而成。这些图形单元可以细分为信号机、道岔、轨道区段、变通及终端按钮、超限绝缘等信号设备对象。然而考虑到超限绝缘与信号机、轨道区段有密切的联系,CAD 子系统最终把这些图形单元划分为信号机、道岔、轨道区段、变更及终端按钮4类。每个类别下面都有各式各样的图形单元,如图1所示。在CAD 子系统中,信号机、道岔、轨道区段、变更及终端按钮都是MFC 的一个类,图1所示的信号机类别下的每个图形单元都是这个信号机类的一个对象实例,他们使用信号机类的画图方法通过属性来决定如何在MFC 的视图中勾画自己,展现自己的具体样式,这充分体现了CAD 子系统中时刻贯穿面向对象的程序设计思想。

4、CAD 子系统的绘图区域即视图被划分成可以根据站场大小进行调节的m ×n 个网格区域,用一个m ×n 的图形矩阵来表收稿日期:2005-07-27。作者简介:彭建伟(1978-,男,北京人,硕士,研究方向为软件工程;殷人昆(1945-,男,北京人,教授,研究方向为数据结构、软件工程。基于邻接表结构的进路搜索算法研究彭建伟,殷人昆(清华大学计算机科学与技术系,北京100084摘要:介绍了计算机辅助设计(CAD 思想在计算机联锁系统自动测试软件中的应用,提供了一种对铁路车站信号平面布置图进行有效分解、图形单元对象快捷录入,用面向对象的方法构造车站拓扑数据的方案。详细地论述了基于

5、邻接表图形数据结构的进路搜索算法,并给出了完整的描述。关键词:计算机辅助设计;信号平面布置图;面向对象;邻接表;进路搜索算法中图法分类号:TP311文献标识码:A文章编号:1000-7024(200618-3400-03Algorithm of route searching based on adjacency listPENG Jian-wei,YIN Ren-kun(Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China Abstract :A CAD applicati

6、on in an automatic test software of a computer is introduced based on interlocking.It also lays out a practical scheme that the test users can divide the signal graph of a railway station into diverse graph units efficiently,inputs the units conveniently and construct topologic data of a station gra

7、ph based on an object oriented method.Finally,a particular description of a route searching algorithm is given based on graph data structure of an adjacency list.Key words :CAD;signal graph;object oriented;adjacency list;route-searching algorithm2006年9月计算机工程与设计Sept.2006第27卷第18期Vol.27No.18Computer En

8、gineering and Design图1 信号机类别下的全部图形单元样式示。如果将工具栏上的一个图形单元选中放到任一网格中,那么系统将生成这个图形单元对象,然后由对象在网格中绘制自己,保存网格的中心坐标到自己的属性中,同时图形矩阵的相应位置被设置为占用状态,只有当图形单元被移动或删除时才被设置为空闲状态。由于图形矩阵的零元素很多,故可采用稀疏矩阵的存储方法。使用CAD子系统拼贴的部分站场图如图2所示。每当用户在视图中添加一个图形单元,系统都将生成一个图形单元对象并将其插入到图形单元节点的单链表中。整个站场图中的所有图形单元对象及其它们之间的关系可以随时被串行化到一个二进制文件中,使用户可以

9、在以后继续拼贴。2基于邻接表数据结构的车站平面布置图进路搜索算法2.1基于邻接表数据结构的平面布置图在用户完成站场图拼贴,选择CAD子系统提供的图数据结构生成的功能时,系统将站场图中所有的图形单元进行链接,为用户生成基于邻接表的图的数据结构。该图的数据结构将用于进路的搜索使用。基于邻接表数据结构的平面布置图由站场图类(CSta-tionDiagram、节点类(CNode和边类(CEdge组成。在站场图的邻接表数据结构中有一个节点类对象的主链表,用于保存图中所有的节点对象,在节点对象中存在一个指向它边链表的头指针。在站场图中,每个图形单元都是一个节点对象,每个节点对象内都有一个指向信号设备类对象

10、的指针。当节点对象对应的图形单元为并置信号机时,节点对象中还有一个指向上行方向信号机对象的指针。边类对象记录了两个节点之间的关系。对于任意一个节点对象,根据它所包含信号设备的具体样式,在进行图形单元链接时,系统会自动判断紧邻它的节点是否为它的合理邻节点。如果是它的合理邻节点,则生成一个边类对象,把这个邻节点的编号及其地址保存到边对象中,并把边对象插入到该节点对象的边链表头指针所指向的单链表中。例如,如图2所示的出站信号机SII,在进行图形单元链接时,系统会把它正左方、正右方的两个轨道区段加到信号机节点对象的边链表中。2.2进路搜索算法研究在进行进路搜索之前,我们首先要建立车站信号平面布置图中的

11、始终端、变更按钮序列的集合,集合中的任一有效始终端、变更按钮序列都将作为进路搜索算法的输入数据。始终端、变更按钮序列集合的建立要通过站场图的遍历完成。由于图中可能存在回路,所以在访问完某个节点之后可能会沿着某些边又回到了曾经访问过的节点。因此为了避免重复访问,可在节点类中设置一个访问过与否的标志,防止某个节点对象被多次访问。在搜索出站场图中信号设备包含的全部按钮后,根据信号设备类型把这些按钮匹配成进路的始终端、变更按钮序列。进路就是由若干个信号机、道岔及道岔位置、轨道区段组成的车列在车站内运行时所经过的通路。由始端按钮和终端按钮决定的进路,必须搜索出进路上所有有关的信息,包括进路类型、进路方向

12、、进路按钮、道岔、轨道区段、敌对信号机、防护信号机等。在建立始终端按钮对集合后,依次取出每个按钮对进行进路搜索。(1搜索策略选择根据数据结构中图论的内容,图的搜索一般有两种方式,即深度优先搜索(depth first search,DFS和广度优先搜索(brea-dth first search,BFS。深度优先搜索(DFS在访问图中某个起始节点v后,由v出发访问它任一邻接节点w1,再从w1出发访问与w1邻接但还没有访问过的节点w2,然后再从w2出发重复进行上面的类似访问,直到找到目标节点为止。广度优先搜索(BFS在访问图中某个起始节点v后,由v出发依次访问v的所有未曾访问过的邻接节点w1,w

13、2,然后在顺序访问w1,w2,的所有未曾访问过的邻接节点,再从这些访问过的节点出发,再访问它们所有还未曾访问过的邻接节点,直到找到目标节点为止。在本文所描述的进路搜索算法中,采用的是深度优先搜索策略。如果采用广度优先搜索,由于在每个节点扩展时,并不知道该扩展方向是否为目标节点的方向,造成扩展的分支较多,存储量很大。但深度优先搜索可以避免这样的问题,它会沿着单一的路径搜索,直到在这一路径上无法找到目标节点时才会选择另一路径搜索,而且对已经搜索过的不能找到目标节点的路径不必保存,这样可以节省存储空间。(2术语及符号定义1对向道岔:沿搜索方向使一个轨道分为两个轨道的道岔。2渡线:指连接两个平行轨道之

14、间的轨道。3起始节点N0:按发车方向进行搜索的指定起始节点。4中间节点N i:与变更按钮相对应的指定节点。5目标节点N g:按发车方向进行搜索时所要找到的最终指定节点。6后继节点Ns:在站场图的数据结构中非道岔节点的后继节点。7后继直节点N z:在站场图的数据结构中道岔节点直股方向的后继节点。8后继弯节点N w:在站场图的数据结构中道岔节点弯股方向的后继节点。9死节点N d:在站场图的数据结构中没有后继节点的节点。10渡线类型CrossingLine:用于存放渡线的类型,其值有撇型“/”和捺型“”。11弯股优先标志SidingPriority: 在搜索中遇到道岔时是图2利用图形单元拼贴的部分站

15、场-3401-3402-否需要沿道岔弯股优先搜索。12堆栈S i :用来存放起始、中间、目标节点。13堆栈S c :用来存放搜索过程中需要考察的节点。14堆栈S r :用来存放搜索过程中需要保存的路径上的节点。(3算法流程图与文字描述进路搜索算法文字描述如下:1从始终端、变更按钮(如果存在序列集合中取出第一个按钮序列,查找序列中与各个按钮对应的信号设备节点,并将这些信号设备节点逆序压入堆栈S i 中;2判断S i 中的节点数是否大于1,如果不大于1,完成搜索,从S r 中的所有节点提取进路需要的信息构成进路并填入进路表;3获取S i 栈顶元素S i (0并将其存入S c 中,S i 退栈;4判

16、断S c 空否,如果为空,退出搜索;5获取S c 栈顶元素S c (0并存入S r 中,S c 退栈;6判断S r (0是否等于S i (0,如果相等转2;7判断S r (0是否为死节点,如果是死节点转17;8判断S r (0是否为对向道岔,如果不是对向道岔转16;9判断S r (0的SidingPriority 是否为弯股优先搜索,如果不是转13;10判断全局变量CrossingLine 是否为空,如果不空转11;11将S r (0的CrossingLine 赋给全局变量CrossingLine ;12将指针pFstSPNode 指向S r (0;13将S r (0的后继直节点N z 、弯节

17、点N w顺序压入堆栈S c 中,转3;14将S r (0的CrossingLine 与全局变量CrossingLine 比较,如果是同类转10;15将S r (0的后继直节点N z 压入堆栈S c 中,转3;16判断全局变量CrossingLine 是否为空,如果不空转15;17将S r (0的后继弯节点N w 、直节点N z 顺序压入堆栈S c 中,转3;18将S r (0的CrossingLine 与全局变量CrossingLine 比较,同类转14,否则转12;19将S r (0的后继节点Ns 压入堆栈S c中,转3;20对S r 执行退栈操作,即删除S r (0节点;21判断S r 是

18、否为空,如果为空,退出搜索;22判断S r (0是否为对向道岔,如果不是对向道岔转17;23判断S r (0是否为指针pFstSPNode 所指向的节点,如果不是转23;24将全局渡线类型变量CrossingLine 置空;25判断S c (0是否为S r (0的N z 或N w ,如果是转3,否则转17;图3详细描述了基于邻接表数据结构的站场图进行进路的流程图。3结束语本文描述的进路搜索算法已经在计算机联锁系统自动测试软件中实现。通过CAD 子系统,测试人员可以方便地进行站场图拼贴,自动生成测试软件需要的所有测试用基础数据,如各种设备数据、联锁表数据等。计算机联锁系统自动测试软件的开发显著地减少了由测试人员手工录入联锁表的工作量和人为错误,由全自动测试取代了联锁系统出厂前的手工测试过程,从而降低了联锁系统的开发成本,缩短了项目的周期,取得了可观的经济