Задача коммивояжера требует найти кратчайший маршрут через заданные точки. Для 20 адресов количество вариантов превышает 60 квадриллионов. Из-за комбинаторного взрыва перебор всех путей становится невозможным, однако эффективные алгоритмы, например Хелда-Карпа, позволяют решать задачу быстро.
На обычном ноутбуке алгоритм Хелда-Карпа находит решение для 12 точек за 17 миллисекунд, тогда как прямой перебор тратит 42 секунды. С ростом числа точек разрыв между методами увеличивается, так как эффективные алгоритмы исключают необходимость проверки большинства заведомо неоптимальных маршрутов.
В 2009 году исследователи Baumgardner et al. предложили использовать кишечную палочку для решения задач на графах. Метод кодирует ребра графа в ДНК-плазмидах, которые фермент Hin-рекомбиназа переставляет случайным образом. Флуоресцентные белки подсвечивают колонии, в которых собралась верная комбинация.
Биологический компьютер демонстрирует логарифмическое время вычислений благодаря делению бактерий, но сталкивается с физическими ограничениями. Для 20 городов потребовалось бы 4 кубометра бактериальной культуры, тогда как обычный Python-скрипт справляется с задачей за 22 секунды.
Экспоненциальный рост популяции бактерий требует пропорционального увеличения ресурсов. Хотя время решения задачи выглядит логарифмическим, объем необходимой биомассы растет экспоненциально. В итоге при увеличении сложности задачи биологический метод проигрывает классическим вычислительным мощностям.
