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

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

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

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

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

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

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

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

Источник: m.vk.com

Комментарии: