Ошибка!

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

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

Ошибка!

Ошибка!

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

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

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

Ошибка!

Обратно

Закрыть

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

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


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


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

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

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

Новая визуализация НАСА исследует изгиб света двойных черных дыр

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

На ней показано, как черные дыры искажают и перенаправляют свет, исходящий от водоворота горячего газа, аккреционного диска, который окружает каждую из них. Если смотреть со стороны плоскости орбиты, каждый аккреционный диск приобретает характерный двугорбый вид. Но когда одна проходит перед другой, гравитация черной дыры на переднем плане превращает ее партнера в быстро меняющуюся последовательн...
16.04.21 19:00
0
2
Возможны ложные данные о кислороде при поиске признаков жизни на других планетах

Возможны ложные данные о кислороде при поиске признаков жизни на других планетах

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

Новые результаты, опубликованные 13 апреля в журнале AGU Advances, подчеркивают необходимость в телескопах следующего поколения, способных характеризовать планетную среду и искать многочисленные свидетельства существования жизни в дополнение к обнаружению кислорода. «Это полезно, потому что показывает наличие способов получить кислород в атмосфере без жизни, но есть и другие наблюдения, которые м...
14.04.21 21:21
0
0
Черные дыры любят поесть, но различаются манерами за столом

Черные дыры любят поесть, но различаются манерами за столом

Все сверхмассивные черные дыры в центрах галактик периодически поглощают материю из своего окружения. Но делают это по-разному.

Такой вывод сделали британские и голландские астрономы в исследовании с ультрачувствительными радиотелескопами в хорошо изученном регионе Вселенной. Астрономы изучали активные галактики с 1950-х годов. Активные галактики имеют сверхмассивную черную дыру в центре, которая поглощает материю. Во время таких активных фаз объекты часто излучают чрезвычайно сильное радио, инфракрасное, ультрафиолетово...
13.04.21 18:39
0
0
Запуск вертолета на Марсе отложен для технической проверки

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

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

Полет Ingenuity, который должен был стать первым в истории управляемым полетом на другой планете, был назначен на понедельник по московскому времени, но сейчас отложен как минимум до 14 апреля. Скоростное испытание винта четырехфунтового (1,8 кг) вертолета в пятницу закончилось раньше, чем ожидалось, из-за предупреждения о потенциальной проблеме. «Команда вертолета изучает телеметрию, чтобы диаг...
12.04.21 20:37
0
2
Настольный голографический принтер создает 3D-анимации на дому

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

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

Бывший исследователь MIT Media Lab занимается краудфандингом настольного 3D-голографического принтера, который может создавать изображения, которые появляются в 3D и даже кажутся движущимися. Хотя отражающие экраны, гарнитуры и даже живые выступления мертвых артистов маскируются под голограммы, технически этот термин относится к определенному типу трехмерного изображения, закодированного на двухм...
08.03.21 21:49
0
5
Первый в истории микропроцессор 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
0
2
Структура СКС и ее функциональные компоненты

Структура СКС и ее функциональные компоненты

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

Расширяется охват, повышаются требования к качеству передачи данных, а также безопасности функционирования производственных и служебных модулей. С этой целью в своё время были созданы средства массовой коммуникации (СМК). Для облегчения деятельности трудового коллектива (персонала) разработана технология под аббревиатурой СКС. СКС – структурированная кабельная система, представляющая собой своеобр...
07.02.21 21:26
1
11
2D-материал помогает обрабатывать и хранить данные

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

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

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