Японские ученые выяснили, что слизевик физарум многоголовый (Physarum polycephalum) способен быстро найти оптимальное решение задачи коммивояжера. Результаты исследования помогут разработать аналоговые компьютеры, которые будут находить более качественные решения NP-трудных задач в отличие от традиционных цифровых компьютеров. Статья исследователей опубликована в журнале Royal Society Open Science.
Узнайте больше в полной версии ➞Задача коммивояжера (англ. Travelling salesman problem, TSP) заключается в поиске самого выгодного (кратчайшего) маршрута, проходящего через несколько городов, при этом каждый город можно посетить только раз и при этом нужно вернуться в исходную точку. При большом количестве городов задача не может быть решена путем простого перебора любыми компьютерами даже за миллиарды лет, так как число маршрутов с числом городов растет экспоненциально. Например, в случае четырех городов существует три возможных маршрута, а в случае восьми — уже 2520.
TSP относится к NP-трудным задачам, и многие ученые считают, что не существует алгоритма, способного быстро (за полиномиальное время) найти точное, а не приближенное решение при большом объеме входных данных. Существующие методы решения позволяют найти приемлемый маршрут, который лишь ненамного длиннее оптимального. В новой работе ученые показали, что найти приближенное решение с достаточной точностью может даже одноклеточный организм.
Исследователи поместили Physarum polycephalum внутрь чипа, который представляет собой круглую выемку с выходящими из нее 64 узкими каналами. Внутри выемки и в каналах находится питательное вещество, и слизевик старается проникнуть в них, чтобы максимизировать поступление в клетку питательных веществ.
Каждый из восьми городов (A, B, C и другие) в задаче представлен восемью каналами с порядковыми номерами, показывающими, каким по счету может быть город при посещении коммивояжером. Когда слизевик проникает в город A с номером 3, во всех остальных каналах с тем же номером (B3, С3) загорается свет, отпугивающий слизевика. Таким образом, предотвращается одновременное посещение городов. Кроме того, в компьютер, управляющий светом, заложена информация о расстоянии между городами. Если слизевик после посещения города А начинает проникать в каналы В и С, но при этом С находится от А ближе, чем В, то в последнем также загорается свет, отпугивающий плазмоид. Так достигается выбор оптимального маршрута.
По словам ученых, существует закон, согласно которому слизевик потребляет желатин для расширения своего тела с постоянной скоростью (х). Тогда он займет площадь n, характерную для решения задачи, за время, равное n/x. То есть слизевик решит задачу с n городами за линейное время. Однако для ученых остается загадкой, как физаруму удается это делать. Исследователи полагают, что выросты клетки каким-то образом обмениваются информацией, синхронизируясь друг с другом.