Back to Study Material Artificial Intelligence

Hill climbing search

Hill climbing is a local search algorithm that starts from an initial solution and repeatedly moves to a neighboring solution with a better evaluation scor...

Hill climbing search

Greedy Ascent Through the Solution Space

Hill climbing is a local search algorithm that starts from an initial solution and repeatedly moves to a neighboring solution with a better evaluation score, continuing until no neighbor offers improvement. The name evokes the image of climbing a hill in dense fog — you always step toward higher ground without seeing the full landscape.

The basic algorithm maintains a current state and evaluates all its immediate neighbors according to a heuristic function. It selects the neighbor with the highest value and moves to it. If no neighbor is better than the current state, the algorithm terminates and reports the current state as a local optimum.

The critical limitation of hill climbing is that it can get stuck in three types of traps. A local maximum is a state better than all neighbors but not the global best. A plateau is a flat region where all neighbors have equal value, giving the algorithm no direction to move. A ridge is a narrow peak in the search landscape where neighboring states in all available directions go downhill, even though a path across the ridge leads to a higher peak.

A concrete example: solving the 8-queens problem by hill climbing places queens on a chessboard and measures conflicts. The algorithm moves queens to positions that reduce conflicts. It often reaches low-conflict configurations quickly but may stall at states with two or three conflicts that no single queen move can eliminate, requiring a restart.

Variants address these limitations. Steepest-ascent hill climbing always picks the best neighbor. Sideways moves allow moving to equally scored neighbors to escape plateaus. Random restart hill climbing runs the algorithm many times from random starting points and keeps the best result found. Stochastic hill climbing randomly selects among neighbors better than the current state.

Exam tip: Know all three types of failure modes — local maximum, plateau, ridge — and know that random restart addresses local maxima. Hill climbing is often contrasted with simulated annealing in exam questions.