Бактерии решили задачу коммивояжера с 60 квадриллионами вариантов

Selectel опубликовал материал о том, как кишечная палочка помогла решить классическую задачу оптимизации маршрутов. Задача коммивояжера — найти кратчайший путь через 20 адресов и вернуться на склад — имеет 60 822 550 204 416 000 возможных вариантов объезда.

Для сравнения: столько секунд прошло бы за два миллиарда лет. В статье разобрано, как живые организмы решают такие задачи и на каком этапе подход упирается в ограничения.