Greedy Best-First Search

Greedy best-first search selects the nod that appears closest to the goal. This uses only the heuristic estimate $h(n)$, ignoring the cost accumulated so far.

Expansion rule: Maintain the frontier in a priority queue, always expand the node with smallest $h(n)$ value.

Properties

• Complete: No
  • can get trapped following misleading heuristic
  • loop or chase deep subtrees
  • completeness is not guaranteed even with cycle checking
• Optimal: No
  • ignores past cost $g(n)$
  • may find a suboptimal solution even with admissible $h(n)$
• Time complexity: $O(b^m)$ (worse case)
  • can be dramatically reduced with good heuristic
• Space complexity: $O(b^m)$

Example