Search Algorithms
Local search

Hill Climbing

Always step toward the best-looking neighbour until nothing looks better.

Interactive demo coming soon — read the theory below

The idea

Hill Climbing is a local search method: it holds a single current solution and keeps moving to the best neighbouring solution that improves things. When no neighbour is better, it stops. It never looks back or remembers where it has been, so it is fast and memory-light, but it can get trapped short of the true best answer.

How it works

  1. Start at some initial state (often chosen randomly) and treat it as your current solution.
  2. Score the current state using an objective function (higher = better, like altitude on a hill).
  3. Look at all the neighbours: states reachable by one small change to the current state.
  4. Score every neighbour and pick the single best one (this is the 'steepest ascent' choice).
  5. Compare the best neighbour to your current state.
  6. If that neighbour is better, move to it (it becomes the new current) and go back to step 3.
  7. If no neighbour is better, stop: you are at a local optimum and return the current state.
  8. (Optional) If stuck, restart from a new random state and keep the best result found across restarts.

OPEN, CLOSED & the data structures

Almost nothing, which is the point. It keeps just the current state plus its objective-function score. Each step it temporarily generates the list of neighbours to compare, but discards them after choosing. There is no OPEN list, no CLOSED list, no path history, and no stack or queue, so memory stays tiny and constant.

Pseudocode

function HillClimbing(problem):
    current = initial_state(problem)          # a single candidate
    loop:
        neighbours = generate_neighbours(current)
        best = neighbour in neighbours with highest value   # steepest ascent
        if value(best) <= value(current):
            return current                    # local optimum: no improvement
        current = best                        # move uphill, no backtracking

# Random-restart wrapper to escape bad local optima:
function RandomRestartHillClimbing(problem, tries):
    best_overall = none
    repeat tries times:
        result = HillClimbing(problem)        # fresh random start each time
        if best_overall is none or value(result) > value(best_overall):
            best_overall = result
    return best_overall

At a glance

Complete?No. Plain hill climbing is not guaranteed to find a solution: it stops at the first local optimum, which may not be a goal at all. Random-restart hill climbing improves the odds a lot given enough restarts, but still offers no hard guarantee.
Optimal?No. It finds a local optimum (a peak relative to its immediate neighbours), not necessarily the global optimum (the best answer overall). Because it never moves downhill and never backtracks, once it climbs the wrong hill it cannot recover on its own.
TimeDepends on the landscape, not a fixed formula. Each step costs O(number of neighbours) to score them all; the number of steps is however many uphill moves it takes to reach a peak. It often converges quickly, but bad terrain (long ridges, wide plateaus) can slow or stall it.
SpaceO(1) extra memory (constant). It stores only the current state and its score, plus a transient list of neighbours during each step. This tiny footprint is hill climbing's biggest advantage over memory-hungry searches like A*.

👍 When to use it

  • The state space is huge and storing many nodes (like A* does) is impractical.
  • You need a good-enough answer fast and can tolerate not finding the absolute best.
  • You can define a meaningful score (objective function) and small 'neighbour' moves.
  • Optimization problems like scheduling, layout, or tuning where any improvement is welcome.
  • As a cheap first attempt, often wrapped in random restarts to boost quality.

⚠️ Watch out for

  • Local maxima: a peak that is higher than everything nearby but lower than the true global peak. Hill climbing happily stops here.
  • Plateaus: a flat region where all neighbours score the same, so there is no uphill direction to guide the next move and the search can wander or halt.
  • Ridges: a narrow rising path where every single small step goes slightly downhill even though the overall ridge climbs, so steepest-ascent gets stuck.
  • No backtracking and no memory of visited states: one wrong turn cannot be undone.
  • The result depends heavily on the starting point, which is why random-restart exists.
  • Don't confuse 'best neighbour' (local, one step away) with 'best overall' (global) - they are often different.