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


Return to Articles