Ошибка!

Показать Ошибка!

Забыли пароль?

Ошибка!

Ошибка!

Скрыть Ошибка!

Скрыть Ошибка!

Забыли пароль? Напишите ваш email и мы отправим письмо с инструкциями.

Ошибка!

Обратно

Закрыть

Амёба намекает на решение самой большой проблемы в информатике

Амёба намекает на решение самой большой проблемы в информатике
Одна маленькая амёба нашла решение задачи коммивояжера быстрее лучших алгоритмов. Что она знает такого, что не знаем мы?


Группа исследователей из токийского университета Кейо решила использовать амёбу для решения задачи коммивояжера, известной проблемы в области компьютерных наук. Задача выглядит так: представьте, что вы - коммивояжер, летающий из города в город и продающий свои товары. Вы стремитесь максимально повысить свою эффективность, чтобы заработать как можно больше денег, поэтому хотите найти кратчайший путь, который позволит вам добраться до каждого города на маршруте.
Нет простой математической формулы, чтобы найти наиболее эффективный маршрут для нашего продавца. Вместо этого, единственный способ решить проблему - это рассчитать длину каждого маршрута и посмотреть, какой из них самый короткий.
Что еще хуже, выполнение этого вычисления становится экспоненциально сложнее с увеличением количества городов на маршруте. С 4 городами есть только 3 разных маршрута для рассмотрения. Но с 6 городами появляется 360 различных маршрутов, которые необходимо рассчитать. Если у вас есть маршрут с 10 или более городами, количество возможных маршрутов исчисляется миллионами.
Это делает задачу коммивояжера одной из широкого класса проблем, которые компьютерные ученые называют «классом сложности NP». Это проблемы, которые экспоненциально усложняются очень быстро, что также включает проблемы, связанные со взломом зашифрованных систем и майнингом криптовалют. По вполне понятным причинам многие люди заинтересованы в поиске путей решения этих проблем как можно быстрее.
Решение Университета Кейо отличается от типичных алгоритмических решений, разработанных другими исследователями, потому что ученые использовали амёбу Physarum polycephalum. Physarum polycephalum – это слизь, очень простой организм, который делает две вещи: движется к еде и уходит от света. Миллионы лет эволюции сделали Physarum аномально эффективным в этих задачах.
Исследователи использовали эту эффективность для создания устройства для решения задачи коммивояжера. Они поместили амёбу в специальную камеру, заполненную каналами, и в конце каждого канала поместили немного еды. Инстинктивно амеба протягивает усики в каналы, чтобы попытаться получить еду. Однако, когда это происходит, она выключает свет в других каналах.


В данном случае каждый канал представляет город на маршруте нашего гипотетического продавца вместе с порядком посещения этого города. Когда амёба распространяется в канал, представляющий город, это влияет на вероятность того, что свет погаснет в каналах, представляющих следующие города на маршруте. Чем дальше находится этот город, тем чаще свет гаснет в этом канале.
Это может показаться окольным способом вычисления решения задачи коммивояжера, но преимущество заключается в том, что амёбе не нужно рассчитывать каждый отдельный путь, как это делают большинство компьютерных алгоритмов. Вместо этого амёба просто пассивно реагирует на условия, и сама находит наилучшее возможное решение. Это означает, что добавление новых городов для амёбы не увеличивает время, необходимое для решения проблемы.
Таким образом, амёба может решить NP-сложную задачу быстрее, чем любой из наших компьютерных алгоритмов. Как это произошло? Ученые из Кейо точно не уверены.
«Механизм, с помощью которого амёба поддерживает качество приближенного решения, то есть короткую длину маршрута, остается загадкой», - говорит ведущий автор исследования Масаси Аоно.
Но если исследователи смогут понять, как работает амёба, они смогут использовать этот прием не только для помощи коммивояжерам. Это может ускорить нашу способность решать всевозможные сложные вычислительные задачи и изменить подход к безопасности.
Эта маленькая амёба может навсегда изменить облик компьютеров.

Комментарии:

Еще нет комментариев, станьте первым коментатором!
Войдите на зайт или зарегистрируйтесь, чтобы оставлять комментарии!
0
Сделано многоцветное изображение первой межзвездной кометы

Сделано многоцветное изображение первой межзвездной кометы

Первая в мире комета из-за пределов Солнечной системы была успешно заснята обсерваторией Джемини в нескольких цветах.

Изображение объекта C/2019 Q4 (Borisov) было получено в ночь с 9 на 10 сентября с использованием мультиобъектного спектрографа на телескопе Джемини Север на Гавайских островах Маунакеа. «Это изображение появилось благодаря способности Джемини быстро корректировать наблюдения и наблюдать за такими объектами, которые имеют очень короткие окна видимости», - сказал Эндрю Стивенс из Обсерватории Джеми...
14.09.19 21:26
0
0
VISTA представляет новый образ Большого Магелланова Облака

