Японские ученые открыли способность организма слизевик физарум многоголовый решать математическую задачу – так называемую задачу коммивояжера. При этом механизм, который помогает слизи делать это, остается загадкой. Статья с описанием экспериментов и выводов опубликована в журнале Royal Society Open Science.
Задача коммивояжера – самая известная из класса задач по поиску маршрута. В популярной трактовке она заключается в следующем: коммивояжер должен пройти по всем городам маршрута таким образом, чтобы посетить каждый город только один раз, чтобы весь маршрут занял минимальное время, и чтобы вернуться в начало.
В общем случае задача не имеет точного решения, которое можно найти за приемлемое время (это положение не доказано, но большинство математиков считают его истинным). Перебор вариантов при достаточно большом количестве городов невозможен даже на современных суперкомьютерах и тех, что появятся в перспективе. Потому что с каждым новым городом количество вариантов растет по экспоненте.
Для такого класса задач (NP-трудные задачи) находят приближенное решение с необходимой точностью. В нынешней работе указано, что одноклеточный организм способен воспроизводить это приближенное решение.
Слизь поместили в чип, созданный в виде круглой выемки с 64 выходящими каналами (в примере задача решена для восьми городов – по восемь каналов на каждый город). Внутри каждого элемента находится питательное вещество. Организм пытается попасть в каналы, чтобы получить питательные вещества. Чтобы смоделировать задачу, ученые зажигают в определенных каналах свет, который отпугивает слизь. В итоге компьютер и организм решают задачу за линейное время, поскольку слизевик потребляет желатин для роста и растет с постоянной скоростью.
Ученые пока не могут понять, как слизевик делает это. Они предполагают, что клетки синхронизируются друг с другом, обмениваясь информацией. Это решение позволяет задуматься о создании аналоговых компьютеров, вычислительная мощность которых будет значительно выше, чем цифровых в современной концепции.
Подробнее в сюжете: Мир науки