You are viewing brokenhut

The Broken Hut
Working my way up to a full-size building
Hill-climbing as a search technique 
16th-Oct-2007 11:35 pm

Photograph of hills

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.

Comments 
17th-Oct-2007 06:43 am (UTC)
Very nice.

And true of many other things in life, not only computer science....
This page was loaded Jul 24th 2014, 3:52 pm GMT.