Photo: Popular Mechanics |
A group of researchers from Tokyo’s Keio University set out to use an amoeba to solve the Traveling Salesman Problem, a famous problem in computer science.
The problem works like this: imagine you’re a traveling salesman flying
from city to city selling your wares. You’re concerned about maximizing
your efficiency to make as much money as possible, so you want to find
the shortest path that will let you hit every city on your route.
There’s
no simple mathematical formula to find the most efficient route for our
salesman. Instead, the only way to solve the problem is to calculate
the length of each route and see which one is the shortest.
What’s worse, performing this calculation gets exponentially harder the
more cities are added to the route. With four cities, there are only
three different routes to consider. But with six cities, there are 360
different routes that need to be calculated. If you’ve got a route with
ten or more cities the number of possible routes is in the millions.
This makes the traveling salesman problem one of a broad class of problems computer scientists call ‘NP hard.’...
This makes the traveling salesman problem one of a broad class of problems computer scientists call ‘NP hard.’...
But if the researchers can figure out just how the
amoeba works, they can use this trick for more than just helping out
traveling salesmen. It could speed up our ability to solve all kinds of
difficult computational problems and change the way we approach
security.
This one small amoeba—and the way it solves difficult problems—might just change the face of computing forever.
Source: Popular Mechanics