## Definition **Hill climbing** is a local search algorithm. At each step it considers the *neighbors* of the current state and moves to the one with the best objective value. No path history, no backtracking — just current state plus a notion of "neighbour". ## Algorithm ``` current ← initial_state loop: neighbor ← best-valued neighbor of current if value(neighbor) ≤ value(current): return current # local optimum current ← neighbor ``` (Maximisation; flip the inequality for minimisation.) ## Properties - **Complete:** no — may stop at a local optimum. - **Optimal:** no — finds local, not global, optima. - **Space:** $O(1)$ — keeps only the current state. - **Time:** depends on the landscape; can be very fast for unimodal problems. ## Classic Pathologies 1. **Local optima.** No neighbour improves; algorithm halts below the global best. 2. **Plateaus.** All neighbours have the same value; no progress direction. 3. **Ridges.** The path to better values requires *worse* intermediate states. ## Variants - **Steepest-ascent:** picks the absolute best neighbour. - **First-choice:** picks the first improving neighbour found — useful when neighbourhoods are large. - **Random restart:** run hill climbing multiple times from random starts; keep the best. Surprisingly effective in practice. - **Stochastic hill climbing:** sometimes accepts a worse neighbour with some probability — leading toward [[Simulated Annealing]]. ## When to Use - Continuous optimisation with smooth, unimodal-ish landscapes. - Quick local refinement on top of a global search. - Problems where any reasonable solution is acceptable. For problems with many local optima, switch to [[Simulated Annealing]] or genetic algorithms. ## Related - [[Simulated Annealing]] - [[Heuristic Search]] - [[Gradient Descent]]