| A* algorithm is a heuristic search algorithm with the optimal time, with which the reachable shortest path can be exactly and high effectively obtained by taking evaluation function as guidance and combining the path finding ideas of Dijkstra's algorithm and Greedy Best-First-Search algorithm. A* algorithm is widely used in the field of path finding and traveling in graph, especially in the game development and GIS. Its accessibility and efficiency has been widely recognized. However with the enlargement of the search space, the calculation times of heuristic function,which affects the time complexity of algorithm, is greatly increased and finally tending to exponential growth, because of the need to implement a breadth-first search. Therefore, a variety of algorithms are proposed after A* algorithm, which are called inherited A* algorithms, such as the D* algorithm which is first used for finding path for robot on Mars, the Iterative Deepening A* algorithm which controls the depth of searching, and the Simplified Memory Bounded A* algorithm which controls the bound of used memory when search. There are two ways of these inherited A* algorithms. One is optimizing the calculation of heuristic function. The other is controlling the depth of searching.An efficient optimization algorithm with direction factor was presented, based on common sense illation of artificial intelligence and mathematics vector calculation in this paper, and the optimization contains three strategies:Firstly, search in the direction from start node to goal node direction factor,which makes the middle side nodes close to the goal node.Secondly, move toward the goal node location under direction factor controlling.Thirdly, when a dead-end is encountered, return the recent position as a faulttolerant means making sure find the right way.Finally, the optimization algorithm is applied to optimize the Iterative Deepening A* and the Simplified Memory Bounded A* algorithm, which inherited A* algorithm. |
PDF Full Text Request