A* Informed 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.

Implementations

Python : https://gist.github.com/jamiees2/5531924

C++ : https://dev.to/jansonsa/a-star-a-path-finding-c-4a4h