Эта задача решается с помощью проведения конечного числа попыток. Правила, благодаря которым число попыток станет ниже числа перестановок заданных точек, неизвестны. Правило, по которому следует двигаться из начальной точки в ближайшую к ней точку, затем в ближайшую к этой и т. д., в общем случае не дает кратчайшего пути.
Эта цитата показывает, что Менгер понимал две ключевые особенности этой задачи. Во-первых, алгоритм нахождения ответа существует. Можно просто рассмотреть все пути по очереди, рассчитать длину каждого и посмотреть, который из них окажется кратчайшим. Полное число возможных маршрутов в точности равно числу перестановок точек, которое конечно. Когда он писал, лучший алгоритм был неизвестен, но все понимали, что перебор всех возможных путей безнадежен, если городов больше дюжины, поскольку маршрутов слишком много. Во-вторых, он видел, что «очевидный» метод – из каждой точки двигаться к ближайшей – обычно не работает. Специалисты называют этот метод эвристическим алгоритмом ближайшего соседа. На рисунке показана одна из причин, по которым он не работает.
Одна из причин, по которым метод ближайшего соседа не работает. Начните с точки A и всегда переходите к ближайшей из точек, которые вы еще не посетили. Маршрут слева будет выглядеть как ABCDE. Однако маршрут справа – ACBDE – короче
Менгер шесть месяцев в 1930 и 1931 годах читал в Гарвардском университете лекции, часть из которых прослушал великий тополог Хасслер Уитни. Годом позже Уитни выступил с лекцией, где высказался о том, как следует подходить к поиску кратчайшего пути по всем 48 (на тот момент) штатам Америки. Некоторое время в математических кругах эту проблему называли «задачей 48 штатов», но потом кто-то придумал более изящное название «задача коммивояжера». В печати оно впервые было упомянуто в 1949 году в докладе Джулии Робинсон.
Менгер продолжал работать над задачей коммивояжера и родственными вопросами. В 1940 году Ласло Фейеш Тот заинтересовался, по существу, этой же задачей: нахождением кратчайшего пути через n точек единичного квадрата. В 1951 году Самюэл Верблунски доказал, что ответ составляет меньше чем 2 +√2 · 8n. Позже математики доказывали, что минимальная длина пути через n точек в фиксированной области не превышает определенной константы, умноженной на квадратный корень из n, причем величина константы с каждым разом все уменьшалась.
В конце 1940-х годов одной из ведущих организаций, занимавшихся исследованием операций, была RAND Corporation в Санта-Монике (штат Калифорния). Исследователи RAND немало сил посвятили решению родственной задачи о перевозках, и Джордж Данциг с Тьяллингом Купмансом высказали предположение, что их работа над тем, что сейчас называется линейным программированием, может иметь значение и для решения задачи коммивояжера. Линейное программирование – эффективный и практичный метод решения многих задач комбинаторной оптимизации. Это метод максимизации линейной комбинации переменных с ограничениями в виде неравенств, утверждающих, что другие их линейные комбинации должны быть положительными или отрицательными. Данциг придумал первый практический алгоритм – симплексный метод, широко используемый до сих пор. Неравенства определяют многомерный выпуклый многогранник, а алгоритм перемещает точку вдоль ребер этого многогранника до тех пор, пока величина, которую мы хотим максимизировать, увеличивается.
Первого по-настоящему значимого успеха в решении задачи коммивояжера добились в 1954 году исследователи RAND Данциг, Делберт Фалкерсон и Селмер Джонсон при помощи метода линейного программирования Данцига. Они адаптировали метод к решению именно этой задачи и предложили систематические новые методы, в частности использование «секущих плоскостей». В результате был найден нижний предел длины оптимального маршрута. Если вам удается находить маршрут лишь ненамного длиннее, то вы на правильном пути и внутреннее чутье не обманывает вас. Данциг, Фалкерсон и Джонсон воспользовались этими идеями, чтобы получить первое решение задачи коммивояжера для разумного числа городов, а именно найти кратчайший маршрут через 49 городов: по одному в каждом из 48 штатов США плюс столичный Вашингтон. Это, похоже, та самая задача, которую упоминал Уилкинсон в 1930-е годы, и определенно та самая, о которой писала Джулия Робинсон в 1949 году.