Прежде чем вести страну через Гражданскую войну, до составления Манифеста об освобождении рабов и произнесения Геттисбергской речи, Авраам Линкольн работал адвокатом прерии в Спрингфилде, штат Иллинойс, и путешествовал по Восьмому судебному округу дважды в год на протяжении 16 лет. Служить окружным юристом действительно означало делать своеобразный круг – колесить по городам четырнадцати разных округов, проводя судебные разбирательства. Спланировать такую поездку представляло собой настоящую задачу: как посетить все нужные города, проехав как можно меньшее расстояние и не заезжая в один и тот же город дважды.

Это пример известной математикам и программистам задачи по оптимизации с заданными ограничениями: как найти единственный лучший вариант с рядом переменных при определенных заданных правилах и системе ведения счета. По сути, это самая известная задача по оптимизации из всех. Если бы ее изучали в XIX веке, она наверняка получила бы название «задача адвоката прерий», а если бы с ней впервые столкнулись в XX веке, то ее окрестили бы задачей по перемещениям беспилотника. Но, так же как и задача о секретаре, она появилась в середине XХ века под названием «задача о коммивояжере».

Задача о планировании маршрута не привлекала внимание математического сообщества до 1930-х годов, но, когда это случилось, задача была отомщена. Математик Карл Менгер упоминал о задаче почтового служащего в 1930 году, отмечая, что не существует более простого из известных решений, кроме как испытывать каждую возможность по очереди. Хасслер Уитни из Принстона обозначил эту проблему в 1934 году, тогда она и засела плотно в уме его друга математика Меррила Флада (который, как вы помните из главы 1, причастен к распространению первого решения задачи о секретаре). Когда Флад переехал в Калифорнию в 40-е годы, он передал эту задачу своим коллегам в Институте Айн Рэнд. Каноническое название задачи впервые было упомянуто в газетной публикации в 1949 году благодаря математику Джулии Робинсон. По мере обсуждения задачи в математических кругах она постепенно приобрела печальную известность. Множество величайших умов были ею одержимы, но никто, казалось, даже не начал двигаться в верном направлении, решая ее.

В задаче о коммивояжере вопрос заключается не в том, может ли компьютер (или математик) найти кратчайший путь: теоретически можно просто составить список всех возможностей и оценить каждую из них. Скорее, сложность состоит в том, что по мере роста количества городов список возможных маршрутов стремительно растет. Маршрут – это всего лишь последовательность городов, поэтому метод перебора всех маршрутов и приводит нас к той вселяющей ужас формуле О(n!) факториального времени – вычислительному эквиваленту попытки отсортировать колоду карт в нужном порядке, подбрасывая их в воздух.

Вопрос: а есть ли надежда на лучшее решение?

Десятилетия работы помогли добиться некоторых результатов в укрощении задачи о коммивояжере. К примеру, Флад писал в 1956 году, спустя более 20 лет после первой встречи с этой задачей: «Представляется очень вероятным, что нужен абсолютно другой подход относительно уже испробованных для успешного прохождения этой головоломки. По сути, может не существовать общего способа ее решения, и результаты, демонстрирующие невозможность решения, тоже ценны». Спустя 10 лет общее настроение было еще более унылым. «Я предполагаю, – писал Джек Эдмондс, – что не существует правильного алгоритма для решения задачи о коммивояжере».

Эти слова оказались пророческими.