A magazine where the digital world meets the real world.
On the web
- Browse by date
- Browse by topic
- Enter the maze
- Get our RSS feed
- Follow us on Twitter
- Resources for teachers
What is cs4fn?
- About us
- Contact us
- Privacy and cookies
- Copyright and contributions
- Links to other fun sites
- Complete our questionnaire and get a free magic download
Getting there in much less time with a little soap or slime
We all like to get around, but what’s the best way? Being able to find the shortest route between a group of train stations, or the least amount of petrol needed to visit twenty different towns are important, but often difficult questions to answer. The classic Travelling Salesman problem – find the shortest route to visit a set of towns, visiting each only once – has kept many a mathematician and computer scientist up late at night. The problem looks simple, but if you try to work out a general way to solve it for any large number of towns you’ll just go berserk. It takes too long to work out the route and no one has yet come up with a way to calculate it that doesn’t seem to take forever!
The long way roundIt’s believed that the first people who started to worry about this were, not surprisingly, travelling salesmen. In 1832 a travelling salesman’s handbook was produced, giving useful tips and preferred routes around towns in Germany and Switzerland, but what about those selling stuff in France or Great Britain? There was no mathematical method given to discover the best way. Finding this shortcut to calculating the route is hard because the problem is so complex that the amount of time you need to solve it, depending on the number of cities, just gets too out of hand. So is there another way?
Physical computing for hard problems
Most of today’s computers use millions of electronic switches to do their calculations, but what if today’s switches aren’t enough? You need a physical computer. Every molecule and every cell in the natural world has rules to follow, so you could think of it as a big computer. The way stuff behaves is like a program we have yet to fully understand. Luckily, we know enough to harness bits of that program to answer questions for us.
One early example of a physical computer solving a tough problem involves a bucket of soapy water. You can try it yourself.
Computing with a little bit of soap
You will need:
- A big bucket
- Washing up liquid
- Two Perspex sheets
- A small blob of ‘poster adhesive putty’ (it may be blue and it may tack onto the wall, we couldn’t say)
Start by a drawing a map of your stations (they could be stations in the real world or ones you made up). To find the shortest route between your train stations take two transparent Perspex sheets and stick them together, sandwiching small, same-size blobs of putty as spacers between the sheets at the positions of the stations given by your mini map. Now stand back and have a look. What you have created is a mini model of the world. All you need is to find the shortest distance joining all the stations, solving that rather tricky computational problem.
And the answer is?
Pour plenty of washing up liquid into the bucket and add water to create a very soapy solution. Froth up that bucket of soapy water and dump the Perspex sandwich in, swish it around gently and pull it out. In front of you is the perfect solution (pun intended). The soap film left will cling to all the spaces in between your stations, connecting them together. The clever bit is that due to the physical process of surface tension, bubble films must always take up the least surface area they can to minimise the physical forces acting on them. This means that your network of soap bubble tracks are as short as they can possibly be. The soap has effectively solved a problem that the poor old on/off electronic switches find so difficult. You’ve done some clever physical computing, so have a break and chill.
Slime the problem
The soap film calculation is only one way to let Nature solve these tough computational problems. Another method recently used involves the rather less pleasant option of slime moulds. You may have seen these in lawns or on dead rotting trees – hey, everyone’s gotta live somehow. For their experiment Japanese scientists got a slime mould, a group of single-celled amoeba-like creatures that go by the rather posh name of Physarum polycephalum, and dripped them onto the centre of a wet glass plate. Around this drop of slime they placed oat flakes at the relative locations of stations on the Tokyo subway, making a sort of edible, high-fibre mini map.
Eat your way to victory
The slime mould was hungry, so it spreads to where the oaty goodness of the food is. As it grew, it organised itself into shapes that looked just like the actual Tokyo subway map. After all, if you need to find the best route to all the available food sources or starve, evolution will have given you the necessary bioskills to do this. The team behind the research developed a mathematical model of the strategy the slime mould used, which they believe can help develop new ways to design computer networks and other useful things. We say, well done slime.
Nature knows best
The behaviour of natural systems like bubbles and slime moulds have been shaped by physical laws or perfected by evolution to solve what we still regard as some really tough computational problems. The soap and the slime are only doing what they do, and we can learn from them in so many useful ways. Today’s computer scientists are always on the lookout for ready-made solutions, and physical computers like these are just some of the exciting techniques they are discovering, but there are plenty more out there!