Why heuristics? Hill-climbing and the local-maximum trap

What a heuristic is

A heuristic is an informed rule of thumb — a cheap estimate of how close a state is to a goal — used to steer search toward the promising parts of a space. The word is from the Greek eurisco, "I discover." Heuristics are fallible: they can lead to a worse-than-optimal answer or miss a solution entirely, and that limitation cannot be engineered away.

There are exactly two situations where you reach for a heuristic:

1. No exact algorithm exists because the problem is inherently ambiguous — medical diagnosis, interpreting a noisy image. There is no formula that is guaranteed right.
2. An exact algorithm exists but is too expensive — the state space is combinatorially huge (chess, the 15-puzzle). Exhaustive search is correct in principle but would never finish.

Hill-climbing: the simplest heuristic search

Hill-climbing keeps no history at all. From the current state it generates the children, evaluates each with the heuristic, moves to the single best child, and discards everything else — the siblings and the parent. It then repeats. It is fast and uses almost no memory.

That discard-everything policy is its fatal flaw: with no record of where it has been, hill-climbing cannot back up. If it reaches a state that looks better than all of its neighbours but is not the global best — a local maximum — it has no move that improves the score and simply stops, stranded on a foothill below the summit.

Worked example: a one-dimensional landscape

Give each integer position $x$ a value $f(x)$. Picture two hills: a small one peaking at $x=2$ ($f=5$) and the true summit at $x=9$ ($f=12$), with a valley between them.

• Start at $x=0$. Each step compares $f(x-1)$ and $f(x+1)$ and walks to the higher neighbour. Climbing $0\to 1\to 2$, then $f(3)=4<f(2)=5$, so no neighbour improves — hill-climbing halts at the local maximum $x=2$.
• Start at $x=8$. The uphill path leads straight to $x=9$, the global maximum.

Same algorithm, same landscape — the starting point decides whether you find the real peak. That is the local-maximum trap, and it is exactly why richer searches (best-first, next lesson) keep all generated states so they can recover from a bad heuristic choice.