Ошибка!

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

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

Ошибка!

Ошибка!

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

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

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

Ошибка!

Обратно

Закрыть

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

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


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


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

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

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

Предполагаемый фосфин на Венере, скорее всего, обычный диоксид серы

В сентябре группа астрономов из Соединенного Королевства объявила про обнаружение химического фосфина в толстых облаках Венеры. Сообщение, основанное на наблюдениях двумя земными радиотелескопами, удивило многих экспертов по Венере.

Атмосфера Земли содержит небольшое количество фосфина, который может вырабатываться жизнью. Фосфин на Венере вызвал слухи о том, что планета могла каким-то образом укрывать жизнь в своих облаках. После первоначального заявления другие научные группы поставили под сомнение надежность обнаружения фосфина. Группа исследователей из Вашингтонского университета использовала надежную модель условий в ат...
27.01.21 23:57
0
3
Новая галактика проливает свет на формирование звезд

Новая галактика проливает свет на формирование звезд

О галактиках известно многое. Известно, что звезды в них сформированы из смеси старой звездной пыли и молекул в газе. Но остается загадкой, как эти простые элементы соединяются вместе и образуют новую звезду.

Международная группа ученых, включая астрофизиков из Университета Бата в Великобритании и Национальной астрономической обсерватории (OAN) в Мадриде, Испания, сделала значительный шаг к пониманию того, как газообразное содержимое галактики превращается в новое поколение звезд. Их выводы имеют важное значение для нашего понимания того, как звезды формировались в первые дни существования Вселенной, ...
25.01.21 19:56
0
0
Магнитные волны объясняют загадку внешнего слоя Солнца

Магнитные волны объясняют загадку внешнего слоя Солнца

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

Одно из объяснений состоит в том, что в среднем слое (хромосфере) магнитные волны разделяют плазму Солнца на различные компоненты, так что только ионные частицы переносятся в корону, оставляя нейтральные частицы позади, что приводит к накоплению во внешней атмосфере таких элементов, как железо, кремний и магний. В новом исследовании, опубликованном в The Astrophysical Journal, исследователи объед...
24.01.21 19:11
0
2
Семь каменистых планет TRAPPIST-1 имеют очень похожий состав.

Семь каменистых планет TRAPPIST-1 имеют очень похожий состав.

Красный карлик TRAPPIST-1 стал домом для самой большой группы планет размером с Землю, когда-либо обнаруженных в одной звездной системе. Эти 7 скалистых экзопланет, расположенных на расстоянии около 40 световых лет от нас, являются примером огромного разнообразия планетных систем, которые заполняют Вселенную.

Новое исследование показывает, что у планет TRAPPIST-1 очень похожие плотности. Это может означать, что все они содержат примерно одинаковое соотношение материалов, которые составляют большинство каменистых планет, таких как железо, кислород, магний и кремний. Но если это так, это соотношение должно заметно отличаться от земного: у планет TRAPPIST-1 примерно на 8% меньше плотности, чем если бы име...
23.01.21 18:05
0
7
2D-материал помогает обрабатывать и хранить данные

2D-материал помогает обрабатывать и хранить данные

Инженеры EPFL создали новый компьютерный чип, который может обрабатывать и хранить данные в одной цепи.

Он изготовлен из двумерного дисульфида молибдена (MoS2), что открывает путь для создания более компактной и энергоэффективной электроники. Традиционные компьютеры обрабатывают данные в центральном процессоре, а затем передают их в другой раздел, например, на жесткий диск или твердотельный накопитель, для хранения. Эта система работала десятилетиями, но это не обязательно самый эффективный способ ...
08.11.20 15:26
0
7
Роботизированная медуза движется быстрее живой

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

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

Уникальное движение медуз сделало их популярной моделью обучения для исследователей робототехники, мечтающих разработать новые передовые аппараты, которые будут двигаться с большей эффективностью. Этот новый тип мягкого робота был разработан учеными из Университета Северной Каролины и Университета Темпл и фактически основан на их более ранней работе, в результате которой был создан быстро движущ...
02.07.20 21:52
0
6
HAMR-JR - один из самых маленьких и быстрых роботов

HAMR-JR - один из самых маленьких и быстрых роботов

Семь лет назад в Гарварде создали робота HAMR. И хотя бот уже был маленьким, его дизайнеры создали версию вдвое меньше. Знакомьтесь - HAMR-JR.

Оригинальный HAMR (Harvard Ambulatory MicroRobot) длиной всего 4,4 см (1,7 дюйма) и использует четыре ножки с керамическим приводом для перемещения со скоростью до 8,4 длин тела в секунду. Он был построен с помощью метода производства печатных плат микроэлектромеханических систем (PC-MEMS) Гарварда. Это включает в себя изготовление плоского листа микрослоистого материала, а затем с помощью лазера...
03.06.20 21:57
0
8
Технологический прогресс и его составляющие

Технологический прогресс и его составляющие

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

Сейчас нашу жизнь невозможно представить без электроники, абсолютно все сферы деятельности зависят от тех или иных приборов, помогающих человеку жить, работать, исследовать и создавать. Необходимым элементом для работы даже самого простого электронного устройства является печатная плата, главной задачей которой является электрическое и механическое соединение различных электронных компонентов.&nbs...
07.04.20 21:52
0