---
title: "Hill climbing and its problems"
subject: "Artificial Intelligence"
chapter: 3
key: "semester_6/artificial_intelligence:hill-climbing-problems-solutions"
source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/hill-climbing-problems-solutions
site: BCT Engineering
---

# Hill climbing and its problems

Artificial Intelligence · Chapter 3: Search Techniques

- Asked in: 2069 Bhadra, 9 marks
- Video: [Lec-19: Hill Climbing Algorithm in Artificial Intelligence with Real Life Examples| Heuristic Search](https://www.youtube.com/watch?v=3SiWtAnUROs) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/hill-climbing-problems-solutions
- Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-3

## Question

Discuss the hill-climbing search algorithm along with the problems associated with it and discuss their solutions.

## 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.

## Answer

**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)
```text
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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How does hill climbing choose its next state?
   A. It keeps a full history and backtracks when stuck
   B. It moves to a neighbour with a higher evaluation value and stops when no neighbour is better
   C. It randomly jumps anywhere in the space
   D. It expands the shallowest node first
   Answer: B. Hill climbing is greedy and local: it keeps only the current state, moves uphill, and stops at a peak with no better neighbour. (Key point: Hill climbing idea)

2. What is a local maximum and a suitable remedy?
   A. A flat area; fix it with a big jump
   B. A peak better than its neighbours but lower than the global maximum; fix it with random-restart hill climbing or simulated annealing
   C. A narrow ridge; fix it with sideways moves
   D. The goal state; no fix needed
   Answer: B. The search stops at a local peak. Restarting from random states or occasionally accepting worse moves lets it escape. (Key point: Local maximum)

3. On a plateau, why does hill climbing fail, and what helps?
   A. All neighbours have equal value so there is no uphill direction; use a random big jump or limited sideways moves
   B. All neighbours are worse; use ridge moves
   C. The memory runs out; use a bigger queue
   D. The evaluation function is negative; negate it
   Answer: A. With equal neighbours there is no direction of improvement. A big random jump or a limited number of sideways moves can get past it. (Key point: Plateau)

4. What is the ridge problem and its solution?
   A. A single flat region; add a jump
   B. A narrow high path where every single move goes downhill although the ridge rises; apply two or more moves at once
   C. A very deep valley; use backtracking only
   D. A cycle in the graph; use a visited list
   Answer: B. On a ridge single-step moves all look worse, so combining several moves or moving in more directions is needed. (Key point: Ridge)

## Related in Artificial Intelligence

- [Hill climbing; simulated annealing](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ahill-climbing-simulated-annealing) — Artificial Intelligence, chapter 3

## Related in other subjects

- [Design and construction problems of hill roads](https://www.bctengineer.com/question.md?key=semester_6%2Ftransportation_engineering_i%3Ahill-problems) — Transportation Engineering I, chapter 5, asked 11×
- [Binary search with algorithm and example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-algorithm-example) — Data Structure and Algorithm, chapter 8, asked 4×
- [Geotechnical problems and their solutions](https://www.bctengineer.com/question.md?key=semester_4%2Fsoil_mechanics%3Ageotechnical-problems-solutions) — Soil Mechanics, chapter 1, asked 2×