antfor.ru
Группа исследователей из Университета Кейо в Токио доказала, что амеба может решать знаменитую «задачу коммивояжера» с близкими к правильным результатами. И то, как она это делает, позволяет ей при определенных условиях обогнать по скорости вычислений компьютер. Необычайно умное существо называется Physarum polycephalum.
Задача коммивояжера заключается в том, что нужно рассчитать кратчайший маршрут между базой и несколькими покупателями, которых нужно объехать и доставить им товар. Ее отличает экспоненциальный рост сложности – при 4 покупателях есть лишь 3 возможных решения, но при 6 покупателях количество вариантов возрастает до 360. В общем виде задача была решена в 90-е годы, и сегодня можно получить результат даже для миллионов покупателей, что востребовано в международной логистике.
Амеба Physarum polycephalum вечно голодна и боится солнечного света. Ученые создали подобие лабиринта – в емкости есть 64 сектора, где расположена пища, а сама амеба размещается в центре и должна сместиться, чтобы добраться до еды. Над лабиринтом смонтирована система освещения, которая формирует световые «барьеры» на пути к еде. Нейросеть управляет освещением так, чтобы оставлять в тени для амебы заданное количество целей и подсвечивать пути между ними тем ярче, чем больше расстояние. То есть, амебе нужно найти кратчайшие пути между объектами, чтобы покушать и избежать света.
Выяснилось, что микроорганизм почти всегда решает эту задачу идеально точно. И скорость принятия решений увеличивается линейно при усложнении задачи, хотя в IT-науке рост вычислительных операций в этом случае должен расти по экспоненте. Это трудно объяснить с позиции науки, поэтому эксперименты продолжаются. Сейчас заказаны пробирки с архитектурой для имитации десятков тысяч объектов-кормушек – интересно наблюдать за поведением амебы при таком лавинообразном усложнении условий задачи.
