Дмитрий Чернышев (mi3ch) wrote,
Дмитрий Чернышев
mi3ch

слизь


Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600 вариантов

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

Сложность вычисления правильного решения возрастает экспоненциально, чем больше городов добавляется к задаче. Например, для четырёх городов есть три варианта решения, а для шести городов — 360. Если есть маршрут с десятью или более городами, количество возможных маршрутов исчисляется миллионами.

Группа японских исследователей из Университета Кейо в Токио продемонстрировала, что такие сложные задачи может решать простейшая амёба. За миллионы лет эволюции слизь Physarum polycephalum научилась делать две вещи: двигаться к еде и избегать света





Чтобы превратить этот естественный механизм питания в компьютер, японские исследователи поместили амёбу на специальную пластину с 64 каналами, в направлении которых животное могло вытягивать тело. Амёба постоянно пытается расширить тело, чтобы покрыть как можно большую площадь пластины с питательным веществом. Тем не менее, каждый канал в пластине можно осветить, что заставляет амебу из чувства отвращения к свету убраться из этого канала.

Для программирования амёбы исследователи использовали нейронную сеть, которая включала данные о текущем положении амебы и расстоянии между городами, чтобы осветить определённые каналы. Нейронная сеть была обучена с большей вероятностью освещать города (каналы) с бóльшими расстояниями между ними.

При взаимодействии алгоритма и амёбы последняя принимает форму, которая представляет приблизительные решения задачи коммивояжера. Самое интересное, что количество времени, которое требуется амёбе для получения этих почти оптимальных решений, растёт линейно, хотя количество вариантов решения увеличивается экспоненциально. Таким образом амеба может решать подобные задачи лучше любого компьютерного алгоритма

via
via

Tags: животные, технологии
Subscribe

Posts from This Journal “животные” Tag

  • бровки домиком

    Десятки тысяч лет одомашнивания привели к тому, что у собак появились мышцы, которые практически не развиты у волков. Мимика собак гораздо богаче.…

  • ящер

    Аризонский ядозуб. Интересно, что «пупырышки» на голове – это не кожа, а череп

  • с собаками вход запрещен

    Юдхиштхира, герой «Махабхараты», старший из братьев-Пандавов, в конце своей жизни отрекается от трона и вместе со своими братьями отправляется в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 52 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →