Greedy Best-First Search

Published
Completeness - Not complete. The algorithm is vulnerable to infinite loops if repeated states aren't detected.
Optimality - Not optimal.
Time Complexity - O(bm)
Space Complexity - O(bm)

Visual Example

Current Node Frontier
A B3, C4
B3 D1, C4, E5
D1 F0, C4, E5
F0 C4, E5
Goal Node Found

The subscript number associated with each node, for example C4, is the heuristic value of the node.

  1. We start from the root node A.
  2. We check to see if A 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 D1 and E5, to the frontier.
  4. We remove node D1 from the frontier and check if it's a goal node. It's not, so we add it's child, node F0, to the frontier.
  5. We remove node F0 from the frontier and check if it's a goal node. It is, so we're done.

Algorithm Notes


Return to Articles