Friday, November 20, 2009

Can we use a computer from Nature to attack the Traveling Salesman Problem?


The traveling salesman problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem) tries to find the shortest route covering all points in a plane.


If all points are on a circle, it seems that the shortest route passes from point to point in the order that they are on the circle. Of course, not following the curve, but the straight line between two adjacent cities on the curve.

So I wondered if a general solution would be to find the circle that is a best fit for all points, and then travel along the circle picking the next point to visit - from the previous one.

How about a system from Nature that can simultaneously compute this?

Have a circular coil of wire on a sheet of plastic. The diameter should be in the approximate range of the points. The points are represented by small powerful permanent magnets each with a electromagnetic coil and a bulb - or an ammeter to measure current. The magnets are positioned in a vessel of water, and in the same relative coordinates as in the real world problem.

The sheet of plastic floats over the magnets below. Passing an electric current through the coil moves the floating sheet around and produces a best-fit position for the circle.

Now anchor the sheet so the coil does not move.

Now have a magnet travel around the track, the dog, at relatively high speed. It starts closest to the origin point. Mark this. A current is generated in each coil. The bulb that lights up first - the sensor that picks up the strongest reading - is the point to move next to. And so on.

Of course, you can do this in sophisticated ways, but this is all I know, and is easy to explain to a high school kid. The idea is to use a Natural computer.

(background: I wrote a toy program to solve the Robot Tour Optimization exercise problem in Steven Skiena's book, "The Algorithm Design Manual" and got this idea).