Climbing hills

Roger Boyle of the University of Leeds takes us exploring in the mist of a thought experiment.

You’re in the Scottish highlands and you’re climbing a peak, when the mist comes down. Can you still climb the peak?

Theoretically you can, so let’s overlook the issues of hidden crevasses and lurking wolves. Even if the visibility is zero you are able to sense which way is ‘up’ or ‘down’. If you persistently go up, you don’t actually need to see the destination … you’ll reach a summit, won’t you? Actually, you can be quite smart about this and distinguish between ‘gentle up’ and ‘steep up’, perhaps by just moving one pace in each direction – then taking the steepest route may well get you there quicker. It would be pretty dangerous to try getting up a real mountain without being able to see, but what if you just imagine that any big problem is a mountain to climb? Then this thinking becomes really useful.

Suppose now you have the apples and oranges franchise at Glastonbury Festival. You are given a wheelbarrow that can hold up to 300 apples or 250 oranges, and access to a warehouse with an infinite supply of both. You wheel the barrow through the happy crowds and sell apples at 15p each, oranges at 18p. Profit on an apple is 2.3p, and on an orange 4.1p. The lighter the barrow, the faster you move. The longer you’re away from base, the more chance you run into a friend and decide to spend some of your earnings. And the longer you’re away from base, the more chance the unscrupulous will pilfer some fruit. Pilferers are more likely to steal whatever is in shortest supply on the barrow. Phew – this scenario is getting complex quickly.

The question is, what’s the best number of apples and oranges to load every time you are at base in order to maximise the profit of each outing through the crowd? Of course you can’t see into the future – future-gazing is a bit like peering into a thick fog. Clairvoyance aside, how can you solve the problem?

This sort of problem is very common in the real world of computing – it’s called an ‘optimisation’ problem. If you load the barrow with M apples and N oranges (where M and N are just placeholders for the particular numbers we pick for an outing), you want the value of (M,N) that returns the highest profit. At the outset you have no idea of the best answer, so let’s guess. Go on an outing with 100 apples and 120 oranges, and let’s suppose the profit is some number that we will call: P(100,120). Time is on your hands, so now go on outings with (99,120) – that is 99 apples and 120 oranges, (101,120), (100,119) and (100,121) apple-orange loads. Maybe the profits exceed P(100,120) and maybe they don’t. If you do find a more profitable load, this gives a good clue at how to best adjust the loading.

If you make more profit with an extra orange (eg (100,121) ) then you should go for more oranges on future trips, trying a run like (100,122) next. You can then compare its profits to the earlier trips and keep taking a step in the direction of the most profits for each new outing.

Trying to find the answer to the barrow problem is like trying to find your way up that Highland mountain. We are somewhere in ‘apple-orange land’. We feel around the closest territory sensing which direction is useful, or best. We go that way and then do some more sensing. Each step we take might be in a different direction left or right, but if our senses are right we’ll keep getting closer to the top of the mountain, where the answer lies. And one of the nice things about hill-climbing in computer science is that there’s no chance of ending up being helicoptered away with a broken leg.