Research On Improved A* Algorithm Based On Path Search

With the rapid development of modern computer technology in the world,the function of hardware and software is developing rapidly.Artificial intelligence emerges as the times require in the development of science and technology,and it is a very important frontier subject in modern science and technology.The path of search problem is one of the most important issues,of course,and this is also the focus of research.This paper studies the algorithm of depth first search,breadth first search algorithm,Dijkstra algorithm and A* algorithm in the path of search problem in performance,analyzes their advantages and disadvantages,and focus on the deficiency of A* algorithm in pathfinding problems of improvement and optimization.A* algorithm is a heuristic path search algorithm,through the evaluation of the evaluation function giving its search path.However,when the path is encountered in the path of the dead end trap,according to the evaluation function to choose other paths,the dead end node is also stored in the closed list.Finally,the path extraction will be repeated to investigate the dead end node.Although the optimal path will be abandoned,but meaningless access will take up a lot of memory and reduce search efficiency.This paper proposes a shortcut backtracking A* algorithm to avoid the problem of repeated access to a dead end.The new algorithm of a parent node table adds the parent node information attribute of each node,and ultimately to the node information,the parent node table closes list back and get the optimal path to avoid duplication of redundant nodes from the search speed reduction problem.When there are many starting and ending nodes in the routing problem,the A* algorithm can not determine which path is the shortest,and only through multiple calls can be used to find the optimal path.Based on this,the shortcut back to the A* algorithm is optimized,and A* algorithm is proposed for multi to multi path extraction.The algorithm can be used to store several initial nodes in the open list,and calculate the distance of the nearest target node in order to plan the optimal path.The optimized algorithm can reduce the performance of the A* algorithm and avoid the problem of reducing the number of nodes caused by repeated investigations.Finally,by using the depth first search algorithm,breadth first search algorithm,Dijkstra algorithm and A* algorithm for solving obstacle free backtracking two-dimensional map pathfinding problems and random obstacle in two-dimensional map pathfinding problems,four kinds of path search algorithm of node number,time spent,and whether the four aspects of the optimal path cost is analyzed experiment.The experimental results show that the A* algorithm has the highest search efficiency and good generality.