January 5th, 2019

Живая слизь удивила учёных способностью к математике

Японские ученые открыли способность организма слизевик физарум многоголовый решать математическую задачу – так называемую задачу коммивояжера. При этом механизм, который помогает слизи делать это, остается загадкой. Статья с описанием экспериментов и выводов опубликована в журнале Royal Society Open Science.

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

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

Для такого класса задач (NP-трудные задачи) находят приближенное решение с необходимой точностью. В нынешней работе указано, что одноклеточный организм способен воспроизводить это приближенное решение.

Collapse )