A* Informed Search
Jump to navigation
Jump to search
Algorithm Details
Year : 1968
Family : Informed Search
Authors : Peter E. Hart; Nils J. Nilsson; Bertram Raphael
Paper Link : https://ieeexplore.ieee.org/document/4082128/
Time Complexity :
Problem Statement
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.
PseudoCode
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
Applications
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.