Sign In

Communications of the ACM

ACM TechNews

Shrinking Blob Speeds Traveling Salesman on His Way


View as: Print Mobile App Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
A representation of a solution to the Traveling Salesman Problem.

The traveling salesman problem is solved when the salesman travels through each of n cities while covering the least total distance. There is no known general method for finding the solution.

Credit: Wolfram Mathworld

University of the West of England computer scientists Jeff Jones and Andrew Adamatzky have discovered that a virtual shrinking blob might help find a solution to the renowned traveling salesman quandary.

The problem asks for the shortest route that a traveling salesman could take to reach specified cities in a tour, stopping only once at each city before returning to the starting point. Numerous algorithms have been developed to determine solutions to the problem, but no ideal algorithm has been written.

Jones and Adamatzky created an algorithm based on the concept of the slime mold, a single-celled organism that stretches its body toward nutrients to engulf them. Their approach places a virtual blob comprised of individual particles inside a lattice with virtual cities. A chemoattractant is projected near the cities, and particles are programmed to move toward the area with the highest chemoattractant concentration. The particles leave a trace of chemoattractant that other particles follow, causing the entire blob to shrink to the smallest possible surface area while still touching all cities.

In various tests based on 20 cities, the blob's final circumference created a route map providing a reasonable solution to the traveling salesman problem.


From Phys.Org
View Full Article

 

Abstracts Copyright © 2013 Information Inc., Bethesda, Maryland, USA


 

No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account