A*进路搜索算法的研究与实现

梁艺凡，谭丽，冯挺

(1.兰州交通大学自动化与电气工程学院， 兰州 730070；2.广州铁路(集团)公司，广东深圳 518000)

1 概述

计算机联锁系统是铁路行车指挥的关键系统之一，有着保证行车安全和提高行车效率的重要作用，其主要功能是接受调度计划进行进路控制，完成作业办理。进路搜索作为计算机联锁系统的核心模块，直接影响了进路控制的正确、安全、高效性。目前应用于铁路现场的计算机联锁系统有DS6-K5B、EI32-JD、HJ04A等，其进路搜索方法主要采用带导向标志和优先策略的传统搜路法，改进的深度优先、广度优先搜索和Dijkstra算法，以及相关理论研究采用二叉树遍历进行搜索等[1]。经现场应用发现，上述方法均搜索效率低、占用资源大。为了提高进路办理效率，本文研究采用A*算法搜索进路。

2 A*算法

A*算法是用于求解静态路网中最短路的智能算法，使用启发函数对待扩展节点进行最优选择，使得所扩展的节点少于其他同类搜索算法，因此更加高效，加之其启发函数设计灵活，易于实现的特点，A*算法在智能交通、机器人路径搜寻等方面有着广泛应用。车站信号平面布置图按照接发车方向可以抽象为有向图，应用A*算法进行路径搜索是可行的。

A*算法在搜索时将当前待扩展节点保存在open列表中，对其按照启发函数值进行排序，选择f值最小的节点压入closed列表，并产生此节点的所有后继压入open中，作为下次的扩展对象。在搜索中不断更新open和closed列表，以确保当前保存的是已扩展的起始节点到目标节点的最优路径上的节点[2]。其启发函数为

f′(n)=g′(n)+h′(n)

式中n——搜索中遇到的任意中间节点；

f′(n)——起始节点经由n到目标节点的估计代价；

g′(n)——起始节点到n的最优路径的估计代价；

g(n)——起始节点到n的最优路径的实际代价；

h′(n)——n到目标节点的最优路径的估计代价；

h(n)——n到目标节点的最优路径的实际代价。

当h′(n)≤h(n)时，称h′(n)是可采纳的，此时搜索的点数多、效率低，但能确保得到最优解(若存在最优解)[3]。

3 基于A*算法的进路搜索策略

3.1 启发函数的设计

车站信号平面布置图主要反映了站场线路的布置和接发车方向，以及主要信号设备的名称编号和位置。若将道岔和信号机节点抽象为图的顶点(道岔分岔前、岔后顶点，并置调车信号机用2个顶点表示)，轨道区段则成为连接这些顶点的边。那么对于特定的接发车方向，可以将信号平面布置图看作一个有向图G[4]。G=(V，E)，其中V={v1，v2，…，vn}，为G中顶点的集合；E={e1，e2，…，en}，为G中边的集合。

设vi为搜索中遇到的任意节点，坐标为(xi，yi)；vj为目标节点，坐标为(xj，yj)。为了满足h′(n)≤h(n)，保证算法的完备性和最优性，将h′(n)的值定义为两节点间的欧几里得距离。考虑到列车沿钢轨直线走行的限制，令g′(vi)=4*abs(yi-yj)，增强优先扩展的节点和目标节点在同一股道的可能性。则启发函数为：f′(vi)=g′(vi)+h′(vi)=sqrt((xi-xj)∧2+(yi-yj)∧2)+4*abs(yi-yj)。

根据所设计启发函数的构造特点，设K为G的距离矩阵，用于存储G中所有节点两两间的f′(n)值。K满足kij=d(vi，vj)，其中i≥0，j≤n-1；对于i=j，有kij=0；且满足d(vi，vj)=d(vj，vi)，即kij=kji，K为对称矩阵[5]。对待扩展节点排序时，通过读取K的部分值即可得到待扩展节点的f′(n)值，总体上节省了程序执行时间。

3.2 数据结构的实现

