Communications of the ACM
Shrinking Blob Speeds Traveling Salesman on His Way
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