Время коммивояжеров давно прошло. В век интернета компании редко продают свой товар, отправляя путешествовать по городам и весям человека с чемоданом образцов. Они выставляют свои товары в Сети. Но, как обычно (все та же непостижимая эффективность), задача коммивояжера не устарела из-за этих изменений в культуре. Онлайн-продажи растут экспоненциально, потребность в эффективных способах определения маршрутов и графиков приобретает все большее значение для доставки всего, от посылок до пиццы и заказов в супермаркетах. Задачу коммивояжера можно было бы, наверное, переименовать в задачу курьера-доставщика: какой маршрут будет наилучшим для фургончика, доставляющего заказы?
И здесь на сцену выходит переносимость математики. Применение задачи коммивояжера не ограничивается поездками между городами или по улицам большого города. На стене нашей гостиной висит большой квадрат из черной ткани с вышитым на нем из блесток элегантным спиральным узором, основанным на знаменитых числах Фибоначчи. Дизайнер называет этот узор «блестками Фибоначчи». Изготовлен он был при помощи машины под управлением компьютера, способной вышить все что угодно размером вплоть до покрывала на большую кровать. Игла, делающая стежки, прикреплена к стержню, который перемещает ее в продольном направлении, а сам стержень может еще двигаться в поперечном направлении. Сочетание этих двух движений позволяет переместить иглу в любую точку. По чисто практическим причинам (потеря времени, лишняя нагрузка на машину, шум) никто не хочет, чтобы игла скакала туда-сюда по всему полотну, так что суммарное пройденное ею расстояние необходимо минимизировать. Получается задача, очень похожая на задачу коммивояжера. Родословная таких машин восходит к ранней компьютерной графике и к устройству, известному как плоттер, где перо двигалось примерно так же.
Аналогичных вопросов хватает и в естественных науках. Давным-давно видные астрономы имели собственные телескопы или пользовались ими совместно с несколькими коллегами. Эти телескопы можно было без труда направлять на новые небесные тела и таким образом импровизировать. Теперь все не так, ведь телескопы, которыми пользуются астрономы, громадны, невероятно дороги и доступ к ним осуществляется онлайн. Наведение телескопа на новый объект требует времени, а пока агрегат движется, вести наблюдения невозможно. Выстройте цели в неверном порядке, и зря потратите много времени на то, чтобы повернуть телескоп на большой угол, а потом обратно, если хотите наблюдать объект, расположенный рядом с начальной точкой. При секвенировании ДНК фрагментарные последовательности ДНК-оснований необходимо соединять в определенном порядке, и этот порядок нужно оптимизировать, чтобы избежать напрасных трат компьютерного времени.
Среди других применений можно назвать и эффективное прокладывание авиамаршрутов, и разработку и производство компьютерных микрочипов и печатных плат. Приближенные решения задачи коммивояжера используются для нахождения эффективных маршрутов доставки еды нуждающимся (программа Meals on Wheels) и оптимизации доставки крови в больницы. Один из вариантов задачи коммивояжера засветился даже в программе «Звездных войн» или, как ее правильнее называть, в гипотетической Стратегической оборонной инициативе президента США Рональда Рейгана, где мощный лазер, находящийся на околоземной орбите, должен был наводиться на ряд приближающихся ядерных ракет.
Карл Менгер, работы которого в настоящее время рассматриваются как предвестники фракталов, пожалуй, первым из математиков написал о задаче коммивояжера, и было это в 1930 году. Он рассматривал эту задачу под совершенно другим углом, поскольку в то время изучал длины кривых с точки зрения чистой математики. В то время длина кривой определялась как наибольшая величина, получаемая путем сложения длин участков любой ее полигональной аппроксимации, вершинами которой является конечное множество точек, проходимых в том же порядке, в каком они лежат на кривой. Менгер доказал, что тот же ответ получится, если заменить аппроксимирующую ломаную линию конечным множеством точек на кривой и найти минимальное суммарное расстояние вдоль любой ломаной с этими вершинами, в каком бы порядке они ни проходились. Связь с задачей коммивояжера здесь в том, что кратчайший путь Менгера – тот, что является решением задачи коммивояжера, если вершины ломаной рассматривать как города. Менгер назвал это «задачей гонца», заявив, что она применима не только к торговцам, но и к почтальонам, и написал: