View source for 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.ezproxy.canberra.edu.au/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