Greedy Best First Search (COMP3411)

Greedy Best First Search is a basic search that uses path-cost to determine the next node to expand.

Classification

  • Complete: No, it can get stuck in loops. It's complete in a finite space with state-checking
  • Time Complexity: $O(b^m)$
  • Space Complexity: $O(b^m)$ (it keeps all nodes in memory)
  • Optimality: Not optimal, it can follow initially good but misleading paths (same as dfs. However, a good heuristic can reduce time and memory costs substantially