Кто-нибудь может это грамотно прокомментировать? Я мало что понял, но на видео, вроде бы, найден не самый кратчайший маршрут, а просто "достаточно хороший". В совокупности с заявлениями в духе "никто не понимает, как это она делает" это совсем дурно пахнет.
https://habr.com/post/434236/Пахнет, при чем скверно. Подобные задачи ускоряются следующим способами:
1. Приближенные алгоритмы (локальные минимумы)
2. Вероятностные методы
3. Эвристические методы
4. Распараллеливание (не для NP-трудных задач)
Просто молодые японские ученые закинули преждевременную утку. Для приближенных алгоритмов нет смысла говорить об экспоненциальном росте сложности. Тем более в плане безопасности: приближенный алгоритм не способен подобрать код.
-- 04.01.2019, 22:03 --Из комментов хабра:
Цитата:
Исследователи поместили Physarum polycephalum внутрь чипа, который представляет собой круглую выемку с выходящими из нее 64 узкими каналами. Внутри выемки и в каналах находится питательное вещество, и слизевик старается проникнуть в них, чтобы максимизировать поступление в клетку питательных веществ.
Каждый из восьми городов (A, B, C и другие) в задаче представлен восемью каналами с порядковыми номерами, показывающими, каким по счету может быть город при посещении коммивояжером. Когда слизевик проникает в город A с номером 3, во всех остальных каналах с тем же номером (B3, С3) загорается свет, отпугивающий слизевика. Таким образом, предотвращается одновременное посещение городов. Кроме того, в компьютер, управляющий светом, заложена информация о расстоянии между городами. Если слизевик после посещения города А начинает проникать в каналы В и С, но при этом С находится от А ближе, чем В, то в последнем также загорается свет, отпугивающий плазмоид. Так достигается выбор оптимального маршрута.
-- 04.01.2019, 22:15 --Насчет распараллеливания: обычно считается, что количество процессоров (ядер) есть величина постоянная. Однако в случае амебы идет речь о слизи, которая по сути является агентом амебы. И похоже распараллеливание не особо ограничено. Буду смеяться над японцами, если амеба распараллеливает вычисления. Это значит технически их алгоритм не изящен.
