AI · Theory

Hill Climbing

Theory

23/215

Hill Climbing

Hill climbing looks only at neighbours and steps to a better one. Like climbing in fog: you go up, then you stop at a peak that may not be the highest mountain. Local maxima, plateaus, ridges trap it. Variants: random restart, simulated annealing.

8-queens or a tiny landscape sketch is enough. Don’t claim hill climbing always finds global best. It is greedy local search, not A*.

Hill Climbing — output — stopped at index 1 height 5. Global peak is 9. Local maximum trap.

Exam tip

Local max trap + one fix.

Example

# Hill climb — may miss global peak
height = [2, 5, 4, 9, 8]
i = 0
while i + 1 < len(height) and height[i + 1] > height[i]:
    i += 1
print("stopped at index", i, "height", height[i])

Hill Climbing — output: stopped at index 1 height 5. Global peak is 9. Local maximum trap.

Short notes

DefStep to better neighbour.
TrapLocal maximum.
Fix : random restart.

AI · Theory

Hill Climbing

← All stacks

Theory

23/215

Hill Climbing

8-queens or a tiny landscape sketch is enough. Don’t claim hill climbing always finds global best. It is greedy local search, not A*.

Hill Climbing — output — stopped at index 1 height 5. Global peak is 9. Local maximum trap.

Exam tip

Local max trap + one fix.

Example

# Hill climb — may miss global peak
height = [2, 5, 4, 9, 8]
i = 0
while i + 1 < len(height) and height[i + 1] > height[i]:
    i += 1
print("stopped at index", i, "height", height[i])

Hill Climbing — output: stopped at index 1 height 5. Global peak is 9. Local maximum trap.

Short notes

DefStep to better neighbour.
TrapLocal maximum.
Fix : random restart.

Hill Climbing

Example

Short notes

Questions

Hill Climbing

Example

Short notes

Questions