Monday, March 25, 2013

Shrinking Blob Computes Travelling Salesman Solutions

Shrinking Blob Computes Travelling Salesman Solutions:  In simplified terms, the blob clings to the dots as it shrinks, linking them with a minimal surface, rather like a soap bubble surface. “As the blob shrinks it morphologically adapts to the configuration of the cities,” they say...

The magic ingredient in all this is the special goo. It consists of many particles that each move according to a set of simple rules, like autonomous agents. These sit in a sea of “chemoattractant”, a virtual scent that the particles are attracted to.  At each stage in the calculation, each particle senses the chemoattractant around it and then moves towards the region of highest concentration. As it moves, it leaves behind its own trace of the chemoattractant for other particles to follow.

No comments:

Post a Comment