Слизь решила математическую задачу лучше, чем суперкомпьютеры

Японские ученые открыли способность слизевика (физарума многоголового) решать математическую задачу – так называемую задачу коммивояжера. При этом механизм, который помогает слизи делать это, остается загадкой. Статья об этом опубликована в журнале Royal Society Open Science.

Задача коммивояжера – самая известная из класса задач по поиску маршрута. В популярной трактовке она заключается в следующем: коммивояжер должен пройти по всем городам маршрута таким образом, чтобы посетить каждый город только один раз, чтобы весь маршрут занял минимальное время, и чтобы вернуться в начало.

Слизевики и раньше удивляли ученых. К примеру, вот они успешно находят еду в лабиринте

При большом количестве городов задача не может быть решенапутем простого перебора любыми компьютерами даже за миллиарды лет, так как число маршрутов с числом городов растет экспоненциально. Например, в случае четырех городов существует три возможных маршрута, а в случае восьми — уже 2520.

Для такого класса задач (NP-трудные задачи) находят приближенное решение с необходимой точностью. В нынешней работе указано, что одноклеточный организм способен воспроизводить это приближенное решение.

Слизь поместили в чип, созданный в виде круглой выемки с 64 выходящими каналами (в примере задача решена для восьми городов – по восемь каналов на каждый город). Внутри каждого элемента находится питательное вещество, а организм пытается попасть в каналы, чтобы получить вкусный приз.

Эксперимент в процессе
Эксперимент в процессе

Чтобы смоделировать задачу, ученые зажигают в определенных каналах свет, который отпугивает слизь. В итоге компьютер и организм решают задачу за линейное время, поскольку слизевик потребляет желатин для роста и растет с постоянной скоростью.

Слизевики иногда принимают за грибы, но их точная классификация ещё не разработана
Слизевики иногда принимают за грибы, но их точная классификация ещё не разработана

Ученые пока не могут понять, как слизевик делает это. Они предполагают, что клетки синхронизируются друг с другом, обмениваясь информацией. Это решение позволяет задуматься о создании аналоговых компьютеров, вычислительная мощность которых будет значительно выше, чем цифровых в современной концепции.