Японские ученые узнали, что слизевик физарум многоголовый (Physarum polycephalum) способен скоро отыскать оптимальное ответ задачи коммивояжера. Результаты изучения окажут помощь создать аналоговые компьютеры, каковые будут обнаружить более качественные ответы NP-тяжёлых задач в отличие от классических цифровых компьютеров. Статья исследователей размещена в издании Royal Society Open Science.
Задача коммивояжера (англ. Travelling salesman problem, TSP) содержится в поиске самого удачного (малейшего) маршрута, проходящего через пара городов, наряду с этим любой город возможно посетить лишь раз и наряду с этим необходимо возвратиться в исходную точку. При громадном количестве городов задача не разрешиться методом несложного перебора любыми компьютерами кроме того за миллиарды лет, поскольку число маршрутов с числом городов растет экспоненциально. К примеру, при четырех городов существует три вероятных маршрута, а при восьми — уже 2520.
TSP относится к NP-тяжёлым задачам, и многие ученые уверены в том, что не существует метода, талантливого скоро (за полиномиальное время) отыскать правильное, а не приближенное ответ при громадном количестве входных данных. Существующие способы ответа разрешают отыскать приемлемый маршрут, что только ненамного дольше оптимального. В новой работе ученые продемонстрировали, что отыскать приближенное ответ с достаточной точностью может кроме того одноклеточный организм.
Исследователи поместили Physarum polycephalum вовнутрь чипа, что представляет собой круглую углубление с выходящими из нее 64 узкими каналами. В углубления и в каналах находится питательное вещество, и слизевик старается пробраться в них, дабы максимизировать поступление в клетку питательных веществ.