Google Play icon

Shrinking blob speeds traveling salesman on his way

Share
Posted March 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]

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.

Read more at: Phys.org

Featured news from related categories:

Technology Org App
Google Play icon
85,462 science & technology articles

Most Popular Articles

  1. New treatment may reverse celiac disease (October 22, 2019)
  2. "Helical Engine" Proposed by NASA Engineer could Reach 99% the Speed of Light. But could it, really? (October 17, 2019)
  3. New Class of Painkillers Offers all the Benefits of Opioids, Minus the Side Effects and Addictiveness (October 16, 2019)
  4. The World's Energy Storage Powerhouse (November 1, 2019)
  5. Plastic waste may be headed for the microwave (October 18, 2019)

Follow us

Facebook   Twitter   Pinterest   Tumblr   RSS   Newsletter via Email