VISTA представляет новый образ Большого Магелланова Облака

Большое Магелланово Облако - один из наших ближайших галактических соседей, всего в 163 000 световых лет от Земли.

Они с Малым Магеллановым Облаком являются одними из ближайших галактик-спутников-карликов к Млечному Пути.  Большое Магелланово Облако (БМО) также является домом для различных звездных скоплений и идеальной лабораторией для астрономов для изучения процессов формирования галактики. Телескоп ESO VISTA наблюдает за этими двумя галактиками в течение последнего десятилетия. Представленное сегодня...
13.09.19 19:46
0
1
Новое путешествие под землю для освоения космоса

Новое путешествие под землю для освоения космоса

Шесть астронавтов, пять космических агентств и новый старт в подземный мир, чтобы помочь подготовиться к жизни на других планетах.

Последнее учебное приключение ЕКА предоставит международному экипажу навыки для изучения неизведанных ландшафтов на Луне и Марсе, на этот раз с акцентом на поиски воды. Учебный курс CAVES отправляет астронавтов в глубины Земли, чтобы улучшить их навыки общения, решения проблем и командной работы. После недели подготовки над и под землей «каванавты» собираются исследовать пещеру в Словении, где он...
12.09.19 21:08
0
1
На потенциально обитаемой экзопланете обнаружена вода

На потенциально обитаемой экзопланете обнаружена вода

Экзопланета K2-18b, с массой в восемь раз больше Земли, стала единственной планетой, вращающейся вокруг звезды за пределами Солнечной системы, у которой есть вода и температура, которые могут поддерживать жизнь.

Открытие, опубликованное в Nature Astronomy, является первым успешным обнаружением в атмосфере экзопланеты, находящейся на орбите в обитаемой зоне звезды на расстоянии, где вода может существовать в жидкой форме. Первый автор статьи доктор Ангелос Циарас сказал: «Поиск воды в потенциально обитаемом мире, отличном от Земли, невероятно захватывающий. K2-18b - это не Земля 2.0, поскольку она значите...
12.09.19 19:48
0
1
Samsung представила Galaxy A90 5G

Samsung представила Galaxy A90 5G

На домашнем рынке южнокорейский производитель Самсунг объявил о выпуске телефона Galaxy A90 5G.

Он создан для тех, кто живет в цифровом мире. Устройство сочетает в себе 5G-соединение с мощными функциями для потоковой передачи и обмена данными. С четвертого сентября смартфон станет доступен в Южной Корее, а через некоторое время и на других рынках.Технические спецификации гаджета:- Сеть: 5G (NSA), Sub6- Габариты: 164.8х76.4х8.4мм- Вес: 206 грамм- Экран: 6.7 дюймов / Super AMOLED / Infinity-U-...
06.09.19 08:57
0
5
Каким Samsung видит мир в 2069 году?

Каким Samsung видит мир в 2069 году?

Новый прогноз «Samsung KX50: будущее в фокусе» основан на мнении шести ведущих британских ученых и футуристов о ряде новых технологий, которые повлияют на повседневную жизнь людей.

Попытка предсказать будущее - это хитрый бизнес с крайне низким уровнем успеха. Если бы мир 2019 года был похож на прошлые прогнозы, у нас были бы летающие машины, личные реактивные ранцы, роботы-дворецкие, 100-процентная атомная энергетика, производящая безграничную энергию, маленькие бутылки с наноботами, которые могут выращивать машины на лужайке перед домом, колонии на Луне и Марс - и все это ...
01.09.19 20:58
0
1
Фестиваль 404 в Самаре 14-15 сентября — надо ехать!

Фестиваль 404 в Самаре 14-15 сентября — надо ехать!

404FEST — самое душевное IT-событие в России.

Два дня, 1500 участников, 70 спикеров, 10 секций: мобильная и веб-разработка, дизайн и UX, управление проектами и продуктами, PR и бизнес, контроль качества и технологии будущего.Загляните на роскошную секцию дизайн-директора Mail ru Юрия Ветрова и двухдневную веб-секцию Макса Сальникова из норвежского офиса Microsoft, послушайте доклад PR-директора Яндекс.Такси Владимира Исаева или любого другого...
26.08.19 10:37
0
4
Роботизированная рыба питается от жидкой батареи

Роботизированная рыба питается от жидкой батареи

Сосудистая система робота имитирует человеческую.

Исследователи из Корнелльского университета разработали роботизированную рыбу, которая питается от кровеносной системы, которая работает на «крови». В роботе не настоящая кровь, а батарея в жидкой форме, которая движется по кровеносной системе бота. Как бы ни были современны роботы, им все еще не хватает «многофункциональных взаимосвязанных систем, обнаруживаемых в живых организмах», пишут исслед...
01.07.19 15:52
0