联锁程序需要大量的静态数据为基础，对数据库的构建，一般有进路表型数据结构和站场型数据结构。进路表型数据结构的优点是搜路方便，根据操作命令从总进路表中选取即可；缺点是总进路表编制繁琐、容易出错，占用存储空间大，修改困难[6]。站场型数据结构的优点是动态生成进路表，占用存储空间小，容易修改；缺点是进路办理约束多，程序实现复杂，搜索耗时多。

综合两者的优点，当由于平行渡线而产生多条进路时，将确定的基本进路编制成“基本进路表”，再采用更适合A*算法的改进的站场型数据结构进行其余进路的搜索。在搜索时若判定始终端在基本进路表中，则直接读取进路；否则采用A*搜路算法搜索进路。这样冲淡了上述两种数据结构各自的优缺点，既简化了A*搜路算法程序，保留了站场型数据结构的优点，又仅是对基本进路进行进路表编制，占用存储空间较小。

3.3 A*进路搜索算法的搜索流程

进路搜索程序需要完成的具体任务如下：

(1)按下进路始终端按钮后只能选出一条基本进路，要选择变通进路需人工按压变通按钮[7]；

(2)检查所选出进路的敌对进路是否建立；

(3)若能建立进路，在与该进路有关的所有变量模块中设置占用标志，即锁闭敌对进路；

(4)指明与进路相关道岔的位置；

(5)形成一个进路表供联锁处理程序使用。

