Shrinking blob speeds traveling salesman on his way
PostedMarch 27, 2013
Foraging plasmodium of Physarum does not approximate the Travelling Salesman Problem in both unconstrained and constrained environments. Credit: arXiv:1303.4969 [cs.ET]
What is the shortest route that a traveling salesman must take to visit a number of specified cities in a tour, stopping at each city once and only once before returning to the starting point? The most accurate way to answer this question is to measure every possible route, then determine which one is shortest. However, this method becomes unfeasible when there are too many cities on the salesman’s tour. Jeff Jones and Andrew Adamatzky of the University of the West of England have discovered that they can use a virtual shrinking blob to find a reasonable solution.
The traveling salesman problem is a frequently studied mathematical problem. Mathematicians have developed many algorithms that provide reasonably good solutions; however, they tend to agree that no algorithm will solve the problem perfectly every time.