Improving A Star Search In Road Networks

With the development of economy, the city’s geographic information data is exploding and the structure of urban road network has become increasingly complex. Whether it can find the shortest path from departure to destination from the complex urban road network almost in real time, which is getting more and more from people. A-star algorithm as a kind of classic heuristic pathfinding algorithm, widely used in urban traffic pathfinding. With the progress of the times, many improved A-star algorithms have been proposed by people. Among these, using binary heap storage structure instead of the traditional linear OPEN table to storage structure is remarkable. Although the efficiency improve obviously, it gradually difficult to meet the needs of users. This paper launches research on the premise of the improved A-star algorithm under these background.Firstly, this paper describes the relevant knowledge of graph and graph search algorithm. It emphatically introduces the heuristic pathfinding algorithm--A-star algorithm that it is research object of this paper. This paper analyzes A-star algorithm and points out it’s bottleneck.And then this paper introduces some improved solutions that proposed by others. Based on research of the above improvement solutions and in conjunction with the mature multi-core multi-thread technology, this paper presents two improved algorithms solutions.One solution is the node parallel extensions and OPEN list divide into several some parts and find out the minimum value generation nodes parallelly. The solution to the node is expanded to the adjoining node value, whether in the OPEN and CLOSE list medium takes on the read operation in parallel by multiple child threads, nodes and OPEN list to add or change the value, the CLOSE list write operations carried out by the main thread serial additions such as node. At the same time, in order to reduce the minimum generation value node in the OPEN list of lookup time, based on the idea of "divide and conquer", this paper proposed divided the OPEN list into some small lists, and stored by the multi-thread binary heap parallelly, each thread need to find the smallest generation the value of a single list pass the node to the main thread to get the global minimum value node.The other solution is the two-way search path parallelly. It proposes open two threads simultaneously toward each other which route from originating node and destination node, and two threads each independently owned OPEN list table but share a CLOSE list and this table is synchronized, when one of its own thread when that CLOSE find the minimum value of the node in owns the OPEN list and then the put into the CLOSE list, if the node is found to exist in the CLOSE list and marked by the other thread, which indicate that the path has been found. After analysis, the algorithm is applicable to the solution that the shortest path between two nodes is only have one or have more but they have overlapping nodes between multiple paths.Finally, the experiments show that two improved solutions have good performance when the road network is complex and the starting node and the destination node is far away.