罗耀云

（兰州铁道设计院有限公司，甘肃兰州 730030）

目前，我国新建及改造车站信号控制系统均采用计算机联锁系统，其可靠运行不仅依赖于硬件系统，更依赖于联锁软件，进路控制是联锁软件的核心功能。进路控制包括进路建立和进路解锁两大任务。进路建立可分为进路搜索、道岔转换、选排一致性检查、联锁条件检查、进路锁闭、信号开放、信号保持等阶段。进路搜索是进路控制的基础和关键环节，其准确高效性将决定整个联锁软件的安全性和执行效率。如何准确高效地完成进路搜索取决于联锁软件所采用的进路搜索算法，而进路搜索算法的实现又依赖于所采用的数据结构。目前主要采用基于总进路表和站场型两种数据结构建立进路搜索算法[1-3]。基于总进路表的进路搜索适用于规模较小、进路数量较少、长期不进行改建或扩建的车站。基于站场型数据结构的进路搜索则不受上述限制，其搜索算法有DFS 算法和广度优先搜索（Breadth First Search，BFS）算法。文献[4]及文献[5]提出的基于DFS 算法图匹配在搜索增广路时不会出现“花”的情况；文献[6]、文献[7]、文献[8]采用DFS 加约束条件的站场遍历算法；文献[9]采用有向无环图与二叉树结合的进路搜索算法，系统功能不完善。这些算法均存在回溯搜索的问题。针对此问题，提出一种DFS 高度无往返优化算法，提高进路搜索效率。

1 联锁软件数据结构

铁路车站计算机联锁数据是指在联锁计算机中参与运算的所有数据，它们在计算机中的存储和组织方式称为数据结构。……