Communications of the ACM
An Amoeba Just Found an Entirely New Way to Solve a Classic Computing Problem
Researchers at Keio University in Japan gave the Traveling Salesman Problem to a "true slime mold" amoeba, which found a solution.
Credit: Masashi Aono/Keio University
Researchers at Keio University in Japan gave the Traveling Salesman Problem (TPS) to a "true slime mold" amoeba, and found as the cities increased from four to eight, the single-celled organism only needed a linear amount of more time to determine a single reasonable route.
TPS is an optimization problem requiring a computer to look at a list of cities and determine the shortest route in which each city is visited exactly once.
In this experiment, the "cities" were 64 narrow channels—eight "cities" each containing eight channels—in a round plate placed on top of agar.
The researchers ensured the amoeba entered the "cities" in an optimal way, using light to illuminate certain channels that were too far apart or which it had already visited, and to stop it from entering several channels simultaneously.
The team said its results "may lead to the development of novel analogue computers enabling approximate solutions of complex optimization problems in linear time."
From ScienceAlert
View Full Article
Abstracts Copyright © 2018 Information Inc., Bethesda, Maryland, USA
No entries found