Йэн Стюарт – Это база: Зачем нужна математика в повседневной жизни (страница 10)

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

И здесь на сцену выходит переносимость математики. Применение задачи коммивояжера не ограничивается поездками между городами или по улицам большого города. На стене нашей гостиной висит большой квадрат из черной ткани с вышитым на нем из блесток элегантным спиральным узором, основанным на знаменитых числах Фибоначчи. Дизайнер называет этот узор «блестками Фибоначчи». Изготовлен он был при помощи машины под управлением компьютера, способной вышить все что угодно размером вплоть до покрывала на большую кровать. Игла, делающая стежки, прикреплена к стержню, который перемещает ее в продольном направлении, а сам стержень может еще двигаться в поперечном направлении. Сочетание этих двух движений позволяет переместить иглу в любую точку. По чисто практическим причинам (потеря времени, лишняя нагрузка на машину, шум) никто не хочет, чтобы игла скакала туда-сюда по всему полотну, так что суммарное пройденное ею расстояние необходимо минимизировать. Получается задача, очень похожая на задачу коммивояжера. Родословная таких машин восходит к ранней компьютерной графике и к устройству, известному как плоттер, где перо двигалось примерно так же.

Аналогичных вопросов хватает и в естественных науках. Давным-давно видные астрономы имели собственные телескопы или пользовались ими совместно с несколькими коллегами. Эти телескопы можно было без труда направлять на новые небесные тела и таким образом импровизировать. Теперь все не так, ведь телескопы, которыми пользуются астрономы, громадны, невероятно дороги и доступ к ним осуществляется онлайн. Наведение телескопа на новый объект требует времени, а пока агрегат движется, вести наблюдения невозможно. Выстройте цели в неверном порядке, и зря потратите много времени на то, чтобы повернуть телескоп на большой угол, а потом обратно, если хотите наблюдать объект, расположенный рядом с начальной точкой. При секвенировании ДНК фрагментарные последовательности ДНК-оснований необходимо соединять в определенном порядке, и этот порядок нужно оптимизировать, чтобы избежать напрасных трат компьютерного времени.

Среди других применений можно назвать и эффективное прокладывание авиамаршрутов, и разработку и производство компьютерных микрочипов и печатных плат. Приближенные решения задачи коммивояжера используются для нахождения эффективных маршрутов доставки еды нуждающимся (программа Meals on Wheels) и оптимизации доставки крови в больницы. Один из вариантов задачи коммивояжера засветился даже в программе «Звездных войн» или, как ее правильнее называть, в гипотетической Стратегической оборонной инициативе президента США Рональда Рейгана, где мощный лазер, находящийся на околоземной орбите, должен был наводиться на ряд приближающихся ядерных ракет.

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

Эта задача решается с помощью проведения конечного числа попыток. Правила, благодаря которым число попыток станет ниже числа перестановок заданных точек, неизвестны. Правило, по которому следует двигаться из начальной точки в ближайшую к ней точку, затем в ближайшую к этой и т. д., в общем случае не дает кратчайшего пути.

Эта цитата показывает, что Менгер понимал две ключевые особенности этой задачи. Во-первых, алгоритм нахождения ответа существует. Можно просто рассмотреть все пути по очереди, рассчитать длину каждого и посмотреть, который из них окажется кратчайшим. Полное число возможных маршрутов в точности равно числу перестановок точек, которое конечно. Когда он писал, лучший алгоритм был неизвестен, но все понимали, что перебор всех возможных путей безнадежен, если городов больше дюжины, поскольку маршрутов слишком много. Во-вторых, он видел, что «очевидный» метод – из каждой точки двигаться к ближайшей – обычно не работает. Специалисты называют этот метод эвристическим алгоритмом ближайшего соседа. На рисунке показана одна из причин, по которым он не работает.

Одна из причин, по которым метод ближайшего соседа не работает. Начните с точки 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 году.

В 1956 году пионер исследования операций Меррилл Флуд заявил, что задача коммивояжера сложна. Возникает ключевой вопрос: насколько сложна? Чтобы ответить, мы должны вернуться к P и NP – показателям вычислительной сложности ценой миллион долларов. Похоже, что Флуд был прав, причем очень сильно.