Informed Search: Greedy Best-First Search — Beginner-Friendly Notes

1. What "Informed" Means

Use a heuristic $h(n)$ — an estimate of cost from $n$ to goal — to guide search toward promising nodes.

• Greedy Best-First: always expand node with smallest $h(n)$ (closest seems to goal). It is greedy — picks what looks best now.

2. How It Works

Priority queue by $h(n)$ only (ignores actual cost so far $g(n)$).

frontier = priority queue by h(n)
push initial with h(initial)
while frontier not empty:
  node = pop smallest h(n)
  if goal_test(node): return path
  for child: push child with h(child)

Heuristic example: straight-line distance to goal on map, or "number of misplaced tiles" for 8-puzzle.

3. Example — Road Map (Arad → Bucharest)

• $h(n)$ = straight-line distance. Greedy expands the city that looks closest to Bucharest, even if path via it is longer. Can get stuck on a seemingly close but actually costly road.

4. Properties (important for exam)

Property	Value	Why?
Complete	No (can loop, especially without visited set)	Goes down greedy path forever
Optimal	No	Ignores $g(n)$, so cheaper longer-looking path missed
Time / Space	$O(b^m)$ worst, but often much better with good heuristic	Depends on heuristic quality

5. Why Still Useful

• Very fast when heuristic is good — goes straight to goal.
• Used inside A* — Greedy is the $h(n)$ half of A*; A* adds $g(n)$ to fix optimality.

6. Common Mistake

Thinking "best-first" means "best path" — it means "best heuristic". Best looking ≠ best actual.

7. One-Line Summary

Greedy Best-First expands the node with smallest heuristic $h(n)$, is fast but incomplete and non-optimal, and is the heuristic-only precursor to A*.

8. Quick Self-Check

1. Give an 8-puzzle heuristic $h(n)$.
2. Why can Greedy fail to find optimal route even if heuristic seems reasonable?