设起始节点为S，目标节点为M，X为搜索中遇到的任意节点，搜索范围为：{xM

图1 A*进路搜索算法搜路流程

4 实验及算法性能分析

4.1 实验平台搭建

计算机联锁系统软件用于实现人机界面信息处理、基本联锁控制及执行、自动检测与诊断等功能。为方便实现，在保证核心功能的前提下，用Visual C++6.0进行编程，实现了简化的计算机联锁软件，设备状态通过变量设置虚拟实现。通过此仿真软件办理列、调车进路，验证A*进路搜索算法的可行性；并在同一台PC机上实现两个联锁仿真软件，两者仅在进路搜索程序上有所区别，分别使用A*搜路算法和传统搜路法。编写测试代码分别对两者的进路办理时间进行测试显示，比对算法效率。

对各设备的结构体定义中，除了包括节点ID号、空间坐标、左右节点ID号等体现链接关系的信息外，还要对其各种特性用“0”“1”码分别描述，得出每个节点十六进制的特性编码，用来反映设备的状态及确定所办进路性质、能否建立进路等。

对open列表采用最小二叉堆(class BinaryHeap)来实现，最小二叉堆很容易找到最小元素，并在移除最小元素时仍然保持为一个有效最小二叉堆[8]。将closed列表定义为一个一维变长数组，用vector来实现。对矩阵K采用压缩存储的方法，只将K的下三角中的元素按行优先的顺序存储在一个一维数组double heur[ ]中，让每两个对称的元素共享一个存储空间，节约近一半的存储空间。

实验界面如图2所示，图中白光带表示已选出进路，此时X4信号机开放，亮绿灯。道岔状态如图左上角所示，进路所经过的道岔均已锁闭，为红灯。图3为点击菜单“进路表”后弹出的窗口，记录了所办进路的进路表。实验证明，A*搜路算法能够快速正确的搜出所需基本进路，自动生成进路表。

图2 联锁仿真软件上位机显示

图3 进路表窗口

4.2 算法性能分析

目前常用的几种进路搜索方法中，Dijkstra算法性能较好，传统搜路法应用最为广泛。Dijkstra算法毫无选择地向四周扩展，遍历计算的节点很多，搜索效率较低。若图的节点数为n，边数为m，边的权值为c，搜索效率较高的基于Bucket优先级队列的Dijkstra算法的时间复杂度为O(m+nc)，而A*算法的时间复杂度为O(n′)，n′为A*算法搜索中扩展的节点数，效率明显优于Dijkstra算法，且A*算法遍历保存的节点数量不多，节省存储空间[9]。现将A*搜路算法与传统搜路法从以下几个方面进行比较，详细分析A*搜路算法的性能。

(1)有效性

传统搜路方法经过多年实践验证，其有效性不言而喻。A*搜路算法使用欧几里得距离作为估价值，必然小于或等于实际距离，满足可采纳性，能够得到最优解。且经实验验证，A*搜路算法能够搜出所需的基本进路，证明了其可行与准确，即有效。

(2)高效性

图4 两种算法多次办理同一进路的时间曲线

由于联锁软件的高实时性，使用微秒级精确度的QueryPerformanceCounter函数来测试进路办理时间，为便于记录，将换算结果换算为毫秒输出。实验结果如图4、图5的MATLAB拟合曲线所示。图4为多次办理同一条进路(D4-XⅠ)两者的用时曲线；图5为办理多条不同进路两者的用时曲线。由图4可见，传统搜路法由于扩展节点多，遍历节点的累积时间差较大，相较之下，A*搜路算法的搜索时间更加稳定。由图5

可见，当所办进路经过多个对向道岔时，两者时间相差较大，A*搜路算法效率明显高于传统搜路法；当所办进路经过对向道岔不多时，两者时间相差不大，A*搜路算法效率仍然高于传统搜路法；当所办进路不经过对向道岔时，两者时间相差不大，A*搜路算法效率有时会低于传统搜路法。由此可得，当站场复杂，咽喉区道岔数量多，平行进路多时A*搜路算法的高效性会更加突出；当站场简单时，A*搜路算法较传统搜路法高效性优势体现不大。

图5 两种算法办理多条进路的时间曲线

(3)占用空间

在静态数据的存储上，除了所需的共同基础数据，传统搜路法需要存储道岔类型、渡线类型等数据，A*搜路算法需要存储各节点f′(n)值，两者相差不大；对于搜索过程中所产生的动态存储空间，传统搜路法搜索时遍历的节点数要多于A*搜路算法，在所办进路复杂时尤为明显。总体来说，A*搜路算法更加节省存储空间。

(4)可靠性

一个有效的算法其可靠性要通过程序的完善和强壮性来实现，A*搜路算法的程序编写还不够精良，和已经实际运行很多年的传统搜路法相比，A*搜路算法的可靠性还需要在实际应用中不断完善增强。但在满足仿真实验平台的需求上，A*搜路算法的可靠性已达到预期效果。

(5)通用性

传统搜路法和A*搜路算法均基于站场型数据结构，修改容易，可移植性强；通过对多个不同的站场图进行实验，用A*搜路算法均能准确的搜出所需基本进路，其通用性得到了验证。

5 结论

由于A*算法本身的高效性及启发函数的设计而具有的完备性，使得其应用于车站进路搜索成为可能。经实验验证和分析，采用满足进路搜索需求的A*算法能够快速准确的搜出所需基本进路，动态生成进路表。综合各种性能的优劣，总体来说，A*进路搜索算法在很多方面都优于或等同于传统搜路法，而其不足之处在当前的仿真实验环境下也能够克服，达到了提高进路办理效率的目的。

[1] 文武臣，王晓明.计算机联锁的数据结构及进路搜索算法[J].重庆工学院学报：自然科学版，2008，22(6):51-53.

[2] George F.LUGER.人工智能[M].史忠植，等，译.北京:机械工业出版社，2006:96-103.

[3] 刘浩，鲍远律.A*算法在矢量地图最优路径搜索中的应用[J].计算机仿真，2008，25(4):253-256.

[4] 王晓明，郭进，姚琨岚.铁路车站信号选路中图论应用的研究[J].铁道学报，1989，11(2):52-57.

[5] 李明哲.图论及其算法[M].北京:机械工业出版社，2010.

[6] 赵志熙.计算机联锁系统技术[M].北京:中国铁道出版社，2008.

[7] 王瑞峰.铁路信号运营基础[M].北京:中国铁道出版社，2008:85-93.

[8] Michael MAIN， Walter SAVITCH.数据结构与面向对象程序设计[M].刘东，张丽，译.北京:清华大学出版社，2007:480-484.

[9] B V Cherkassky， A V Goldberg and Tomasz Radzik. Shortest paths algorithms: Theory and Experimental Evaluation[R]. Technical Report 9321480， Computer Science Department， Stanford University， 1993.