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