Research And Design Of Route Search Based On Depth-First Search

With the development of technology,railway equipment is developing in the direction of more intelligence and cost saving.Interlocking system is the core system to ensure the safe operation of train in railway station.The function of route control is realized by route search.This thesis first studies the route search methods and analyzes shortcomings such as poor universality and low search efficiency.Then,a route search method based on depth-first search algorithm is proposed in order to reduce the preparatory work and improve the security and reliability of the search program.In order to achieve the above goals,the specific work of this paper is as follows:(1)This thesis studies the existing search methods to analyze the advantages and disadvantages of the existing search methods.Also,determines the research direction of the thesis.(2)This thesis studies the theoretical knowledge of station signals and the way to realize route search in order to clarify the content of route search.Discuss the existing methods of route search,which lays a theoretical foundation for the design method of this thesis.(3)The depth first search algorithm is chosen as the route search algorithm to design the route search method.According to the design idea,the modeling rules of graphic elements in station diagram are designed based on graph theory.Also,the undirected graph model of the example station is completed.The station data structure is selected to store the graph model,which is designed according to the graph model and algorithm.According to the pruning optimization design principle,the depth-first search algorithm is modified by designing the search direction,search range and search order principles.After modification,the invalid nodes during the search is reduced.Finally the correctness of the algorithm is verified in theory.(4)This thesis builds an interlocking simulation platform by C# to verify the method.Firstly,according to the interlocking table,some routes are selected to verify the correctness of the method.Moreover,the A-Star algorithm is compared with the improved depth-first search algorithm to verify the performance.After testing and verification,the route search method designed in this thesis is correct and has good performance.Also the method can reduce the manual input data,enhance the universality of the route search program.Compared with the A-Star algorithm,the improved depth-first search algorithm has a faster search speed,fewer invalid data,and a simpler implementation.59 pictures,16 tables,54 references.