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

слизь

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

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

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

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





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

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

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

via
via

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

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

Предыдущие записи блогера :
Архив записей в блогах:
Документ №297. Название: Грамматика языка руссийскаго. Датировка: 1754 год. Издание: Львов. Типография Успенского Ставропигийского братства. https://kp.rusneb.ru/item/material/bukvar-grammatika-yazyka-russiyskago-chteniya-i-pisaniya-uchashchimsya-v-poleznoe-rukovozhdenie Чтобы ...
Простите, на другую тему пока записей не будет. Моя жизнь сейчас практически полностью сконцентрирована на этой девочке. Я хочу рассказать вам о нынешнем положении дел. Простите, если кого-то утомят детали. Это вопрос смерти и жизни, и мне очень важно, чтоб вы поняли. Прежде все ...
полоса напряжения в отношениях с Белоруссией... «Медведев припомнил Лукашенко Южную Осетию и Абхазию» (и ее полный текст): http://www.regnum.ru/news/polit/1331788.html и такая же www.newsru.com/russia/04oct2010/medvedev.html > > > Президент России Дмитрий Медведев выступил в своем ...
Все знают, что название «Олимпийские игры» произошло от места Олимпия в Древней Греции, где эти игры проводили. В подробности официальной истории этой темы углубляться не будем. Упомяну лишь, что в Олимпии, в священном на тот момент месте игры проводились каждые четыре года с 776 г. до ...
 Миксины - интересная группа рыб не имеющих челюстей, и миноги - их ближайшие родственники. С остальными рыбами их разделяет 500 миллионов лет эволюции. Миксины известны тем, что они способны выделять огромные количества очень вязкой слизи. Эта слизь используется и для охоты и для ...