Amoeba Solves the TSP

A classic, iconic problem, often mentioned in analytics texts.   Often use as a classic optimization problem that gets very hard, very fast for digital computers to solve.   Here an analog solution by primitive animals.

Amoeba Solves the TSP    By Fiona MacDonald in Sciencealert

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 their results "may lead to the development of novel analog computers enabling approximate solutions of complex optimization problems in linear time." ..."