Ошибка!

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

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

Ошибка!

Ошибка!

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

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

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

Ошибка!

Обратно

Закрыть

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

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

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


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

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

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

Измерена скорость вращения Сатурна по волнам в кольцах

Наблюдения колец Сатурна с беспрецедентной детализацией от космического корабля НАСА Cassini дали ученым возможность исследовать внутреннюю часть планеты-гиганта и получить первое точное определение скорости её вращения.

Согласно расчетам, продолжительность дня на Сатурне составляет 10 часов 33 минуты и 38 секунд.Исследователи изучали волновые структуры, созданные в кольцах Сатурна внутренними колебаниями планеты. По сути, кольца действуют как чрезвычайно чувствительный сейсмограф, реагируя на вибрации внутри самой планеты.Подобно вибрациям от землетрясения на Земле, Сатурн реагирует на возмущения, вибрируя на час...
19.01.19 21:44
0
3
Сатурн обзавелся кольцами сравнительно недавно

Сатурн обзавелся кольцами сравнительно недавно

Одним из последних действий космического корабля НАСА Кассини перед смертью стало движение между планетой и ее кольцами.

Точные измерения окончательной траектории движения Кассини позволили ученым сделать первую точную оценку количества материала в кольцах планеты, взвесив их в зависимости от силы их гравитационного притяжения.Получилось около 40 процентов массы Мимаса, луны Сатурна, которая сама в 2000 раз меньше нашей Луны. Это говорит о том, что кольца возникли сравнительно недавно – 10 - 100 миллионов лет назад....
18.01.19 19:51
0
4
Китайский эксперимент закончился морозной лунной ночью

Китайский эксперимент закончился морозной лунной ночью

Росток хлопка, проросший на Луне, погиб из-за наступления ночи, которая продлится две земных недели.

Ранее на этой неделе китайское космическое агентство объявило, что семена хлопка проросли в специальной канистре на борту зонда Chang'e-4, после того как 3 января космический корабль совершил первую в мире посадку на обратной стороне Луны. Эксперимент Lunar Micro Ecosystem, продлившийся более 212 часов, закончился. Ожидалось, что температура внутри контейнера опустится ниже -52 градусов по Цельс...
18.01.19 19:13
0
7
Обнаружено свидетельство смены времен года и дожди на северном полюсе Титана

Обнаружено свидетельство смены времен года и дожди на северном полюсе Титана

Изображение с Кассини свидетельствует об осадках на северном полюсе Титана, самого большого из спутников Сатурна. Осадки - первый признак начала летнего сезона в северном полушарии луны.

«Все с нетерпением ждут возможности увидеть облака и дожди на северном полюсе Титана, что указывает на начало северного лета, но, несмотря на предсказания климатических моделей, мы не увидели даже облаков», - сказала Раджани Дхингра, аспирант университета штата Айдахо в Москве и ведущий автор нового исследования. Дингра и ее коллеги обнаружили сияние около северного полюса Титана на снимке, сдела...
17.01.19 16:58
0
4
5 технологий будущего, которые обязательно изменят этот мир

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

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

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

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

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

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

Новый Huawei P30 Pro 2019 года

Вторая половина февраля 2019 года обещает показать международной выставке MWC 2019 Barcelona новый флагманский смартфон Huawei P30 Pro. Чего же стоит от него ожидать?

В первую очередь, это основная камера с трёхкратным зумом. Далее в списке достоинств идёт поддержка 5G, что станет приятным сюрпризом для любителей высокоскоростного интернета.Исполнительный директор отдела Huawei Devices впервые официально рассказал о данной модели ещё в начале сентября. Тогда он заявил, что P30 превзойдёт Mate 20 (дата выхода запланирована на вторую половину октября) по многим п...
13.12.18 22:23
0
2
Корейский человекоподобный робот Mahru

Корейский человекоподобный робот Mahru

У японского робота Honda ASIMO появляется все больше и больше конкурентов. На сегодняшний день основным и достойным конкурентом японца становится его корейский собрат Mahru.

Учитывая усовершенствования японца, корейские специалисты также обновили внешний вид Mahru, придав ему более симпатичный вид. Однако, внешние изменения повлияли на звучность робота: за счет нового корпуса, Mahru стал громыхать. Но с другой стороны, смена имиджа железного чуда нисколько не повлияла на его возможности.Специалистами института KIST была проведена еще одна презентация корейского челове...
12.12.18 09:30
0