Одноклеточное решило математическую задачу

Исследователи продемонстрировали, что амеба — одноклеточный организм, состоящий в основном из гелеобразной протоплазмы, — обладает уникальными вычислительными способностями.

Исследователи из Университета Кейо предложили амебе решить задачу коммивояжера. Это известная задача на оптимизацию, в которой нужно найти кратчайший маршрут между несколькими городами так, чтобы посетить каждый город один раз и вернуться в начальную точку.

Эта задача является NP-полной — с ростом числа городов время, необходимое компьютеру для решения, растет в геометрической прогрессии из-за большего количества вариантов. Например, для четырех городов есть только три возможных маршрута, но для восьми городов число возможных маршрутов увеличивается до 2520.

Ученые изучали амебу Physarum polycephalum («Физарум многоголовый», или «настоящая слизистая плесень»).

Ее поместили в центр «чипа» — специальной круглой пластины с 64 узкими каналами — поверх пластины с питательным агаром. Амеба могла двигаться в разных направлениях, образуя придатки-ложноножки. Закрывая собой каждый канал, она поглощала вещество из него.

Амеба не любит свет. Как только она «съедала» агар из одного канала, ученые подсвечивали его, чтобы амеба больше туда не вернулась. Кроме того, подсветку сконструировали так, чтобы одноклеточное не могло попасть в два канала одновременно. Таким образом амебе пришлось решать задачу: найти оптимальный маршрут по каналам, заходя в них по очереди.

Амеба справилась. Оказалось, что одноклеточное может найти разумное (почти оптимальное) решение для этой задачи. Интересно, что время, необходимое для решения, при увеличении количества городов от четырех до восьми росло линейно.

«Хотя обычные компьютеры также могут находить приближенные решения за линейное время, подход амебы полностью отличается от традиционных алгоритмов, — пишут ученые. — Амеба исследует пространство раствора, непрерывно перераспределяя гель в аморфном теле. Она делает это с постоянной скоростью и обрабатывает визуальные данные параллельно, а не последовательно».

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

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