Heuristic Path Finding Algorithm Based On Small World Model

With the development of economy, the application field of optimal path-findings is used widely, such as road network navigation, gaming industry, the logistics industry, etc. Among them, the road network navigation is the attention of many scholars. With the growing road network data, the performance of conventional path findings seems to be slightly insufficient, which can’t search a path between any two points in the vast road network. The most popular path finding currently is hierarchical algorithm, whose idea is to abstract a traffic network with higher-weight nodes and paths, by reasonable switching the detailed road network and the new road network making the path finding algorithm obtain better performance of space and time. Although hierarchical algorithm optimizes the performance of path findings in huge map data, its quality is behind A* path finding algorithm.To solve the above problem, drawing on the hierarchical algorithm, the theory of small world network model and routing theory, this paper gives a path finding strategy: Heuristic path finding algorithm based on small world model (referred HPAS algorithm) that promotes efficiency of path-finding quality guarantee. First, referencing on the hierarchical algorithm thought and the small world network model, with the clustering analysis on the traffic network, network zoning divides each cluster in the clustering results into different areas. Second, boundary routing nodes and internal path nodes are set, and the optimal path between adjacent routing nodes is stored in the cache. Third, in the path finding phase, A* algorithm finds the optimal path between the boundary routing nodes and internal routing nodes in each partition.The experiment consists of the path computation module, the cache module, the map database accessing module and the user request processing module and so on. The test to the road network data of the eastern and western U. S. shows that different granularity of clustering improves the efficiency of the improved A* path finding algorithm in different degree. But the length deviation between the shortest path and the solved path will be increased with a larger granularity of clustering. The simulation experiment result shows that the deviation between the average path length and the optimal path length is only 0.03%. Compared with A* algorithms, bi-directional A* algorithm and A* algorithm based on a hierarchical structure, the improved path finding algorithm has good performance in path-finding efficiency and found-path quality under the condition of the map with a larger scale.