рейтинг блогов

слизь

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

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

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

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





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

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

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

via
via

слизь слизь слизь слизь

Оставить комментарий

Предыдущие записи блогера :
Архив записей в блогах:
сегодня, перемещаясь в городе, сделал небольшой крюк прошелся по переулкам-улочкам, на которых прошло мое децтво какбэ знаю, шо у меня присутствуют любители вертуальных гуляний по Киеву для них и ага свет и скорость бега (а также лень) - отмазки по ...
Возможно, кто-то помнит мои отзывы на сказки Марии Заболотской "Милость крестной феи" и "Красавица, чудовище и волшебник без лицензии". https://author.today/u/popovana/reviews Кто-то даже прочитал их по моей наводке, и им даже понравилось. У Марии сейчас очень сложная ситуация - ...
Главные персонажи фильма "Алиса в стране чудес" (Бертона) в полном гриме ...
 Вчера вечером раздаётся неожиданный звонок в дверь. Открываю - стоит ...
Из книжки Толстого Буратино с иллюстрациями Владимирского: Лиса объяснила, что опасный воришка-Буратино обнаружен на пустыре. Дежурный, все еще рыча, позвонил. Ворвались два добермана-пинчера, сыщики, которые никогда не спали, никому не верили и даже самих себя подозревали в ...