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

слизь

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

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

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

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





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

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

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

via
via

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

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

Предыдущие записи блогера :
Архив записей в блогах:
Мовсура Хасаева обвиняли в убийстве по найму одного из лидеров свердловской армянской диаспоры 22-летнего бизнесмена Ашота Арутюняна и покушении на убийство свидетелей Л. и П. с целью сокрытия убийства Аратюняна, а также в незаконном приобретении, хранении и ношении огнестрельного ...
На прошлой неделе очень многих возбудил беспримерный по длительности и торжественности визит Си Цзиньпина в Великобританию. Сама королева катала Си в своей королевской карете и чуть ли не лично утверждала меню праздничного стола, а Кейт Мидлтон щеголяла в платье цветов китайского флага. Т ...
Что было достаточно предсказуемо изначально, если когда традиционно послушным распоряжениям администраций гражданам Израиля навешивали лапшу о том, что "после всеобщей вакцинации они вернутся к обычной жизни" Хрен вам, а не возвращение к обычной жизни после покорного принятия требуемых ...
Выложу-ка я первые наброски - если не с натуры, так по очень свежей памяти. Пока хозяйский вайфай посрамляет мой питерский интернет... Это утренний вид с моего балкона. Сядешь так с чашечкой кофе и сигареткой, а кругом скворцы безумствует. И хоть зубами стучишь - не жалко. Пара ...
«Role Play» — это кино про то, как сохранить семью. Если ваша семейная жизнь стремится к разводу, то надо кое-что поменять. Например, «профессию» жены. Интересный фильм для просмотра парой. Читать обзор ...