Ошибка!

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

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

Ошибка!

Ошибка!

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

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

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

Ошибка!

Обратно

Закрыть

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

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


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


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

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

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

У V473 Lyr обнаружен компаньон с низкой массой

Используя космический аппарат XMM-Newton, астрономы провели рентгеновские наблюдения своеобразной переменной звезды цефеиды V473 Lyr.

Переменные звезды (или цефеиды) - это светящиеся желтые гиганты, изменяющие свою яркость в результате регулярных звездных пульсаций. Учитывая, что периоды их изменения тесно связаны с их светимостью, астрономы используют их для измерения межзвездных и межгалактических расстояний. Расположенная на расстоянии около 1800 световых лет, V473 Lyr представляет собой своеобразную цефеиду с переменной амп...
17.01.20 15:11
0
0
Открыта новая суперземля у Проксимы Центавра

Открыта новая суперземля у Проксимы Центавра

Астрономы обнаружили еще одну кандидатуру в экзопланеты, вращающуюся вокруг Проксимы Центавра. Если подтвердится, это будет вторая экзопланета, обнаруженная на орбите звезды.

В 2016 году астрономы обнаружили планету, вращающуюся вокруг Проксимы Центавра, ближайшей звезды к нашему Солнцу. Планета Proxima b потенциально пригодна для обитания, и тогда ходили слухи, что мы могли бы послать туда робота-исследователя всего через несколько десятилетий. Открытие второй планеты, даже если она находится слишком далеко от звезды для наличия жидкой воды, увеличивает интерес к сист...
16.01.20 22:58
0
1
Астрономы раскрывают межзвездное происхождение одного из строительных блоков жизни

Астрономы раскрывают межзвездное происхождение одного из строительных блоков жизни

Фосфор, присутствующий в нашей ДНК и клеточных мембранах, важный элемент той жизни, какой мы её знаем. Но его появление на ранней Земле остается загадкой.

Астрономы проследили путь фосфора из звездообразующих областей к кометам, используя объединенные силы ALMA и зонда Rosetta Европейского космического агентства. Их исследования впервые показывают, где образуются молекулы, содержащие фосфор, как этот элемент переносится в кометах и ??как определенная молекула могла сыграть решающую роль в начале жизни на нашей планете. «Жизнь появилась на Земле око...
15.01.20 23:09
0
1
Тайна приземления Гюйгенса раскрыта

Тайна приземления Гюйгенса раскрыта

Пятнадцать лет назад зонд ЕКА Гюйгенс вошел в историю, когда спустился на поверхность спутника Сатурна Титан и стал первым зондом, который успешно приземлился во внешней Солнечной системе.

Но во время спуска зонд начал вращаться не в ту сторону - и недавние испытания показывают почему. Миссия НАСА/ЕКА/ИКА Кассини-Гюйгенс, начатая в 1997 году, остается культовой и внесла огромный вклад в наше понимание Сатурна и его луны Титана с момента его прибытия на планету в конце 2004 года. Миссия включала в себя орбитальный аппарат Кассини, который более 13 лет летал на орбите Сатурна после ...
15.01.20 22:35
0
3
Futurus превратит лобовое стекло в дисплей AR

Futurus превратит лобовое стекло в дисплей AR

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

Пекинская компания Futurus считает, что автомобили ближайшего будущего будут выпускаться с поющими, танцующими лобовыми стеклами дополненной реальности, и заявляет, что готова представить технологию проекции светового поля, которая сделает это возможным на выставке CES 2020 в следующем месяце. Предлагая поле зрения до 60 градусов, разрешение 80 пикселей/градус и яркость до 15 000 нит, эти дисплеи...
14.12.19 22:32
1
5
SAMOLED - компания Samsung запатентовала новый тип дисплея

SAMOLED - компания Samsung запатентовала новый тип дисплея

Скоро мы увидим новые дисплеи в новых телефонах Galaxy.

Производитель подал заявку на сохранение исключительного права на использование названия будущих экранов - SAMOLED.Все мы ожидаем появления новых флагманов Samsung, а последние утечки говорят о том, что у них теперь будут совершенно новые дисплеи. Производитель зарезервировал в Корейском ведомстве торговое наименование SAMOLED - его не следует сравнивать и путать с Super AMOLED. В предыдущем флагм...
14.11.19 21:43
0
4
GoPro представила экшн-камеру Hero8 Black

GoPro представила экшн-камеру Hero8 Black

После короткой онлайн-тизерной кампании GoPro представила преемника прошлогоднего Hero7 Black.

Hero8 Black похвастается улучшенной стабилизацией, новой функцией Digital Lens и возможностью подключения аппаратных надстроек – Mods – к экшн-камере. Новый флагман GoPro поставляется с технологией Hypersmooth второго поколения, которая работает со всеми разрешениями и частотой кадров, и теперь включает в себя режим Boost, повышающий уровень стабилизации, а также автоматическое выравнивание гориз...
02.10.19 19:52
1
7
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