antony_w (antony_w) wrote,
antony_w
antony_w

Categories:

Амеба нашла решение сложной математической задачи быстрее компьютера



Амеба — это простейшее существо, которое мы проходим в школе на одном из первых уроков биологии. Вряд ли кто-то считает амебу высокоинтеллектуальной особью, ведь у нее даже нет нервной системы в привычном нам понимании. Однако группа ученых из Токийского университета Кейо использовала этот одноклеточный организм для решения математической задачки. И на удивление амеба справилась с ней быстрее и эффективнее, чем мощный компьютер.

Задачка, которую предстояло решить, носит название «задача комивояжера». Она заключается в следующем: представьте, что вы коммивояжер, переезжающий из города в город, продавая свои товары. Вам нужно быть максимально эффективным, чтобы заработать как можно больше денег, поэтому вы хотите найти кратчайший путь, который позволит вам попасть в каждый город на маршруте следования. При этом не существует математической формулы, чтобы найти наиболее эффективный маршрут. Единственный способ решить проблему — вычислить длину каждого маршрута и посмотреть, какой из них самый короткий.

Но и это еще не все: расчет расстояния становится тем сложнее, чем больше городов добавляется к маршруту. Для 4 городов есть только 3 маршрута. А вот для 6 их уже 360. Это делает «задачу коммивояжера» одной из проблем, которую ученые называют «NP hard». То есть проблема, сложность которых возрастает по экспоненте даже из-за незначительного увеличения показателей. К такому же типу задач относится, например, майнинг криптовалют, поэтому находить их решение довольно важно на сегодняшний день.

В своей работе японские ученые использовали амебу Physarum polycephalum, а конкретнее — ее слизь, которую она распространяет в качестве «разведчика». Существо поместили в специальную камеру, в которой было множество каналов. В конце каждого из каналов исследователи разместили немного воды. Когда амеба получала воду — в одном из соседних каналов гас свет. Канал в данном случае был аналогом пути к городу из задачи.

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

«Механизм, который влияет на скорость принятия решения амебой и то, как она вычисляет наиболее короткий путь до сих пор остается загадкой. Выяснив это, мы сможем найти пути быстрого решения сложных вычислительных задач и даже улучшить системы безопасности.» — говорит ведущий автор исследования Масаши Аоно.



Subscribe

promo antony_w august 17, 2014 11:48 18
Buy for 10 tokens
Есть блог, в котором написано много постов про роботов: ссылка И там есть несколько статей о замене рабочих мест человека роботами: Уже к 2018 году роботы отберут у человека часть профессий Рабский труд без зарплаты Армия роботов: зачем она нужна обильной людьми Поднебесной и кому может…
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments