- 2069 Bhadra · 9 marks
Hill climbing and its problems
Short answer
Hill climbing is a local greedy search that always moves to the best neighbouring state and stops when no neighbour improves. Its problems are local maxima, plateaus, and ridges; solutions include random restarts, sideways moves or big jumps, and applying several moves at once.
Discuss the hill-climbing search algorithm along with the problems associated with it and discuss their solutions.
Hill climbing is a local, greedy search algorithm that continually moves in the direction of increasing value (uphill) of an evaluation (objective) function until it reaches a peak where no neighbour is better. It keeps only the current state, does not look ahead and does not backtrack. It is like climbing a mountain in fog by always stepping to the highest neighbouring point.
Algorithm (steepest-ascent)
current = initial state
loop:
neighbours = all successors of current
best = neighbour with highest value
if value(best) <= value(current):
return current (peak reached)
current = best
Variants:
- Simple hill climbing: moves to the first neighbour that is better than the current state.
- Steepest-ascent: examines all neighbours and moves to the best.
- Stochastic: chooses randomly among the uphill moves.
- First-choice: generates random neighbours until a better one is found.
Advantages: very little memory (O(1)), fast, simple, often finds a good solution (e.g. 8-queens: reduces the number of conflicting pairs).
Problems and their solutions
| Problem | Description | Solution |
|---|---|---|
| Local maximum | A peak higher than its neighbours but lower than the global maximum; the algorithm stops there | Random-restart hill climbing: run from many random start states and keep the best; backtracking to an earlier state and take another path; simulated annealing (occasionally accept worse moves) |
| Plateau (flat area) | All neighbours have the same value, so there is no uphill direction (may be a flat local maximum or a shoulder) | Make a big jump (random move far away) or allow sideways moves with a limit on their number |
| Ridge | A narrow ridge rising slowly where all single moves go downhill although the ridge itself goes up | Apply two or more rules/moves at once (move in several directions), or use bidirectional/diagonal moves |
Other remedies: tabu search (remember visited states), genetic algorithms, and using a better evaluation function.
Properties: not complete, not optimal; the quality depends on the starting state and the shape of the landscape.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Hill climbing; simulated annealing · Artificial Intelligence, chapter 3
- Design and construction problems of hill roads · Transportation Engineering I, chapter 5 · asked 11×
- Binary search with algorithm and example · Data Structure and Algorithm, chapter 8 · asked 4×
- Geotechnical problems and their solutions · Soil Mechanics, chapter 1 · asked 2×