Artificial Intelligence · AI Foundations
Hill Climbing
In AI because many real decisions are 'improve the current state' rather than 'reconstruct a cheapest path' — and hill climbing is the algorithm that idea becomes.
A* reconstructs a cheapest path from a start to a goal. A different kind of problem only asks for a good state — a timetable, a circuit layout, a cafe location — and does not care which sequence of edits produced it. Hill climbing is the algorithm for that job: stand on a state, look at its neighbours, step to a better one, and stop when every neighbour is worse. This lesson is that loop, the three landscapes that trap it, and when a restart is the whole method.
- Artificial Intelligence
- Medium level
- 5 concepts
1A good state, not a cheapest path
Path-finding search — the family A* belongs to — keeps a frontier of partial routes and returns the route itself. Local search keeps one current state and returns that state. The edits that got you there are thrown away, because the job was never 'how did we travel' — it was 'where should we stand'.
The campus running example is placing a cafe on a single street of eight blocks. Each block has an expected daily customer count. The question is which block to pick, not which walk visited the others. A* would be the wrong tool: there is no start-to-goal path to reconstruct, only a quality number sitting on each block.
Reach for hill climbing when the state is the answer and a neighbour is a small legal edit — move one block, swap two timetable slots, flip one bit. Reach for A* when the answer is a route and every prefix of that route has to stay cheap.
The product of the algorithm decides the family — a route, or a state.
| Family | Keeps | Returns | Campus job |
|---|---|---|---|
| Path-finding (A*) | A frontier of routes | A path | Walk from gate to library |
| Local (hill climb) | One current state | A state | Pick a cafe block |
How does hill climbing differ fundamentally from systematic search algorithms like BFS or A*?
- It operates on complete state configurations seeking peak quality without retaining path history
- It guarantees discovering the globally optimal path with zero heuristic cost
- It requires storing all visited nodes in a first-in first-out queue
- It is restricted strictly to binary decision tree representations
Local search algorithms like hill climbing keep a single current state and move to neighbors, caring about the final state rather than the path taken.
2The climb itself
Hill climbing starts on a state and scores it with an objective — here, expected daily customers. A neighbour is a legal one-step edit: from block 3 the neighbours are blocks 2 and 4, one door each way. The loop is: look at every neighbour, move to the best one that scores strictly higher than you, and repeat. When no neighbour is better, you stop and return the current block.
That stop is the whole algorithm, not a failure handler. The climber has no memory of earlier blocks and no view of the rest of the street. It cannot step downhill to cross a valley, because a worse neighbour is refused by construction.
Figure. Eight blocks and their customer counts. The climb from block 3 stops on the terracotta bar at 2 (25). The sage bar at 7 is the global best (30) and is unreachable without walking downhill through the valley at 4.
One climb
- Score hereRead the objective on the current state — customers on this block.
- Inspect neighboursScore every legal one-step edit. From a street block that is the two doors.
- Step or stopMove to the best strictly better neighbour; if none exists, return the current state.
One climb from block 3
Street scores, west to east: block 0: 12, 1: 18, 2: 25, 3: 20, 4: 16, 5: 28, 6: 22, 7: 30. Start at block 3.
- At 3 (score 20): neighbours 2 (25) and 4 (16)best better is 2
- Move to 2 (25): neighbours 1 (18) and 3 (20)both worse — stop
- Returned block2, score 25
Pro tip. The street's best block is 7 at 30 customers. The climb never saw it: from 2, the only way east is back through 3, which the rule forbids.
Coding lab. Steepest-ascent hill climbing runs in the app, with checks on your output.
3Local maxima, plateaus, ridges
A local maximum is a state better than every neighbour and worse than some state elsewhere. Block 2 is one: 25 beats 18 and 20, and loses to 30. The algorithm cannot tell a local maximum from the global one, because it never looks past the two doors.
A plateau is a flat run of equal scores. Strict hill climbing refuses a sideways step — equal is not better — so it stops on the first flat tile even when a peak sits at the far end of the shelf. A ridge is a thin high path that only a diagonal or coordinated edit can follow; one-feature neighbours step off it and the score drops, so the climber treats the ridge as a maximum.
All three are properties of the landscape plus the neighbour relation, not bugs in the loop. Change the neighbour relation — allow a two-block jump, or a sideways step on a plateau — and the same street becomes a different problem.
Each trap is a place where a better state exists and the neighbour relation cannot reach it in one uphill step.
| Trap | What you see | Why you stop |
|---|---|---|
| Local maximum | Every neighbour is worse | The better state is past a valley |
| Plateau | Every neighbour is equal or worse | A sideways step is refused |
| Ridge | Every one-feature neighbour is worse | The uphill move is a coordinated edit |
4Restarts, stochastic steps, annealing
The cheapest repair is to start again. Random-restart hill climbing runs the same loop from a fresh random block and keeps the best finish. From block 6 on this street the climber steps to 7 and finds 30; from block 5 it sticks at 28. Two restarts already beat a single climb from 3.
Stochastic hill climbing picks among the better neighbours at random instead of always taking the single best. It still refuses downhill steps, so a valley still blocks it, but it is less enslaved to one greedy path on a plateau. Simulated annealing goes further: it sometimes accepts a worse neighbour, with that chance falling as a temperature cools, which is how a climber can cross the valley at block 4. The cooling schedule is a design choice, not a derived constant — this lesson names the idea; it does not tune a schedule.
Two restarts on the same street
Same scores as the climb from block 3. Restart A starts at block 5; restart B starts at block 6.
- Restart A at 5 (28): neighbours 4 (16), 6 (22)both worse — finish 28
- Restart B at 6 (22): neighbours 5 (28), 7 (30)step to 7
- At 7 (30): only neighbour 6 (22)stop at 30
- Keep the best finish of {25, 28, 30}block 7, score 30
Pro tip. The original climb from 3 is still in the set — restarts add candidates, they do not erase the first run. The method is 'best of several finishes', not 'trust the last one'.
5When the climb is the right tool
Hill climbing earns its keep on large state spaces where a neighbour is cheap to score and a pretty-good state is enough — timetable repair, circuit placement, a first cut of a tour. It is the wrong tool when you must return a cheapest path, when a neighbour is as expensive to score as solving the problem, or when any local maximum is an unacceptable answer.
It also does not replace the informed-search guarantees of the last two lessons. There is no admissibility story here: the climber can stop on 25 while 30 sits four blocks away, and that is a legal run. If the job needs the optimum and a path, stay with A*. If the job needs a good state and you can afford restarts, climb.
Figure. Hill climbing earns its keep when a neighbour is cheap to score and a pretty-good state is enough — timetable repair, circuit placement, a first cut of a tour. It is the wrong tool for a cheapest path. There is no admissibility story: the climber can stop on 25 while 30 sits four blocks away.
A campus planner wants the cheapest walking route from the gate to the library, and must show the route. Why is hill climbing the wrong algorithm?
- Because hill climbing returns a state, not a path, and this job's answer is the route itself
- Because hill climbing cannot use a heuristic
- Because the street has a local maximum
- Because A* is always faster than local search
The product of hill climbing is a state. A cheapest-route job needs the path A* reconstructs. Speed and heuristics are beside the point — the families return different objects.
Notes
- Hill climbing is local search: keep a current state, move to a better neighbour, stop when none is better.
- It returns a state, not a path — the route taken is discarded.
- Local maxima, plateaus and ridges are the three ways a better global state can sit next door and still be unreachable.
Exam traps & shortcuts
- If the job is 'find a good arrangement' rather than 'the cheapest route here', you want local search, not A*.
- A stuck climber is not a bug in the loop — it is the definition of a local maximum.
- Random restart is the cheapest insurance: run the same climb from new starts and keep the best finish.
Recap
Next: AND-OR search.
- Local search
- Keep one state, return that state. The edits are discarded — the job was where to stand, not how you walked.
- The loop
- Move to a strictly better neighbour; stop when none exists. That stop is the algorithm.
- Traps
- Local maxima, plateaus and ridges hide a better state behind a downhill or sideways step the loop refuses.
- Restarts
- Run the same climb from new starts and keep the best finish. There is no optimality certificate.
Practise Hill Climbing
Reading is free and needs no account. Practice, mocks and progress live in the app.
- 2 quick checks with worked explanations
- Timed mocks scored with the real marking scheme
- Readiness tracked per topic, kept on your device