Ошибка!

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

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

Ошибка!

Ошибка!

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

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

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

Ошибка!

Обратно

Закрыть

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

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


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


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

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

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

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

Бесконечное количество споров о рисках для здоровья из-за кофе привело к последнему крупному исследованию.

На этот раз исследователи изучили данные более 300 000 человек о возможных связях между кофе и раком, и обнаружили, что он не вызывает и не предотвращает развитие рака. Это просто вкусный напиток. Многие считают, что дискуссия о кофе окончена, но наука никогда не останавливается на достигнутом, и всегда есть исследователи, которые думают, что могут сделать немного лучше. Так и должно быть. Хотя В...
18.07.19 15:52
0
2
Neuralink хочет подключить мозг к компьютеру уже в следующем году

Neuralink хочет подключить мозг к компьютеру уже в следующем году

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

Прошло более двух лет с тех пор, как мир узнал о Neuralink Илона Маска, - амбициозном и загадочном стартапе, сфокусированном на разработке интерфейсов мозг-компьютер, способных соединить человеческий мозг с машинами. Есть немало причин, по которым мы могли бы захотеть соединить наш мозг с компьютером, и уже есть несколько способов сделать это. Основные методы включают в себя использование электрод...
17.07.19 20:39
0
1
Обнаружены механизмы самозащиты бактерий

Обнаружены механизмы самозащиты бактерий

Эволюция помогла человечеству дожить до настоящего момента, но теперь она работает против нас.

Бактерии быстро развивают резистентность к нашим лучшим лекарствам, что ведет к будущему, когда антибиотики просто не будут работать. Но одна команда исследователей обнаружила потенциально уязвимую трещину в броне особенно проблемной группы бактерий. Многие антибиотики, в том числе пенициллин, с которого все началось, воздействуют на клеточную стенку бактерий. Проблема в том, что у класса грамотр...
17.07.19 19:59
0
4
Атмосфера защитит Землю от небольших астероидов

Атмосфера защитит Землю от небольших астероидов

Рюгу и другие астероиды спектрального класса С состоят из более пористого материала, чем считалось, из-за чего небольшие их фрагменты не выживают при попадании в атмосферу Земли.

Исследователи из Немецкого аэрокосмического центра (DLR) пришли к такому выводу в научной статье, опубликованной в журнале Nature Astronomy. Это выявило долгожданную причину дефицита таких метеоритов в находках на Земле. Результаты основаны на измерениях температуры поверхности с помощью радиометра MARA на борту немецко-французского MASCOT. 3 октября 2018 года, в рамках японской миссии Hayabusa2, ...
16.07.19 20:04
0
3
Роботизированная рыба питается от жидкой батареи

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

Сосудистая система робота имитирует человеческую.

Исследователи из Корнелльского университета разработали роботизированную рыбу, которая питается от кровеносной системы, которая работает на «крови». В роботе не настоящая кровь, а батарея в жидкой форме, которая движется по кровеносной системе бота. Как бы ни были современны роботы, им все еще не хватает «многофункциональных взаимосвязанных систем, обнаруживаемых в живых организмах», пишут исслед...
01.07.19 15:52
0
7
ИИ Сальвадор Дали жив и делает селфи в музее Флориды

ИИ Сальвадор Дали жив и делает селфи в музее Флориды

Посетителей музея Дали в Санкт-Петербурге, штат Флорида, теперь встречает виртуально воскрешенный Сальвадор Дали.

Цифровой Дали создан с использованием машинного обучения и технологии глубокой подделки, и запрограммирован общаться с людьми: от обсуждения погоды до съемки селфи с посетителями музея. Представленный на 115-ю годовщину рождения легендарного сюрреалиста, проект называется Dali Lives. Чтобы создать это сгенерированное цифровым способом изображение Дали, алгоритм ИИ проанализировал сотни интервью, ...
13.05.19 18:32
0
7
SpaceX запустит тысячи спутников на орбиту вокруг Земли

SpaceX запустит тысячи спутников на орбиту вокруг Земли

План SpaceX по запуску тысяч спутников на орбиту вокруг Земли был одобрен Федеральной комиссией по связи США.

Аэрокосмическая компания, принадлежащая предпринимателю-миллиардеру Илону Маску, может запустить первые из того, что в конечном итоге станет супер-созвездием из почти 12 000 спутников уже в мае. Спутники Starlink обеспечат дешевый и надежный доступ к Интернету по всему миру. SpaceX получила разрешение на запуск созвездия в ноябре 2018 года. Но с тех пор изменила свои планы размещения некоторых с...
29.04.19 17:19
0
7
Обновленный робот Handle работает на складе

Обновленный робот Handle работает на складе

Компания Boston Dynamics поделилась новым видео.

Немногие технологические компании становятся вирусными, как Boston Dynamics, благодаря своим роботам, которые могут подниматься по лестнице и открывать двери. На последнем видео главным героем стал «переосмысленный» старый робот Handle. Оказывается, он отлично подходит для складирования ящиков.Робот Handle - это «робот для мобильных манипуляций, разработанный для логистики», - говорится в описании...
31.03.19 16:43
0