---
title: "Hill climbing; simulated annealing"
subject: "Artificial Intelligence"
chapter: 3
key: "semester_6/artificial_intelligence:hill-climbing-simulated-annealing"
source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/hill-climbing-simulated-annealing
site: BCT Engineering
---

# Hill climbing; simulated annealing

Artificial Intelligence · Chapter 3: Search Techniques

- Asked in: 2075 Baisakh, 6+2 marks
- Video: [Steepest Ascent Hill Climbing | Simulated Annealing | Artificial Intelligence in hindi #22](https://www.youtube.com/watch?v=4pVYqxoPE94) — Well Academy
- 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-simulated-annealing
- 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. Why is simulated annealing important?

## Short answer

Hill climbing is a local greedy search that stops at any peak without backtracking; its problems are local maxima, plateaus, and ridges, handled by random restarts, sideways moves or big jumps, and multi-direction moves. Simulated annealing occasionally accepts worse moves with probability e^(deltaE/T), letting it escape local maxima and approach the global optimum as temperature falls.

## Answer

**Hill climbing** is a local search that repeatedly moves from the current state to the neighbouring state with the highest value of the evaluation function, and stops when no neighbour is better. It keeps only the current state (O(1) memory), has no backtracking and no look-ahead, like climbing a hill in fog.

```text
current = initial state
loop:
   best = highest-valued neighbour of current
   if value(best) <= value(current): return current
   current = best
```
Variants: simple (first better neighbour), steepest-ascent (best neighbour), stochastic and first-choice hill climbing.

#### Problems and solutions
| Problem | Meaning | Solution |
|---|---|---|
| Local maximum | A peak better than its neighbours but not the best overall; search stops | Random-restart hill climbing, backtracking, simulated annealing |
| Plateau | A flat area; all neighbours have equal value, so no direction is better | Take a big random jump, or allow a limited number of sideways moves |
| Ridge | A narrow high path; every single move goes downhill though the ridge rises | Apply several moves at once or move in more directions (e.g. diagonally) |

The algorithm is not complete and not optimal, but it is fast and uses almost no memory.

#### Importance of simulated annealing
Simulated annealing is hill climbing that sometimes accepts a **worse** move. A random neighbour is chosen; if it is better it is accepted; if worse (change ΔE < 0), it is accepted with probability **e^(ΔE/T)**, where T is a "temperature" that is slowly lowered (cooling schedule). At high T the search wanders and **escapes local maxima**; as T falls it behaves like hill climbing and settles on a good solution. With a slow enough cooling it finds the global optimum with probability approaching 1, so it solves the main weakness of hill climbing.

## Check yourself

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

1. Which describes hill climbing?
   A. Complete and optimal, uses much memory
   B. Keeps only the current state (O(1) memory), no backtracking, not complete and not optimal
   C. Complete but not optimal
   D. Uses a queue of all visited states
   Answer: B. Hill climbing is fast and memory-light but can get stuck, so it is neither complete nor optimal. (Key point: Hill climbing properties)

2. Which remedy suits a plateau?
   A. Take a big random jump or allow limited sideways moves
   B. Apply a higher temperature
   C. Use BFS
   D. Remove the evaluation function
   Answer: A. A plateau has no uphill direction, so jumping away or limited sideways moves helps. (Key point: Plateau solution)

3. How does simulated annealing treat a worse move (ΔE < 0)?
   A. Never accepts it
   B. Accepts it with probability e^(ΔE/T)
   C. Always accepts it
   D. Accepts it only when T = 0
   Answer: B. Worse moves are accepted with probability e^(ΔE/T), which allows escape from local maxima. (Key point: Simulated annealing acceptance)

4. What happens as the temperature T is lowered?
   A. The search wanders more
   B. It behaves more like hill climbing and settles on a good solution
   C. It restarts from the beginning
   D. It stops accepting any moves immediately
   Answer: B. High T allows wandering; as T falls, worse moves become unlikely and the search settles. (Key point: Cooling)

## Related in Artificial Intelligence

- [Hill climbing and its problems](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ahill-climbing-problems-solutions) — 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×