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

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

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

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

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

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

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

Подпишитесь на наши новости
Лого www.SiteHere.ru
1970-01-01 03:00 http://news.xtipe.com/ru/news/33355

Смотрите так же

Airbus Helicopters провел первые летные испытания беспилотного вертолета 1970-01-01 03:00

Европейский консорциум Airbus Helicopters провел первые летные испытания беспилотного разведывательного вертолета VSR700. При этом впервые испытания проходили без пилота в кабине, говорится в сообщении компании.

Гипотеза: внутрикластерный свет позволит точно определить расположение темной материи 1970-01-01 03:00

Астрономы нашли новый способ идентификации темной материи — на ее наличие прямо указывает звездный свет, который задерживается между массивными скоплениями галактик. Этот метод точнее, чем традиционные способы картирования темной материи, пишет ScienceAlert.

Астероид Ультима Туле в поясе Койпера всегда светит одинаково ярко. И это очень странно! 1970-01-01 03:00

Астрономы из миссии New Horizons («Новые горизонты») обнаружили у астероида Ультима Туле (2014 MU69) странную особенность — интенсивность свечения космического тела не меняется при его вращении. Такой вывод ученые сделали в ходе анализа фотографий, присланных зондом, говорится в сообщении университета Джона Гопкинса.

Российский 3D-биопринтер напечатал на МКС 12 органов и тканей 1970-01-01 03:00

Российская компания 3D Bioprinting Solutions напечатала на установленном на МКС 3D-биопринтере шесть человеческих хрящей и шесть щитовидных желез мыши. Об этом пишет «РИА Новости» со ссылкой на сообщение компании.

Геологи: накопление холодной воды на дне океанов привело к ледниковым периодам, длившимся почти 2 млн лет 1970-01-01 03:00

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