Ошибка!

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

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

Ошибка!

Ошибка!

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

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

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

Ошибка!

Обратно

Закрыть

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

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


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


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

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

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

Молекулярные облака продлевают себе жизнь, постоянно собирая себя заново

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

Чтобы создать звезды, сначала нужны гигантские облака молекулярного газообразного водорода. Это резервуары, которые могут подвергнуться катастрофическому коллапсу. При этом могут появиться сразу десятки и даже сотни звезд. Без резервуаров газа невозможно создать звезды, поэтому астрономов особенно интересует, как ведут себя эти облака. Эволюция облаков в галактической среде может рассказать об ист...
31.01.23 08:45
0
1
Ультратонкое покрытие делает солнечные батареи самоочищающимися

Ультратонкое покрытие делает солнечные батареи самоочищающимися

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

Солнечная энергия — крупнейший источник возобновляемой энергии, и быстро растет. Но, как можно себе представить, невозможно отправить кого-то со шваброй для очистки миллионов солнечных панелей в каждом парке. В идеале они бы сами очищались, и теперь исследователи из Института Фраунгофера в Германии добились успехов в этой концепции. Команда создала покрытие, которое меняет свою реакцию на воду в ...
30.01.23 13:27
0
0
Метеориты раскрывают вероятное происхождение летучих химических веществ Земли

Метеориты раскрывают вероятное происхождение летучих химических веществ Земли

Метеориты рассказали исследователям о вероятном далеком происхождении летучих химических веществ Земли, некоторые из которых составляют строительные кирпичики жизни.

Они обнаружили, что около половины земных запасов летучего элемента цинка приходится на астероиды, происходящие из внешней части Солнечной системы — части за поясом астероидов, который включает планеты Юпитер, Сатурн и Уран. Предполагается, что из этого материала были получены и другие важные летучие вещества, такие как вода. Летучие вещества — это элементы или соединения, которые переходят из тв...
28.01.23 14:04
0
2
Впервые представлен бестопливный генератор электроэнергии от компании Neutrino Energy Group

Впервые представлен бестопливный генератор электроэнергии от компании Neutrino Energy Group

Технологическое развитие экономики и общества неразрывно связано с появлением новых материалов и исследованием их свойств, в частности наноматериалов.

Если проанализировать наиболее критичные области экономики, которые находятся сегодня в эпицентре санкций и антисанкций, - это энергоресурсы и IT, в первую очередь, разработки различных чипов. Но развитие любой из стран, в первую очередь, попадающих под различные ограничения, показывает, что не только правительста и госкомпании, но и национальный бизнес готов направлять финансовые инвестиции и ин...
27.01.23 18:23
0
5
iPhone 14 и 14 Plus предлагают лучшие камеры, лучшее время автономной работы и технологию SOS

iPhone 14 и 14 Plus предлагают лучшие камеры, лучшее время автономной работы и технологию SOS

7 сентября Apple анонсировала новый iPhone 14 вместе с более крупным 14 Plus. Оба телефона 5G оснащены новой системой камер, функцией обнаружения сбоев, экстренным вызовом SOS через спутник и лучшим временем автономной работы среди всех iPhone.

У базового iPhone 14 6,1-дюймовый дисплей Super Retina XDR, а модель Plus — 6,7 дюйма. Дисплеи оснащены прочным стеклом Ceramic Shield, а также водо- и пыленепроницаемы. Широко разрекламированная система камер включает в себя новые камеры Main, TrueDepth и Ultra wide. У камеры Main большая диафрагма 1,5 и пиксели размером 1,9 микрометра, что позволяет улучшать фото и видео при всех сценариях осв...
11.09.22 10:54
0
0
Дистанционно управляемые тараканы-киборги теперь питаются от Солнца

Дистанционно управляемые тараканы-киборги теперь питаются от Солнца

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

Насекомые используют целый ряд мощных органов чувств, они достаточно малы, чтобы добраться до недоступных для нас мест, они могут выживать в неблагоприятных условиях, они могут с легкостью карабкаться по поверхности или летать. Все это полезные атрибуты для роботов — или, что еще лучше, киборгов, если прикрепить электронные устройства к живым насекомым. За прошедшие годы многие виды насекомых под...
06.09.22 08:12
0
10
Оптический чип обрабатывает почти 2 миллиарда изображений в секунду

Оптический чип обрабатывает почти 2 миллиарда изображений в секунду

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

В основе нового чипа лежит нейронная сеть - система, моделирующая то, как мозговая информация. Эти сети происходят из узлов, которые соединяются друг с другом с появлением нейронов, и они даже «обучаются» органическому мозгу, занимаясь набором данных, например, распознавание объектов на изображениях или словах в речи. Со временем они намного лучше справляются с задачами. Но вместо электрических с...
08.06.22 07:10
0
3
Самые быстрые логические вентили могут сделать компьютеры в миллион раз быстрее

Самые быстрые логические вентили могут сделать компьютеры в миллион раз быстрее

Логические вентили - это фундаментальные строительные блоки компьютеров, и исследователи из Университета Рочестера разработали самые быстрые из созданных.

Уничтожая графен и золото лазерными импульсами, новые логические вентили работают в миллион раз быстрее, чем в существующих компьютерах, демонстрируя жизнеспособность «световолновой электроники». Логические элементы принимают два входа, сравнивают их, а затем выводят сигнал на основе результата. Например, они могут выводить 1, если оба входящих сигнала равны 1 или 0, или если один из них или ни о...
14.05.22 10:42
0