Амеба справилась с вычислениями лучше современного компьютера

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

Универсальной формулы для этого не существует. Единственный способ решить проблему — это рассчитать длину каждого из возможных маршрутов и выбрать из них самый короткий. Кроме того, с добавлением новых городов на этот маршрут сложность вычислений возрастает экспоненциально. Так, для 4 городов нужно построить всего 3 маршрута, а для 6 — уже 360. А если ваш путь предполагает посещение 10 и больше городов, то счет пойдет уже на миллионы.

Решение ученых из Университета Кейо отличается от всех прочих алгоритмов, разработанных исследователями. Причина тому — одноклеточное существо Physarum polycephalum, а именно его слизь. P. polycephalum сам по себе очень простой организм, который умеет делать две вещи: двигаться в сторону еды и прятаться от света. Миллионы лет эволюции сделали его аномально эффективным в выполнении обоих этих процессов.

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

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

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