Японские инженеры научили амебу Physarum polycephalum (или «многоголовую слизь») решать проблему коммивояжера — классическую вычислительную задачу, которая позволяет оптимизировать маршрут между точками на карте, посещая каждую из них только один раз. Одноклеточное решило проблему совершенно новым способом — это значит, что современным электронным устройствам есть, чему поучиться у амебы, пишет ScienceAlert.
Задача коммивояжера — одна из самых распространенных оптимизационных задач. Решающему ее алгоритму необходимо найти оптимальный маршрут между городами, проходящий через каждый из них как минимум по одному разу, с возвратом в исходный город. При постановке задачи указываются критерии маршрута — кратчайший, самый выгодный с точки зрения денег, совокупный критерий и другие. Сложность задачи растет экспоненциально: например, в списке из четырех городов можно составить три возможных маршрута, из восьми — уже 2 520 маршрутов.
Решением задачи занималась амеба Physarum polycephalum или «многоголовая слизь» — одноклеточное, которое обитает в тенистых и влажных местах. Например, в гниющих листьях и деревьях.
Исследователи из Университета Кейо в Японии поставили задачу коммивояжера амебе в простейшем виде, и ей удалось справиться. Тогда ученые усложнили задачу и обнаружили, что при экспоненциальном росте сложности время на решение у амебы увеличивается линейно.
Другими словами, из-за усложнения задачи качество ее решения не упало — амебе просто потребовалось больше времени. Исследователи отмечают, что одноклеточное решило задачу совершенно новым способом — и сделало это эффективнее компьютера.
Вот как амеба решала задачу: