# A* Informed Search

## Algorithm Details

Year : 1968

Family : Informed Search

Authors : Peter E. Hart; Nils J. Nilsson; Bertram Raphael

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.