Ошибка!

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

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

Ошибка!

Ошибка!

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

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

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

Ошибка!

Обратно

Закрыть

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

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


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


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

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

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

Первое обнаружение света из-за черной дыры

Наблюдая за рентгеновскими лучами, выбрасываемыми во Вселенную сверхмассивной черной дырой в центре галактики на расстоянии 800 миллионов световых лет от нас, астрофизик Стэнфордского университета Дэн Уилкинс заметил интригующую закономерность.

Он наблюдал серию ярких рентгеновских вспышек, интересных, но не беспрецедентных, а затем телескопы зафиксировали нечто неожиданное: дополнительные рентгеновские вспышки, которые были меньше, позже и разных «цветов», чем яркие вспышки. Согласно теории, эти световые эхо соответствовали рентгеновским лучам, отраженным позади черной дыры, но даже базовое понимание черных дыр говорит нам, что это стр...
29.07.21 09:37
0
1
Астрономы показали образование планет в двойных системах

Астрономы показали образование планет в двойных системах

Астрономы разработали наиболее реалистичную на сегодняшний день модель образования планет в двойных звездных системах.

Исследователи из Кембриджского университета и Института внеземной физики Макса Планка показали, как экзопланеты в двойных звездных системах возникли, не будучи разрушенными в хаотичной среде рождения. Они изучили тип двойной системы, в которой меньшая звезда-компаньон вращается вокруг большей родительской звезды примерно раз в 100 лет - наш ближайший сосед, Альфа Центавра, является примером такой...
28.07.21 09:56
0
0
Хаббл обнаружил первые свидетельства наличия водяного пара на Ганимеде

Хаббл обнаружил первые свидетельства наличия водяного пара на Ганимеде

Впервые астрономы обнаружили свидетельства водяного пара в атмосфере спутника Юпитера Ганимеда. Водяной пар образуется, когда лед с поверхности луны сублимируется, то есть превращается из твердого вещества в газ.

Предыдущие исследования предоставили косвенные доказательства того, что Ганимед, самая большая луна в Солнечной системе, содержит больше воды, чем все океаны Земли. При этом температура там настолько низкая, что вода на поверхности замерзает. Океан Ганимеда будет располагаться примерно на 100 миль ниже земной коры; следовательно, водяной пар – это не испарение океана. Астрономы пересмотрели наблю...
27.07.21 10:28
0
3
НАСА выбрало SpaceX для миссии к Европе

НАСА выбрало SpaceX для миссии к Европе

В пятницу НАСА заявило, что выбрало SpaceX для запуска запланированного рейса к ледяному спутнику Юпитера Европе, что стало огромной победой компании Илона Маска, которая нацелена глубже в Солнечную систему.

Миссия Europa Clipper будет запущена в октябре 2024 года на ракете Falcon Heavy из Космического центра Кеннеди во Флориде, общая стоимость контракта составляет 178 миллионов долларов. Ранее предполагалось, что миссия будет запущена на собственной ракете НАСА Space Launch System (SLS), страдающей от задержек и перерасхода средств. И хотя SLS еще не работает, Falcon Heavy уж использовался как в ком...
26.07.21 10:59
0
4
Hyundai покупает Boston Dynamics

Hyundai покупает Boston Dynamics

Hyundai Motor Group сделала важный шаг в мире мобильной робототехники, объявив о приобретении контрольного пакета акций Boston Dynamics у японской технологической компании Softbank.

Компания Boston Dynamics, наиболее известная своей неизменно впечатляющей роботизированной собакой по имени Spot, теперь будет работать вместе с автопроизводителем над технологиями, улучшающими мобильность человека. Boston Dynamics впервые представила Spot в июне прошлого года, и среди его стабильных маневренных роботов четвероногий, похожий на собаку, несомненно, стал звездой шоу. Мы видели, как...
22.06.21 10:42
0
1
Запуск серии телевизоров Mi TV P1 в Европе: что готовит Xiaomi?

Запуск серии телевизоров Mi TV P1 в Европе: что готовит Xiaomi?

Xiaomi регулярно создает интересные новинки телевизоров для локального и мирового рынка.

Свежая линейка Mi TV P1 нацелена на Европу, ее анонс состоялся в Италии. Уже в мае представленные разработки должны появиться на прилавках магазинов в разных странах.  Mi TV P1 — это 4 модели, которые принадлежат к бюджетному и среднему сегменту цен. За самый дешевый телевизор Хиоми Mi TV P1 просят от 280 долларов.  Фишки и особенности Экраны у новинок жидкокристаллические. В кач...
28.05.21 23:11
0
1
Настольный голографический принтер создает 3D-анимации на дому

Настольный голографический принтер создает 3D-анимации на дому

Голограммы - одно из обещаний научной фантастики, которые остаются недостижимыми.

Бывший исследователь MIT Media Lab занимается краудфандингом настольного 3D-голографического принтера, который может создавать изображения, которые появляются в 3D и даже кажутся движущимися. Хотя отражающие экраны, гарнитуры и даже живые выступления мертвых артистов маскируются под голограммы, технически этот термин относится к определенному типу трехмерного изображения, закодированного на двухм...
08.03.21 21:49
0
7
Первый в истории микропроцессор Texas Instruments TMX 1795. Создан 50 лет назад, 24 февраля 1971 года.

Первый в истории микропроцессор Texas Instruments TMX 1795. Создан 50 лет назад, 24 февраля 1971 года.

Первый в истории микропроцессор Texas Instruments TMX 1795. Создан 50 лет назад, 24 февраля 1971 года.

Микропроцессор Texas Instruments TMX 1795. Предоставлено Computer History Museum.История начинается с Datapoint 2200 [1], «программируемого терминала», размер которого позволяет разместить его на рабочем столе. Первоначально Datapoint 2200 продавался как терминал, но на самом деле это был мини-компьютер, который можно было программировать на BASIC или PL / B. Некоторые люди считают Datapoint ...
24.02.21 20:08
1