If you’ve spent any time hillwalking at all you’ll be
familiar with the “false summit effect”. From afar you
can tell where the top of the mountain is, but as you get onto the
slope itself your view is occluded. You fix your sights on a little
hill just in front of you that blocks your view of everything else.
But just as you reach this summit, you find that there’s more
to come. And in the worst case, you might have to go back down from
the mini-summit you’re on to reach the slopes of the higher
part of the hill.
That is the false summit.
Searching for things in computer science is often likened to
climbing a hill, where the summit represents the goal, and every
point on the landscape represents a candidate for this goal. The
idea is that, without knowing where the summit is, one can get
there by always walking up hill. Assuming an ideal
(smooth) landscape one could get to the top of a hill blindfold.
(Not recommended.)
The flaw, which I’m sure you’ll have spotted, is the
false summit. If we can’t see where we’re going then we
can never be totally sure if we’re on a minor summit rather
than the very top of the mountain. This is called a
local maximum—every direction you walk goes
down, but there is a direction which will eventually take you to a
taller peak.
The solution is to add a bit of randomness. If you’re at the
top and don’t know where to go, spin round in circles until
you’re dizzy and then strike out in the direction you end up
facing. (I don’t suggest you do this literally either.
I’m not going to be responsible for dizzy people hurling
themselves off hillsides.) With a bit of randomness added to the
search pattern you can break out of the local maxima.
Of course, this is one of those circumstances where you can never
be totally sure you’re at the summit. Though if all
you’re looking for is a hill high enough then it
will fit the bill adequately.
Photograph credit goes to Christof Autengruber on Flickr.