Суть задачи на первый взгляд проста: представьте, что вы — путешествующий от города к городу продавец, предлагающий свои товары. Вы стремитесь максимально увеличить свою эффективность, чтобы заработать как можно больше денег.
Поэтому продавцу нужно найти кратчайший маршрут, который позволил бы вам добираться от одной точки к другой. Для этого нужно рассчитать длину каждого из возможных маршрутов и выбрать из них самый короткий.
Сложность заключается в том, что добавлением новых городов на этот маршрут сложность вычислений возрастает экспоненциально. Например, для четырех городов нужно построить всего три маршрута, а для десяти — более миллиона.
Японские ученые использовали для решения простейшее одноклеточное существо Physarum polycephalum, которое всего лишь умеет двигаться в сторону еды и прятаться от света. Амебу поместили в камеру, состоящую из каналов, в конце каждого было немного еды.
Существо инстинктивно вытягивало жгутики в сторону
конкретного канала, после чего срабатывала сигнализация, отключающая свет. При этом
чем дальше канал находится от текущей точки, тем чаще в нем гаснет свет.
Амеба реагирует на все изменения пассивно и вынуждено выбирает самый выгодный маршрут. В результате можно увеличивать количество каналов-городов бесконечно, однако время достижения конечного результата остается оптимальным.
Как отмечают исследователи, простейший организм решил задачу быстрее любого современного компьютера. В перспективе новый подход поможет пересмотреть современные алгоритмы вычислений.