Задача коммивояжёра
Проблема путешествующего продавца (часто называемая TSP) - классическая алгоритмическая проблема в области вычислительной техники и исследования операций. Она ориентирована на оптимизацию. В этом контексте лучшее решение часто означает решение, которое дешевле, короче или быстрее. TSP является математической задачей. Легче всего она выражается в виде графика, описывающего расположение набора узлов.
Проблема путешествующего продавца была определена в 1800-х годах ирландским математиком У. Р. Гамильтоном и британским математиком Томасом Киркманом. Икосианская игра Гамильтона была рекреационной головоломкой, основанной на поиске цикла Гамильтона. Общая форма TSP, по-видимому, были впервые изучены математиками во время 1930-х годов в Вене и в Гарварде, в частности, Карл Менгер. Менгер определяет проблему, рассматривает очевидный алгоритм брутальной силы и наблюдает неоптимальность эвристики ближайшего соседа:
Обозначим задачей посланника (так как на практике этот вопрос должен решаться каждым почтальоном, во всяком случае, и многими путешественниками) задачу найти для многих точек, чье парное расстояние известно, кратчайший маршрут, соединяющий эти точки. Конечно, эта проблема решается бесконечно многими испытаниями. Неизвестны правила, по которым количество испытаний опускалось бы ниже количества перестановок в заданных точках. Правило, по которому нужно сначала пройти от начальной точки до ближайшей, затем до ближайшей точки и т.д., в общем случае, не дает кратчайшего маршрута.
Хасслер Уитни из Принстонского университета вскоре представил проблему с именем продавца путешествий.
Продавец хочет посетить все города, A, B, C и D. Как лучше всего это сделать (самые дешевые авиабилеты и минимальное время путешествия)?
Уильям Роуэн Гамильтон
Оптимальный маршрут продавца с посещением 15 крупнейших городов Германии. Представленный маршрут является самым коротким из 43 589 145 600 возможных.
Заявление о проблеме
Проблема коммивояжера-путешественника" описывает коммивояжера, который должен путешествовать между городами N. Порядок, в котором он это делает, его не волнует, при условии, что он посещает каждый раз во время поездки и заканчивает там, где был сначала. Каждый город связан с другими близлежащими городами или узлами, самолетами, автомобильным или железнодорожным транспортом. Каждое из этих связей между городами имеет один или несколько весов (или стоимость). Стоимость описывает, насколько "трудно" пересечь этот край на графике, и может быть дана, например, стоимостью авиабилета или билета на поезд, или, возможно, длиной края, или временем, необходимым для завершения обхода. Продавец хочет сохранить как стоимость проезда, так и расстояние, на которое он путешествует, на как можно более низком уровне.
Проблема путешествующего продавца типична для большого класса "трудных" задач оптимизации, которые годами интриговали математиков и ученых-вычислителей. Самое главное, что она имеет прикладное применение в науке и технике. Например, при изготовлении печатной платы важно определить наилучший порядок, в котором лазер будет сверлить тысячи отверстий. Эффективное решение этой проблемы снижает производственные затраты производителя.
Трудность
В общем, проблему коммивояжера путешественников решить сложно. Если есть способ разбить эту проблему на более мелкие проблемы с компонентами, то компоненты будут по крайней мере такими же сложными, как и оригинальные. Это то, что компьютерные ученые называют NP-жесткими проблемами.
Многие люди изучали эту проблему. Самое простое (и самое дорогое) решение - это просто попробовать все возможности. Проблема заключается в том, что для N городов у вас есть (N-1) факториальные возможности. Это означает, что только для 10 городов можно попробовать более 180 тысяч комбинаций (так как стартовый город определен, то перестановки могут быть и на остальных девяти). Мы считаем только половину, так как каждый маршрут имеет одинаковый маршрут в обратном направлении с одинаковой длиной или стоимостью. 9! / 2 = 181 440
- Точные решения проблемы могут быть найдены с использованием алгоритмов ветвления и привязки. В настоящее время это возможно в 85 900 городах.
- Эвристические подходы используют набор руководящих правил для выбора следующего узла. Но поскольку эвристика приводит к аппроксимации, она не всегда дает оптимальное решение, хотя высококачественная допустимая эвристика может найти полезное решение за долю времени, необходимого для полной грубой силы задачи. Примером эвристики для узла будет суммирование того, сколько непроверенных узлов находятся "рядом" с соединенным узлом. Это могло бы побудить продавца посетить группу близко расположенных узлов, сгруппированных вместе, прежде чем перейти к другому естественному кластеру на графике. См. алгоритмы Монте-Карло и Лас-Вегаса.
Вопросы и ответы
В: Что такое "проблема коммивояжера"?
О: Проблема путешествующего продавца (Traveling Salesman Problem, TSP) - это классическая алгоритмическая проблема в области информатики и исследования операций. Она сосредоточена на оптимизации, причем лучшие решения часто означают более дешевые, короткие или быстрые решения.
В: Как выражается TSP?
О: TSP легче всего выразить в виде графа, описывающего расположение множества узлов.
В: Кто впервые определил TSP?
О: Проблема путешествующего продавца была определена в 1800-х годах ирландским математиком У. Р. Гамильтоном и британским математиком Томасом Киркманом.
В: Кто продолжил ее изучение в 1930-х годах?
О: В 1930-х годах математики Карл Менгер в Вене и Гарварде изучали ее дальше.
В: Что вскоре после этого представил Хасслер Уитни?
О: Хасслер Уитни из Принстонского университета ввел название "проблема коммивояжера" вскоре после ее определения.
В: Что означает "лучшее решение" в данном контексте?
О: В данном контексте лучшее решение часто означает решение, которое дешевле, короче или быстрее.
В: Какой алгоритм Менгер считал очевидным при изучении TSP?
О: Менгер считал очевидным алгоритм грубой силы при изучении TSP и заметил, что использование эвристики ближайшего соседа не всегда дает оптимальные результаты.
