Ошибка!

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

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

Ошибка!

Ошибка!

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

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

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

Ошибка!

Обратно

Закрыть

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

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


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


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

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

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

Визуализация галактического центра Млечного Пути

Хотите отправиться в путешествие по центру Млечного Пути? Посмотрите новую иммерсивную визуализацию сверхвысокой четкости.

Это 360-градусное видео предлагает беспрецедентную возможность осмотреть центр галактики с точки зрения центральной сверхмассивной черной дыры в любом выбранном направлении. Комбинируя симуляции суперкомпьютера НАСА Ames с данными рентгеновской обсерватории Chandra, эта визуализация обеспечивает новый взгляд на то, что происходит в центре Млечного пути и вокруг него. Она показывает влияние деся...
22.03.19 22:05
0
1
Астронавты заменяют аккумуляторы МКС

Астронавты заменяют аккумуляторы МКС

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

Энн МакКлейн и Ник Хейг из НАСА будут в течении нескольких часов работать в открытом космосе, чтобы заменить три старые никель-водородные батареи на более мощные литий-ионные аккумуляторы. Астронавтам пришлось приложить немного усилий для выполнения своей первой задачи, которая заключалась в прикрепление сумки с инструментами к корпусу станции для возможного использования в будущем. Робот-манипу...
22.03.19 21:03
0
5
НАСА может отправиться к астероиду Паллада

НАСА может отправиться к астероиду Паллада

НАСА рассматривает вопрос о финансировании миссии, в ходе которой небольшой спутник отправится в пояс астероидов, чтобы исследовать огромный астероид Паллада.

Решение будет объявлено в середине апреля. Если миссия, получившая название Афина, будет одобрена, она будет следовать по пути миссии НАСА «Рассвет». Этот космический корабль исследовал два других гигантских объекта в поясе астероидов, Весту и Цереру, прежде чем его миссия закончилась этой осенью. «Паллада - единственный объект в главном поясе астероидов, похожий на Весту и Цереру. Не просто ас...
21.03.19 20:08
0
4
Обнаружен спутник звезды HD 118475

Обнаружен спутник звезды HD 118475

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

Звезда HD 118475 находится примерно в 107 световых годах от Земли. Она примерно на 12% массивнее Солнца, эффективная температура около 5900 К и металличность на уровне 0,07.Команда астрономов во главе со Стивеном Р. Кейном из Калифорнийского университета в Риверсайде провела наблюдения радиальной скорости HD 118475 в поисках любых объектов, сопровождающих эту звезду в рамках англо-австралийского п...
21.03.19 19:25
0
2
Обзор Samsung Galaxy S10

Обзор Samsung Galaxy S10

В этой статье речь пойдет об этой модели, а точнее о ее основных характеристиках и интересных свойствах функционала.

Немного остановимся на технической части характеристик. Для покупателей представлен небольшой спектр возможных цветов мобильного телефона – это перламутр, черный оникс и аквамарин. Корпус смартфона сделан из металла с добавлением стекла. Экран 6,1 пикселей, что тоже довольно неплохо. Весьма мощный процессор – целых 8 ядер. Имеется поддержка карт памяти до 512 Гб. Сама память телефона составляет це...
20.03.19 13:06
0
2
Ученые создали сеть внутри человека

Ученые создали сеть внутри человека

Это изобретение поможет держать кардиостимуляторы и инсулиновые помпы в безопасности.

Ужасная история пишет сама по себе: взломанные кардиостимуляторы и инсулиновые помпы. Получение контроля над медицинскими устройствами через беспроводные соединения позволяет хакерам визуализировать показатели жизненно важных функций или даже причинять вред человеку. Команда инженеров в Пердью работает над решением этой проблемы.«Мы подключаем все больше и больше устройств к сети человеческого тел...
13.03.19 20:54
0
6
5 технологий будущего, которые обязательно изменят этот мир

5 технологий будущего, которые обязательно изменят этот мир

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

Однако высокотехнологическая эра уже вступила в свои права. И это можно хорошо проследить, сравнив черно-белые пэйджеры 90-х с нынешними смартфонами, которые по мощности ни чем не хуже среднего компьютера. А прошло всего лишь двадцать лет. Что же стоит ожидать в ближайшем будущем?1. Умное стеклоСегодня вокруг нас все становится умным. И самое неожиданное, что можно увидеть утром в ванной - это умн...
09.01.19 13:23
0
4
«Donald» и «sunshine» присоединяются к списку худших паролей 2018 года

«Donald» и «sunshine» присоединяются к списку худших паролей 2018 года

Поразительное рядом: в списке наиболее часто используемых паролей 2018 года огромное количество людей все еще использует «password» (пароль) в качестве своего пароля.

Когда мы представляем гадкого хакера, проникающего в наши учетные записи, то с удовольствием представляем супер-опытного компьютерного волшебника, стучащего по клавиатуре перед эпической коллекцией мониторов. Но на самом деле, многие личные учетные записи скомпрометированы потому, что кто-то просто угадал слишком простой пароль. Поразительное рядом: в списке наиболее часто используемых паролей 201...
14.12.18 20:42
0