Амеба по прозвищу «многоголовая слизь» решила классическую вычислительную задачу новым способом
21 декабря 2018

Амеба по прозвищу «многоголовая слизь» решила классическую вычислительную задачу новым способом

Японские инженеры научили амебу Physarum polycephalum (или «многоголовую слизь») решать проблему коммивояжера — классическую вычислительную задачу, которая позволяет оптимизировать маршрут между точками на карте, посещая каждую из них только один раз. Одноклеточное решило проблему совершенно новым способом — это значит, что современным электронным устройствам есть, чему поучиться у амебы, пишет ScienceAlert.

Задача коммивояжера — одна из самых распространенных оптимизационных задач. Решающему ее алгоритму необходимо найти оптимальный маршрут между городами, проходящий через каждый из них как минимум по одному разу, с возвратом в исходный город. При постановке задачи указываются критерии маршрута — кратчайший, самый выгодный с точки зрения денег, совокупный критерий и другие. Сложность задачи растет экспоненциально: например, в списке из четырех городов можно составить три возможных маршрута, из восьми — уже 2 520 маршрутов.

Решением задачи занималась амеба Physarum polycephalum или «многоголовая слизь» — одноклеточное, которое обитает в тенистых и влажных местах. Например, в гниющих листьях и деревьях.

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

Другими словами, из-за усложнения задачи качество ее решения не упало — амебе просто потребовалось больше времени. Исследователи отмечают, что одноклеточное решило задачу совершенно новым способом — и сделало это эффективнее компьютера.

Вот как амеба решала задачу: