Задача о планировании маршрута не привлекала внимание математического сообщества до 1930-х годов, но, когда это случилось, задача была отомщена. Математик Карл Менгер упоминал о задаче почтового служащего в 1930 году, отмечая, что не существует более простого из известных решений, кроме как испытывать каждую возможность по очереди. Хасслер Уитни из Принстона обозначил эту проблему в 1934 году, тогда она и засела плотно в уме его друга математика Меррила Флада (который, как вы помните из главы 1, причастен к распространению первого решения задачи о секретаре). Когда Флад переехал в Калифорнию в 40-е годы, он передал эту задачу своим коллегам в Институте Айн Рэнд. Каноническое название задачи впервые было упомянуто в газетной публикации в 1949 году благодаря математику Джулии Робинсон. По мере обсуждения задачи в математических кругах она постепенно приобрела печальную известность. Множество величайших умов были ею одержимы, но никто, казалось, даже не начал двигаться в верном направлении, решая ее.
В задаче о коммивояжере вопрос заключается не в том, может ли компьютер (или математик) найти кратчайший путь: теоретически можно просто составить список всех возможностей и оценить каждую из них. Скорее, сложность состоит в том, что по мере роста количества городов список возможных маршрутов стремительно растет. Маршрут – это всего лишь последовательность городов, поэтому метод перебора всех маршрутов и приводит нас к той вселяющей ужас формуле О(n!) факториального времени – вычислительному эквиваленту попытки отсортировать колоду карт в нужном порядке, подбрасывая их в воздух.
Вопрос: а есть ли надежда на лучшее решение?
Десятилетия работы помогли добиться некоторых результатов в укрощении задачи о коммивояжере. К примеру, Флад писал в 1956 году, спустя более 20 лет после первой встречи с этой задачей: «Представляется очень вероятным, что нужен абсолютно другой подход относительно уже испробованных для успешного прохождения этой головоломки. По сути, может не существовать общего способа ее решения, и результаты, демонстрирующие невозможность решения, тоже ценны». Спустя 10 лет общее настроение было еще более унылым. «Я предполагаю, – писал Джек Эдмондс, – что не существует правильного алгоритма для решения задачи о коммивояжере».
Эти слова оказались пророческими.
В середине 1960-х годов Эдмондс, сотрудник Национального института стандартов и технологии, и Алан Кобхэм из IBM сформулировали рабочее определение того, что делает задачу решаемой или наоборот. Они доказывали утверждение, ныне известное как гипотеза Кобхэма и Эдмондса: алгоритм считается эффективным, если его действие происходит в так называемом полиномиальном времени, а именно O(