Forget GPS. With no fancy maps or even brains, immune system cells can solve a simple version of the traveling salesman problem, a computational conundrum that has vexed mathematicians for decades.
The new research, which simulates how a type of white blood cell seeks and destroys infectious particles, shows how living things — be they cells, sharks or bees — successfully find a target, with only limited information and even more limited cognitive skills.
“Some search strategies are perhaps not the best, but they make the whole exploration of a space very efficient,” says theoretical ecologist Frederic Bartumeus of the Spanish Council for Scientific Research’s Centre for Advanced Studies of Blanes.
While some of the best mathematical minds have been tackling the traveling salesman problem for decades and some have found efficient solutions, no one has figured out how to completely solve the puzzle: For a given number of cities, a traveling salesman must plan a route that visits each city once, covering the minimum possible overall distance. A pencil and paper and brute force can find the shortest route when there aren’t a lot of target cities. But fancy algorithms and serious computing power are usually needed when the number of targets reaches mere double digits. The new research, to appear in an upcoming Physical Review E, shows that when there aren’t a lot of targets, cells do a pretty good job of finding the shortest possible route that hits all the targets. These cells “search” by tuning into local concentrations of chemical signals and following the signals to the nearest target. Repeating that process allows immune cells to find and demolish numerous invaders.