基于改进Dijkstra算法的进路搜索研究 |
| |
引用本文: | 杜文文,杨扬.基于改进Dijkstra算法的进路搜索研究[J].铁路计算机应用,2020,29(9):62. |
| |
作者姓名: | 杜文文 杨扬 |
| |
作者单位: | 西南交通大学 信息科学与技术学院,成都 611756 |
| |
基金项目: | 中国铁路总公司科技研究开发计划重点课题(2017X011-A) |
| |
摘 要: | 进路搜索是计算机联锁的核心部分,其准确性及高效性对保证行车安全至关重要。建立铁路站场结构的有向图模型,将站场进路搜索问题转化为有向图的遍历问题;根据铁路站场简化图的特点,从数据存储结方式和队列结构2个方面改进传统Dijkstra算法,采用广度优先搜索方式,提出以最短路径为目标函数的进路搜索策略;编制仿真程序对该算法进行验证,结果表明:基于改进Dijkstra算法能够正确、高效地完成多种类别进路搜索。
|
关 键 词: | 进路搜索 有向图 Dijkstra算法 最短路径 |
收稿时间: | 2020-03-25 |
Research on route search based on improved Dijkstra algorithm |
| |
Institution: | Southwest Jiaotong University, College of Information Science and Technology, Chengdu 611756, China |
| |
Abstract: | Route searching is one of the core parts of computer interlocking and its efficiency and accuracy is vital to ensure the safety of traffic control. A directed graph model based on the structure of railway station yard is modeled and the problem of searching routes in a railway station yard is then converted as the problem of traversing a directed graph. According to the characteristics of simplified railway station yard graph, traditional Dijkstra algorithm is improved from the aspects of data storage and queue structure, breadth-first search is adopted, and a route searching strategy with the shortest path as objective function is proposed. Furthermore, a simulation program is built to verify this algorithm and the simulation results show that this improved Dijkstra algorithm can complete searching types of routes accurately and efficiently. |
| |
Keywords: | |
|
| 点击此处可从《铁路计算机应用》浏览原始摘要信息 |
| 点击此处可从《铁路计算机应用》下载免费的PDF全文 |