Virtual goo provides solutions to “traveling salesman problem”

MIT Technology Review : The traveling salesman problem seeks to determine the shortest possible route that passes through a given number of cities and returns to the starting point without visiting the same city twice. The brute-force method for determining the shortest path is extremely challenging and even computationally impossible for very large numbers of points. Most computer algorithms for solving the problem therefore look for “good enough” solutions that can be found in reasonable amounts of time. Jeff Jones and Andrew Adamatzky of the University of the West of England have instead developed a nonalgorithmic method that uses a virtual goo. They created a virtual petri dish, with pegs representing cities, and added a blob of virtual particles governed by a few simple behavioral rules. The resulting configuration exhibited emergent behavior, such as shrinking to minimize its surface area, much like a soap bubble does. Because the blob of goo clings to the pegs, it adapts to their arrangement such that the path the surface of the goo makes between each pair of pegs is the shortest possible. Jones and Adamatzky found that, if the shortest possible path connecting all the pegs was defined as length 1, then their goo produced mean average paths of length 1.07. Although the method is not exceptional compared to already known algorithms, its simplicity raises new avenues for approaching the problem.