Амеба нашла решение сложной математической задачи быстрее компьютера
Амеба — это простейшее существо, которое мы проходим в школе на одном из первых уроков биологии. Вряд ли кто-то считает амебу высокоинтеллектуальной особью, ведь у нее даже нет нервной системы в привычном нам понимании. Однако группа ученых из Токийского университета Кейо использовала этот одноклеточный организм для решения математической задачки. И на удивление амеба справилась с ней быстрее и эффективнее, чем мощный компьютер.
Задачка, которую предстояло решить, носит название «задача комивояжера». Она заключается в следующем: представьте, что вы коммивояжер, переезжающий из города в город, продавая свои товары. Вам нужно быть максимально эффективным, чтобы заработать как можно больше денег, поэтому вы хотите найти кратчайший путь, который позволит вам попасть в каждый город на маршруте следования. При этом не существует математической формулы, чтобы найти наиболее эффективный маршрут. Единственный способ решить проблему — вычислить длину каждого маршрута и посмотреть, какой из них самый короткий.
Но и это еще не все: расчет расстояния становится тем сложнее, чем больше городов добавляется к маршруту. Для 4 городов есть только 3 маршрута. А вот для 6 их уже 360. Это делает «задачу коммивояжера» одной из проблем, которую ученые называют «NP hard». То есть проблема, сложность которых возрастает по экспоненте даже из-за незначительного увеличения показателей. К такому же типу задач относится, например, майнинг криптовалют, поэтому находить их решение довольно важно на сегодняшний день.
В своей работе японские ученые использовали амебу Physarum polycephalum, а конкретнее — ее слизь, которую она распространяет в качестве «разведчика». Существо поместили в специальную камеру, в которой было множество каналов. В конце каждого из каналов исследователи разместили немного воды. Когда амеба получала воду — в одном из соседних каналов гас свет. Канал в данном случае был аналогом пути к городу из задачи.
Когда амеба дотягивается до воды, это влияет на вероятность того, что свет погаснет в каналах, являющиеся следующими городами на маршруте. Чем дальше расположен город, тем чаще в его канале будет гаснуть свет. Это может показаться невероятным, но добавление новых «городов» не увеличивало время, которое нужно затратить на решение задачи и путь по каналам всегда оставался кратчайшим. В отличие от компьютера, амебе не нужно было рассчитывать каждое конкретное расстояние, чтобы вычислить оптимальное. Вместо этого она реагирует на изменившиеся условия и определяет наилучшую возможную траекторию движения.
«Механизм, который влияет на скорость принятия решения амебой и то, как она вычисляет наиболее короткий путь до сих пор остается загадкой. Выяснив это, мы сможем найти пути быстрого решения сложных вычислительных задач и даже улучшить системы безопасности.» — говорит ведущий автор исследования Масаши Аоно.
Еще больше интересных и эксклюзивных материалов вы можете прочитать в нашем Telegram-канале(https://t.me/hightech_fm)
"Учёные вновь изнасиловали журналистов". По порядку:
1. Амёба нихрена не решила задачу, просто показала "неплохой" результат на относительно малом количестве тестов. Под "неплохим" результатом учёные понимают результат меньше медианного. В каждом тесте был минимальный путь длиной в 100 у.е., на тестах с 7 и 8 городами она ни разу не нашла путь длины 100.
2. В тесте с 4 городами среднее время поиска - 21 минута 36 секунд, что где-то в дохрена раз больше времени, чем тратит компьютер из 80ых.
3. Основной вывод - при увеличении числа городов и, соответственно, нелинейном росте числа возможных путей, время на поиск результата растёт почти линейно и амёба стабильно (~90%) находит "неплохой" результат. Возможно, это будет полезно для хорошей оптимизации приемлемого решения для большого числа городов, но ни в коем случае амёба не будет находить 100% решение задачи и "майнинг криптовалют" здесь вообще ни коем образом не замешан.
Чё-то непонятно. Если все каналы одинаковой длины, и в конце каждого есть вода, то какая для амебы разница между ними? Каким образом на эту камеру с каналами натягивают условия задачи? Что должно измениться в эксперименте, если я захочу изменить расстояние между двумя городами в исходном условии?
Завтра новость "DHL закупает 10 тонн амеб для построения крупной логистической сети"
Японцы похожим способом с плесенью игрались, когда метро под Токио развивали. Плесень тогда у них сахар искала.