Local Search: Hill Climbing — Beginner-Friendly Notes

1. When Local Search Is Needed

When state space is huge and you have no path to remember — only care about final state (optimisation), not the path. Example: 8-queens, scheduling, circuit layout.

Idea: keep one current state and move to neighbours that look better — like climbing a hill in fog, only seeing nearby ground.

2. Simple (Steepest-Ascent) Hill Climbing

current = initial
loop:
  neighbours = all states one move from current
  next = neighbour with highest value (if maximising)
  if value(next) <= value(current): return current  # peak reached
  current = next

Value / objective function $Value(s)$ scores state (higher = better). For minimisation, use cost.

3. Example — 8-Queens

• State: all 8 queens on board, one per column.
• Value = number of non-attacking pairs (max 28). Neighbour = move one queen in its column.
• Hill climbing moves to neighbour with highest value until no neighbour improves.

4. Why It Gets Stuck (exam must-list)

Trap	What Happens	Fix (preview)
Local maximum	Peak that is not global best — no uphill move	Random restart, simulated annealing
Plateau / flat	Neighbours equal value → no direction	Random sideways move, allow limited sideways
Ridge	Narrow uphill path not aligned to moves	More expressive moves

Hill climbing is incomplete (can stop at local optimum) and non-optimal but uses $O(1)$ memory and is very fast per step.

5. Variants (mention in exam)

• Steepest-ascent: check all neighbours, pick best.
• First-choice: pick first better neighbour randomly — good when many neighbours.
• Random-restart: run many random starts, keep best peak — makes it complete probabilistically.

6. One-Line Summary

Hill climbing iteratively moves to the best-valued neighbour until a local peak, is fast with $O(1)$ memory but incomplete due to local maxima, plateaus and ridges.

7. Quick Self-Check

1. Why is hill climbing called "local" and "greedy"?
2. Name one fix for local maxima.