Дмитрий Чернышев (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 

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