Definition
Hill-Climbing
Hill-climbing is a greedy search strategy that tries to maximise/minimise a local value.
“Like climbing mount everest in thick fog with amnesia”.
Since hill-climbing only focuses on local/relative values, it can easily become stuck in a local maximum/minimum rather than aiming for the global maximum/minimum.
Remedies:
- Random-restart hill-climbing: restart after step limit overcomes local maxima
- Simulated annealing: allowing some “bad” moves
Pseudo Code
function HILL-CLIMBING(problem) returns a state that is a local maximum
current problem.INITIAL
while true do
neighbour a highest-valued successor state of current
if VALUE(neighbour) VALUE(current) then return current
current neighbour