A*
Published
Completeness    Complete if the heuristic is consistent. 
Optimality    Optimal if the heuristic is admissible 
Time Complexity    O(b^{d}) 
Space Complexity    O(b^{d}) 
Visual Example

The subscript number associated with each node, for example C_{4}, is the f(n) value of the node.
 We start from the root node A_{3}.
 We check to see if A_{3} is a goal node. It's not, so we add it's children, nodes B_{3} and C_{4}, to the frontier.

We remove node B_{3} from the frontier and check if it's a goal node. It's not, so we add it's children, nodes D_{3} and E_{4}, to the
frontier.
Because C_{4} and E_{4} have the same cost, we sort them alphabetically in the frontier.  We remove node D_{3} from the frontier and check if it's a goal node. It's not, so we add it's child, node F_{3}, to the frontier.
 We remove node F_{3} from the frontier and check if it's a goal node. It is, so we're done.
Algorithm Notes
 Uses a priority queue for the frontier, where each node is sorted by it's f(n) value.
 If there is a node, say E_{4} in the queue, but we find a shorter path to node E, where the path cost is 3, then we replace the existing node E_{4} with E_{3}, rather than adding a second node E to be explored.
 The f(n) value of a node is the sum of h(n) + g(n), so f(n) = h(n) + g(n).
 The h(n) value value of a node is known as the heuristic value.

Any function can be a heuristic function, but the heuristic function is often a distance formula that attempts to predict how close a given node is to the goal node.
One example of a distance formula is the Manhattan distance formula.  The g(n) value of a node is the distance from a given node to the root node.
Return to Articles