# A*

Published
 Completeness - Complete if the heuristic is consistent. Optimality - Optimal if the heuristic is admissible Time Complexity - O(bd) Space Complexity - O(bd)

## Visual Example Current Node Frontier
A3 B3, C4
B3 D3, C4, E4
D3 F3, C4, E4
F3 C4, E4
Goal Node Found

The subscript number associated with each node, for example C4, is the f(n) value of the node.

1. We start from the root node A3.
2. We check to see if A3 is a goal node. It's not, so we add it's children, nodes B3 and C4, to the frontier.
3. We remove node B3 from the frontier and check if it's a goal node. It's not, so we add it's children, nodes D3 and E4, to the frontier.
Because C4 and E4 have the same cost, we sort them alphabetically in the frontier.
4. We remove node D3 from the frontier and check if it's a goal node. It's not, so we add it's child, node F3, to the frontier.
5. We remove node F3 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 E4 in the queue, but we find a shorter path to node E, where the path cost is 3, then we replace the existing node E4 with E3, 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.