A* Informed Search
Year : 1968
Family : Informed Search
Authors : Peter E. Hart; Nils J. Nilsson; Bertram Raphael
Paper Link : https://ieeexplore.ieee.org/document/4082128/
Time Complexity :
Informed Search algorithms have information on the goal state which helps in more efficient searching. This information is obtained by a function that estimates how close a state is to the goal state.
make an openlist containing only the starting node make an empty closed list while (the destination node has not been reached): consider the node with the lowest f score in the open list if (this node is our destination node) : we are finished if not: put the current node in the closed list and look at all of its neighbors for (each neighbor of the current node): if (neighbor has lower g value than current and is in the closed list) : replace the neighbor with the new, lower, g value current node is now the neighbor's parent else if (current g value is lower and this neighbor is in the open list ) : replace the neighbor with the new, lower, g value change the neighbor's parent to our current node else if this neighbor is not in both lists: add it to the open list and set its g
A* is often used for the common pathfinding problem in applications such as video games, but was originally designed as a general graph traversal algorithm. It finds applications in diverse problems, including the problem of parsing using stochastic grammars in NLP.