Задача коммивояжера - Travelling salesman problem

Решение задачи коммивояжера: черной линией обозначена кратчайшая петля, соединяющая каждую красную точку.

Задача коммивояжера (также называется проблемой путешествия продавцов или TSP ) задает следующий вопрос: «Данный список городов и расстояние между каждой парой городов, что это самый короткий маршрут, посещения каждым город ровно один раз и возвращается к город происхождения? " Это NP-сложная задача комбинаторной оптимизации , важная для теоретической информатики и исследования операций .

Путешествия проблема покупателя и проблема транспортного средства маршрутизации являются обобщения TSP.

В теории вычислительной сложности решающая версия TSP (где задана длина L , задача состоит в том, чтобы решить, имеет ли граф обход не более L ) принадлежит к классу NP-полных задач. Таким образом, возможно, что время работы любого алгоритма TSP в наихудшем случае увеличивается суперполиномиально (но не более чем экспоненциально ) с увеличением количества городов.

Эта проблема была впервые сформулирована в 1930 году и является одной из наиболее интенсивно изучаемых проблем оптимизации. Он используется в качестве эталона для многих методов оптимизации. Несмотря на то, что проблема сложна в вычислительном отношении, известно множество эвристик и точных алгоритмов , так что некоторые экземпляры с десятками тысяч городов могут быть решены полностью, и даже проблемы с миллионами городов могут быть аппроксимированы с точностью до небольшой доли 1%.

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

История

Истоки проблемы коммивояжера неясны. Справочник для коммивояжеров 1832 года упоминает эту проблему и включает примеры туров по Германии и Швейцарии , но не содержит математической обработки.

Уильям Роуэн Гамильтон

Задача коммивояжера была математически сформулирована в XIX веке ирландским математиком У. Р. Гамильтоном и британским математиком Томасом Киркманом . Икозианская игра Гамильтона была развлекательной головоломкой, основанной на нахождении гамильтонова цикла . Общая форма TSP, по-видимому, была впервые изучена математиками в 1930-х годах в Вене и Гарварде, особенно Карлом Менгером , который определяет проблему, рассматривает очевидный алгоритм грубой силы и наблюдает неоптимальность ближайшего эвристика соседа:

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

Впервые это было математически рассмотрено в 1930-х годах Меррилом М. Фладом, который пытался решить проблему маршрутизации школьного автобуса. Хасслер Уитни из Принстонского университета вызвал интерес к проблеме, которую он назвал «проблемой 48 состояний». Самой ранней публикацией, в которой использовалась фраза «задача коммивояжера», был отчет корпорации RAND от 1949 года Джулии Робинсон «О гамильтоновой игре (задача коммивояжера)».

В 1950-х и 1960-х годах проблема становилась все более популярной в научных кругах Европы и США после того, как корпорация RAND в Санта-Монике предложила призы за шаги в решении проблемы. Заметный вклад внесли Джордж Данциг , Делберт Рэй Фулкерсон и Селмер М. Джонсон из корпорации RAND, которые выразили проблему как целочисленную линейную программу и разработали метод секущей плоскости для ее решения. Они написали то, что считается основополагающей статьей по этому вопросу, в которой с помощью этих новых методов они разрешили пример с 49 городами до оптимальности, построив тур и доказав, что никакой другой тур не может быть короче. Данциг, Фулкерсон и Джонсон, однако, предположили, что, имея почти оптимальное решение, мы можем найти оптимальность или доказать оптимальность, добавив небольшое количество дополнительных неравенств (сокращений). Они использовали эту идею для решения своей первоначальной задачи 49 городов с помощью струнной модели. Они обнаружили, что им нужно всего 26 сокращений, чтобы решить их 49 городских проблем. Хотя эта статья не давала алгоритмического подхода к проблемам TSP, идеи, заложенные в ней, были необходимы для последующего создания точных методов решения TSP, хотя для поиска алгоритмического подхода к созданию этих сокращений потребовалось 15 лет. Данциг, Фулкерсон и Джонсон, возможно, впервые использовали не только методы секущей плоскости, но и алгоритмы ветвей и границ .

В 1959 году Джиллиан Бирдвуд , Дж. Х. Халтон и Джон Хаммерсли опубликовали в журнале Кембриджского философского общества статью под названием «Кратчайший путь через многие точки». Теорема Бирдвуда – Халтона – Хаммерсли дает практическое решение проблемы коммивояжера. Авторы вывели асимптотическую формулу для определения длины кратчайшего маршрута для продавца, который начинает свой путь из дома или офиса и посещает фиксированное количество мест, прежде чем вернуться в начало.

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

В 1976 году Христофидес и Сердюков независимо друг от друга сделали большой шаг вперед в этом направлении: алгоритм Христофидеса-Сердюкова дает решение, которое в худшем случае не более чем в 1,5 раза длиннее оптимального решения. Поскольку алгоритм был простым и быстрым, многие надеялись, что он уступит место почти оптимальному методу решения. Однако надежды на улучшение не оправдались немедленно, и Христофидес-Сердюков оставался методом с наилучшим наихудшим сценарием до 2011 года, когда был разработан (очень) немного улучшенный алгоритм аппроксимации для подмножества «графических» TSP. В 2020 году это крошечное улучшение было расширено до полного (метрического) TSP.

Ричард М. Карп показал в 1972 году, что проблема гамильтонова цикла является NP-полной , что подразумевает NP-трудность TSP. Это дало математическое объяснение очевидной вычислительной сложности поиска оптимальных маршрутов.

Большой прогресс был достигнут в конце 1970-х и 1980-х годах, когда Грёчелю, Падбергу, Ринальди и другим удалось точно решить примеры с 2392 городами, используя плоскость сечения и ветвь и границу .

В 1990-х годах Эпплгейт , Биксби , Хватал и Кук разработали программу Concorde , которая использовалась во многих последних решениях для звукозаписи. Герхард Райнельт опубликовал TSPLIB в 1991 году, сборник тестов различной сложности, который использовался многими исследовательскими группами для сравнения результатов. В 2006 году Кук и другие вычислили оптимальный тур по экземпляру с 85 900 городами, заданному проблемой компоновки микрочипа, которая в настоящее время является крупнейшим решенным экземпляром TSPLIB. Для многих других случаев с миллионами городов можно найти решения, которые гарантированно находятся в пределах 2–3% от оптимального маршрута.

Описание

Как проблема с графом

Симметричный ТСП с четырьмя городами

TSP можно смоделировать как неориентированный взвешенный граф , в котором города являются вершинами графа , пути - его ребрами , а расстояние пути - весом ребра. Это задача минимизации, которая начинается и заканчивается в указанной вершине после посещения каждой другой вершины ровно один раз. Часто модель представляет собой полный граф (т.е. каждая пара вершин соединена ребром). Если между двумя городами нет пути, добавление достаточно длинного ребра завершит граф, не влияя на оптимальный маршрут.

Асимметричный и симметричный

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

Связанные проблемы

  • Эквивалентная формулировка с точки зрения теории графов : для полного взвешенного графа (где вершины будут представлять города, края будут представлять дороги, а веса будут представлять собой стоимость или расстояние этой дороги), найдите гамильтонов цикл с наименьший вес.
  • Требование возврата к исходному городу не меняет вычислительную сложность задачи, см гамильтонова проблема пути .
  • Другая связанная с этим проблема - это проблема коммивояжера « Узкое место» (TSP): найти гамильтонов цикл в взвешенном графе с минимальным весом самого весомого ребра . Например, избегать узких улиц с большими автобусами. Проблема имеет немалое практическое значение, помимо очевидной транспортно-логистической сферы. Классический пример - производство печатных плат : планирование маршрута сверлильного станка для сверления отверстий в печатной плате. В роботизированной обработке или сверлении «города» - это детали, которые нужно обработать, или отверстия (разных размеров), которые нужно просверлить, а «стоимость проезда» включает время на переоснащение робота (задача упорядочивания заданий на одной машине).
  • Обобщенная задача коммивояжера , также известная как «путешествующая проблема политик», имеет дело с «состояниями» , которые имеют (один или более) «городами» и торговый агент должен посетить ровно один «город» от каждого «государства». Одно приложение встречается при заказе решения проблемы режущего материала , чтобы свести к минимуму замену ножей. Другой касается сверления при производстве полупроводников , см., Например, патент США 7054798 . Нун и Бин продемонстрировали, что обобщенная задача коммивояжера может быть преобразована в стандартную задачу коммивояжера с тем же числом городов, но с модифицированной матрицей расстояний .
  • Проблема последовательного упорядочивания связана с проблемой посещения набора городов, в которых существуют отношения приоритета между городами.
  • Часто задаваемый вопрос на собеседовании в Google - как маршрутизировать данные между узлами обработки данных; маршруты различаются по времени для передачи данных, но узлы также различаются своей вычислительной мощностью и хранилищем, что усугубляет проблему, куда отправлять данные.
  • Проблема путешествующего покупателя касается покупателя, которому поручено приобрести набор продуктов. Он может покупать эти товары в нескольких городах, но по разным ценам, и не во всех городах предлагаются одинаковые товары. Цель состоит в том, чтобы найти маршрут между подмножеством городов, который минимизирует общую стоимость (стоимость поездки + стоимость покупки) и позволяет покупать все необходимые продукты.

Формулировки целочисленного линейного программирования

ТСП может быть сформулирован в виде целочисленных линейной программы . Известно несколько составов. Двумя примечательными формулировками являются формулировка Миллера – Такера – Землина (MTZ) и формула Данцига – Фулкерсона – Джонсона (DFJ). Состав DFJ сильнее, хотя формула MTZ все еще полезна в определенных условиях.

Формулировка Миллера – Таккера – Землина

Обозначьте города цифрами и определите:

Ибо пусть будет фиктивной переменной и, наконец, примем расстояние от города до города . Тогда TSP можно записать в виде следующей задачи целочисленного линейного программирования:

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

Чтобы доказать, что каждое допустимое решение содержит только одну замкнутую последовательность городов, достаточно показать, что каждый субтур в допустимом решении проходит через город 1 (отмечая, что равенства гарантируют, что такой тур может быть только один). Ведь если просуммировать все неравенства, соответствующие для любого подэтапа из k шагов, не проходящего через город 1, мы получим:

противоречие.

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

Не теряя общности, определите тур как начинающийся (и заканчивающийся) в городе 1. Выберите, будет ли город посещаться по шагу . потом

поскольку не может быть больше и не может быть меньше 1; следовательно, ограничения выполняются всякий раз , когда For , мы имеем:

удовлетворяющий ограничению.

Формулировка Данцига – Фулкерсона – Джонсона

Обозначьте города цифрами 1,…, n и определите:

Возьмем расстояние от города i до города j . Тогда TSP можно записать в виде следующей задачи целочисленного линейного программирования:

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

Вычисление решения

Традиционные направления атаки для NP-сложных задач следующие:

  • Разработка точных алгоритмов , которые достаточно быстро работают только для небольших задач.
  • Разработка «неоптимальных» или эвристических алгоритмов , т. Е. Алгоритмов , которые предоставляют приближенные решения в разумные сроки.
  • Поиск особых случаев для проблемы («подзадач»), для которых возможны либо более точные, либо более точные эвристики.

Точные алгоритмы

Самым прямым решением было бы попробовать все перестановки (упорядоченные комбинации) и посмотреть, какая из них самая дешевая (используя поиск грубой силы ). Время выполнения этого подход лежит в пределах полиномиального фактора , тем факториал числа городов, поэтому это решение становится непрактичным даже только 20 городов.

Одним из первых приложений динамического программирования является алгоритм Хельда – Карпа, который решает проблему во времени . Эта граница также была достигнута с помощью исключения-включения в попытке предшествовать подходу динамического программирования.

Решение симметричной TSP с 7 городами с использованием поиска методом перебора. Примечание: количество перестановок: (7−1)! / 2 = 360

Уточнение этих временных рамок кажется трудным. Например, не было определено, существует ли точный алгоритм для TSP, который выполняется во времени .

Другие подходы включают:

  • Различные алгоритмы ветвей и границ , которые можно использовать для обработки TSP, содержащих 40–60 городов.
Решение TSP с 7 городами с использованием простого алгоритма ветвей и границ. Примечание: количество перестановок намного меньше, чем при поиске методом грубой силы.

Точное решение для 15 112 немецких городов из TSPLIB было найдено в 2001 году с использованием метода секущих плоскостей, предложенного Джорджем Данцигом , Рэем Фулкерсоном и Сельмером М. Джонсоном в 1954 году, основанным на линейном программировании . Расчеты проводились на сети 110 процессоров , расположенных в Университете Райса и Принстонского университета . Общее время вычислений было эквивалентно 22,6 года на одном процессоре Alpha 500 МГц . В мае 2004 года проблема коммивояжера о посещении всех 24 978 городов Швеции была решена: был найден тур протяженностью около 72 500 километров, и было доказано, что более короткого тура не существует. В марте 2005 года задача коммивояжера о посещении всех 33 810 точек на печатной плате была решена с помощью Concorde TSP Solver : был найден маршрут длиной 66 048 945 единиц, и было доказано, что более короткого маршрута не существует. Вычисление заняло приблизительно 15,7 CPU-лет (Cook et al. 2006). В апреле 2006 г. экземпляр с 85 900 точками был решен с использованием Concorde TSP Solver , что потребовало более 136 процессорных лет, см. Applegate et al. (2006) .

Эвристические и аппроксимационные алгоритмы

Были разработаны различные эвристические и аппроксимационные алгоритмы , которые быстро дают хорошие решения. К ним относится многофрагментный алгоритм . Современные методы позволяют находить решения чрезвычайно больших проблем (миллионы городов) в разумные сроки, которые с высокой вероятностью отклоняются от оптимального решения всего на 2–3%.

Различают несколько категорий эвристики.

Конструктивная эвристика

Алгоритм ближайшего соседства для TSP с 7 городами. Решение меняется по мере изменения начальной точки.

Ближайший сосед (NN) алгоритмжадный алгоритм ) позволяет приказчику выбрать ближайший Непосещенный город , как его следующий шаг. Этот алгоритм быстро дает эффективный короткий маршрут. Для N городов, случайно распределенных на плоскости, алгоритм в среднем дает путь на 25% длиннее кратчайшего из возможных. Однако существует множество специально организованных распределений городов, по которым алгоритм NN дает наихудший маршрут. Это верно как для асимметричных, так и для симметричных TSP. Rosenkrantz et al. показал, что алгоритм NN имеет коэффициент аппроксимации для случаев, удовлетворяющих неравенству треугольника. Вариант алгоритма NN, называемый оператором ближайшего фрагмента (NF), который соединяет группу (фрагмент) ближайших непосещаемых городов, может находить более короткие маршруты с последовательными итерациями. Оператор NF также может применяться к начальному решению, полученному с помощью алгоритма NN, для дальнейшего улучшения элитарной модели, где принимаются только лучшие решения.

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

Другая конструктивная эвристика , Match Twice and Stitch (MTS), выполняет два последовательных сопоставления , где второе сопоставление выполняется после удаления всех краев первого сопоставления, чтобы получить набор циклов. Затем циклы сшиваются для создания финального тура.

Алгоритм Христофидеса и Сердюкова
Создание соответствия
Использование эвристики ярлыка на графике, созданном сопоставлением выше

Алгоритм Христофидес и Сердюков следует аналогичный план , но сочетает в себе минимальное покрывающее дерево с решением другой проблемы, минимального веса соответствия совершенным . Это дает тур TSP, который не более чем в 1,5 раза лучше оптимального. Это был один из алгоритмов первого приближения , который частично отвечал за привлечение внимания к алгоритмам приближения как к практическому подходу к трудноразрешимым проблемам. Фактически, термин «алгоритм» обычно не распространялся на алгоритмы аппроксимации до более позднего времени; алгоритм Кристофидеса первоначально назывался эвристикой Кристофидеса.

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

  1. Найдите минимальное остовное дерево для проблемы
  2. Создавайте дубликаты для каждого ребра, чтобы создать эйлеров граф
  3. Найдите эйлеров тур для этого графика
  4. Преобразовать в TSP: если город посещается дважды, создайте в туре ярлык из города до этого в город после этого.

Чтобы улучшить нижнюю границу, необходим лучший способ создания графа Эйлера. Согласно треугольному неравенству, лучший эйлеров граф должен иметь ту же стоимость, что и тур лучшего коммивояжера, следовательно, поиск оптимальных эйлеровых графов не менее сложен, чем TSP. Один из способов сделать это - сопоставление минимального веса с использованием алгоритмов .

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

  1. Найдите минимальное остовное дерево для проблемы
  2. Создайте сопоставление для задачи с набором городов нечетного порядка.
  3. Найдите эйлеров тур для этого графика
  4. Преобразование в TSP с помощью ярлыков.

Попарный обмен

Пример 2-опционной итерации

Метод попарного обмена или 2-опт. Включает итеративное удаление двух ребер и замену их двумя разными ребрами, которые повторно соединяют фрагменты, созданные удалением ребер, в новый и более короткий тур. Точно так же метод 3-opt удаляет 3 края и повторно соединяет их, чтобы сформировать более короткий тур. Это частные случаи метода k -opt. Ярлык Lin – Kernighan часто используется неверно для обозначения 2-opt. Лин – Керниган на самом деле является более общим методом k-opt.

Для евклидовых примеров эвристика с двумя вариантами дает в среднем решения, которые примерно на 5% лучше, чем алгоритм Кристофидеса. Если мы начнем с начального решения, сделанного с помощью жадного алгоритма , среднее количество ходов снова сильно уменьшится и составит . Однако для случайных запусков среднее количество ходов равно . Однако, хотя это небольшое увеличение размера, начальное количество ходов для небольших задач в 10 раз больше для случайного запуска по сравнению с тем, которое выполняется с помощью жадной эвристики. Это связано с тем, что такая эвристика с двумя вариантами использует «плохие» части решения, такие как пересечения. Эти типы эвристик часто используются в эвристиках задач маршрутизации транспортных средств для повторной оптимизации решений маршрутов.

k -opt эвристика, или эвристика Лина – Кернигана

Эвристический Лин-Керниган является частным случаем V -opt или техники переменной опт. Он включает в себя следующие этапы:

  1. Для данного тура удалим k взаимно непересекающихся ребер.
  2. Повторно соберите оставшиеся фрагменты в тур, не оставляя непересекающихся субтур (то есть не соединяйте конечные точки фрагмента вместе). По сути, это упрощает рассматриваемую TSP и превращает ее в гораздо более простую задачу.
  3. Каждая конечная точка фрагмента может быть подключена к 2 k  - 2 другим возможностям: из 2 k доступных конечных точек фрагмента две конечные точки рассматриваемого фрагмента запрещены. Такой ограниченный 2 k -городный TSP может быть затем решен с помощью методов грубой силы, чтобы найти рекомбинацию исходных фрагментов с наименьшими затратами.

Самыми популярными из k -opt методов являются 3-opt, введенные Шен Линь из Bell Labs в 1965 году. Частным случаем 3-opt является то, что ребра не пересекаются (два ребра смежны друг с другом). . На практике часто можно добиться существенного улучшения по сравнению с 2-opt без комбинаторных затрат на общий 3-opt, ограничивая 3-изменения этим специальным подмножеством, где два из удаленных ребер являются смежными. Этот так называемый «два с половиной варианта» обычно находится примерно посередине между 2-мя и 3-мя вариантами, как с точки зрения качества достигнутых туров, так и времени, необходимого для их реализации.

V -opt эвристика

Метод variable-opt является обобщением метода k -opt. В то время как методы k -opt удаляют фиксированное количество ( k ) ребер из исходного маршрута, методы variable-opt не фиксируют размер удаляемого ребра. Вместо этого они увеличивают набор по мере продолжения процесса поиска. Самый известный метод в этом семействе - метод Лин-Кернигана (упомянутый выше как неправильное название 2-opt). Шен Линь и Брайан Керниган впервые опубликовали свой метод в 1972 году, и он был наиболее надежным эвристическим методом для решения задач коммивояжера на протяжении почти двух десятилетий. Более продвинутые методы с переменной оптикой были разработаны в Bell Labs в конце 1980-х Дэвидом Джонсоном и его исследовательской группой. Эти методы (иногда называемые Лин-Керниган-Джонсон ) основаны на методе Лин-Керниган, добавляя идеи из запретного поиска и эволюционных вычислений . Базовая методика Лин-Кернигана дает результаты, которые гарантированно являются как минимум 3-опт. Методы Лин-Керниган-Джонсон вычислить тур Lin-Kernighan, а затем возмущать тур по тому , что было описано как мутации , которая удаляет по меньшей мере , четыре ребра и переподключение тур по-другому, то V -opting нового тура. Мутации часто бывает достаточно, чтобы переместить тур за пределы локального минимума, установленного Лин-Керниган. Методы V -opt широко считаются наиболее мощной эвристикой для решения проблемы и могут решать особые случаи, такие как проблема цикла Гамильтона и другие неметрические TSP, которые не удается решить с помощью других эвристик. В течение многих лет Лин-Керниган-Джонсон выявлял оптимальные решения для всех операторов связи, для которых было известно оптимальное решение, и определял наиболее известные решения для всех других поставщиков услуг связи, на которых был опробован этот метод.

Рандомизированное улучшение

Оптимизированные алгоритмы цепей Маркова , которые используют подалгоритмы эвристического поиска, могут найти маршрут, очень близкий к оптимальному маршруту для 700-800 городов.

TSP - это пробный камень для многих общих эвристик, разработанных для комбинаторной оптимизации, таких как генетические алгоритмы , имитация отжига , запретный поиск , оптимизация колоний муравьев , динамика образования рек (см. Интеллект роя ) и метод кросс-энтропии .

Оптимизация колонии муравьев

Исследователь искусственного интеллекта Марко Дориго описал в 1993 году метод эвристической генерации «хороших решений» для TSP с использованием моделирования колонии муравьев, называемой ACS ( система колоний муравьев ). Он моделирует поведение, наблюдаемое у настоящих муравьев, чтобы найти короткие пути между источниками пищи и их гнездом, возникающее поведение, возникающее в результате предпочтения каждого муравья следовать за феромонами, оставленными другими муравьями.

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

1) Муравей выбирает путь среди всех возможных путей и прокладывает на нем след феромона.  2) Все муравьи путешествуют разными путями, прокладывая след из феромонов, пропорциональный качеству раствора.  3) Каждое ребро лучшего пути более усилено, чем другие.  4) Испарение гарантирует, что плохие растворы исчезнут.  Карта является работой Ива Обри [2].
Алгоритм оптимизации муравьиной колонии для TSP с 7 городами: красные и толстые линии на карте феромонов указывают на присутствие большего количества феромонов.

Особые случаи

Метрическая

В метрике TSP , также известной как дельта-TSP или Δ-TSP, междугородние расстояния удовлетворяют неравенству треугольника .

Очень естественным ограничением TSP является требование, чтобы расстояния между городами образовывали метрику, удовлетворяющую неравенству треугольника ; то есть прямое соединение от A до B никогда не дальше, чем маршрут через промежуточный C :

.

Затем ребра строят метрику на множестве вершин. Когда города рассматриваются как точки на плоскости, многие функции естественного расстояния являются метриками, и очень многие естественные экземпляры TSP удовлетворяют этому ограничению.

Ниже приведены некоторые примеры метрических TSP для различных метрик.

  • В евклидовом TSP (см. Ниже) расстояние между двумя городами - это евклидово расстояние между соответствующими точками.
  • В прямолинейной TSP расстояние между двумя городами является суммой абсолютных значений разностей их координат x и y . Эту метрику часто называют манхэттенским расстоянием или метрикой квартала.
  • В максимальной метрике расстояние между двумя точками является максимальным из абсолютных значений разностей их координат x и y .

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

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

Евклидово

Когда входные числа могут быть произвольными действительными числами, евклидова TSP является частным случаем метрической TSP, поскольку расстояния в плоскости подчиняются неравенству треугольника. Когда входные числа должны быть целыми, сравнение продолжительности обходов включает сравнение сумм квадратных корней.

Как и общая TSP, евклидова TSP в любом случае NP-трудна. С рациональными координатами и дискретной метрикой (расстояния округлены до целого числа) проблема является NP-полной. Известно, что евклидова TSP с рациональными координатами и фактической евклидовой метрикой находится в Иерархии подсчета, подклассе PSPACE. С произвольными действительными координатами евклидова TSP не может быть в таких классах, поскольку существует несчетное количество возможных входных данных. Однако евклидова TSP, вероятно, является самой простой версией для приближения. Например, минимальное остовное дерево графа, связанное с экземпляром евклидова TSP, является евклидовым минимальным остовным деревом , и поэтому может быть вычислено за ожидаемое время O ( n log n ) для n точек (значительно меньше, чем количество ребер ). Это позволяет более быстрому выполнению простого 2-приближенного алгоритма для TSP с указанным выше неравенством треугольника.

В общем, для любого c > 0, где d - количество измерений в евклидовом пространстве, существует алгоритм с полиномиальным временем, который находит обход длиной не более (1 + 1 / c ) раз оптимальной для геометрических экземпляров TSP в

время; это называется схемой полиномиального приближения (PTAS). Санджив Арора и Джозеф С.Б. Митчелл были награждены премией Гёделя в 2010 году за одновременное открытие PTAS для евклидовой TSP.

На практике продолжают использоваться более простые эвристики с более слабыми гарантиями.

Асимметричный

В большинстве случаев расстояние между двумя узлами в сети TSP одинаково в обоих направлениях. Случай, когда расстояние от A до B не равно расстоянию от B до A , называется асимметричным TSP. Практическое применение асимметричной TSP - оптимизация маршрута с использованием маршрутизации на уровне улиц (которая делается асимметричной из-за улиц с односторонним движением, объездных дорог, автомагистралей и т. Д.).

Преобразование в симметричный

Решение асимметричного графа TSP может быть несколько сложным. Следующее представляет собой матрицу 3 × 3 , содержащий все возможные веса пути между узлами , B и C . Одним из вариантов являются , чтобы превратить асимметричную матрицу размера N в симметричную матрицу размера 2 N .

Асимметричные веса пути
А B C
А 1 2
B 6 3
C 5 4

Чтобы удвоить размер, каждый из узлов в графе дублируется, создавая второй призрачный узел , связанный с исходным узлом «призрачным» ребром очень низкого (возможно, отрицательного) веса, здесь обозначенного - w . (В качестве альтернативы, фантомные края имеют вес 0, а вес w добавляется ко всем остальным ребрам.) Первоначальная матрица 3 × 3, показанная выше, видна в нижнем левом углу, а транспонированная копия оригинала - в верхнем правом углу. Диагонали обеих копий матрицы заменены на недорогие переходные пути, обозначенные - w . В новом графе ни одно ребро напрямую не связывает исходные узлы, а никакое ребро напрямую не связывает призрачные узлы.

Веса симметричного пути
А B C A ′ B ′ C ′
А - ж 6 5
B 1 - ж 4
C 2 3 - ж
A ′ - ж 1 2
B ′ 6 - ж 3
C ′ 5 4 - ж

Вес - w «призрачных» ребер, связывающих призрачные узлы с соответствующими исходными узлами, должен быть достаточно низким, чтобы гарантировать, что все призрачные ребра должны принадлежать любому оптимальному симметричному решению TSP на новом графе (w = 0 не всегда достаточно низкое ). Как следствие, в оптимальном симметричном туре каждый исходный узел появляется рядом со своим призрачным узлом (например, возможный путь ), и, снова объединяя исходный и призрачный узлы, мы получаем (оптимальное) решение исходной асимметричной проблемы (в нашем пример, ).

Проблема аналитика

Существует аналогичная проблема в геометрической теории меры , которая задает следующее: при каких условиях могут подмножество Е в евклидове пространства содержаться в спрямляемом кривом (то есть, когда есть кривой с конечной длиной, посещением каждой точкой Е )? Эта проблема известна как задача коммивояжера аналитика .

Длина пути для случайных наборов точек в квадрате

Предположим, что это независимые случайные величины с равномерным распределением в квадрате , и пусть будет длина кратчайшего пути (то есть решение TSP) для этого набора точек в соответствии с обычным евклидовым расстоянием . Известно, что почти наверняка

где - положительная постоянная, которая явно не известна. Поскольку (см. Ниже), из теоремы об ограниченной сходимости следует, что , следовательно, нижняя и верхняя оценки вытекают из оценок .

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

Верхняя граница

  • Можно , следовательно , использовать наивный путь, который монотонно посещает точки внутри каждого из срезов ширины в квадрате.
  • Мало кто доказал , следовательно , в дальнейшем улучшена Карлофф (1987): .
  • Некоторые исследования сообщили о верхней границе этого .

Нижняя граница

  • Наблюдая, что это больше, чем кратное расстояние между и ближайшей точкой , можно получить (после коротких вычислений)
  • Лучшая нижняя граница получается, если наблюдать, что это больше, чем умноженное на сумму расстояний между ближайшими и вторыми ближайшими точками , что дает
  • Лучшая на данный момент нижняя граница
  • Хелд и Карп предложили алгоритм с полиномиальным временем, который обеспечивает численные нижние границы для и, следовательно, для которого кажется хорошим с точностью до более или менее 1%. В частности, Дэвид С. Джонсон с помощью компьютерного эксперимента получил нижнюю оценку:

где 0,522 происходит от точек около границы квадрата, у которых меньше соседей, а Кристин Л. Валенсуэла и Антония Дж. Джонс получили следующую другую числовую нижнюю границу:

.

Вычислительная сложность

Было показано, что проблема NP-трудная (точнее, она полная для класса сложности FP NP ; см. Функциональную проблему ), и версия проблемы решения («учитывая затраты и число x , решить, есть ли раунд -маршрут путешествия дешевле, чем x ") NP-полный . Проблема коммивояжера - узкое место - тоже NP-трудная. Проблема остается NP-сложной даже для случая, когда города находятся в плоскости с евклидовыми расстояниями , а также в ряде других ограничительных случаев. Удаление условия посещения каждого города «только один раз» не снимает NP-жесткости, поскольку в плоском случае существует оптимальный тур, который посещает каждый город только один раз (в противном случае, по неравенству треугольника , ярлык, пропускающий повторное посещение не увеличивал бы продолжительность тура).

Сложность приближения

В общем случае поиск кратчайшего тура коммивояжера - это НКО . Если мера расстояния является метрической (и, следовательно, симметричной), задача становится APX- полной, и алгоритм Христофидеса и Сердюкова аппроксимирует ее с точностью до 1,5. Препринт 2020 года улучшает эту привязку к . Самая известная граница неприближаемости - 123/122.

Если расстояния ограничены 1 и 2 (но все же являются метрикой), коэффициент аппроксимации становится 8/7. В асимметричном случае с неравенством треугольника до недавнего времени были известны только логарифмические гарантии производительности. В 2018 году Свенссон, Тарнавски и Вег разработали приближение постоянного множителя. Лучший алгоритм Трауба и Вигена на сегодняшний день обеспечивает коэффициент производительности . Самая известная граница неприближаемости - 75/74.

Соответствующая задача максимизации поиска самого длинного путешествия коммивояжера аппроксимируется в пределах 63/38. Если функция расстояния симметрична, самый длинный маршрут может быть аппроксимирован в пределах 4/3 с помощью детерминированного алгоритма, а внутри - с помощью рандомизированного алгоритма.

Производительность человека и животных

TSP, в частности евклидов вариант проблемы, привлек внимание исследователей когнитивной психологии . Было замечено, что люди могут создавать почти оптимальные решения быстро, почти линейно, с производительностью, которая колеблется от 1% менее эффективной для графов с 10-20 узлами и на 11% менее эффективной для графов с 120 узлов. Очевидная легкость, с которой люди точно создают почти оптимальные решения проблемы, привела исследователей к гипотезе о том, что люди используют одну или несколько эвристик, причем двумя наиболее популярными теориями, возможно, являются гипотеза выпуклой оболочки и эвристика избегания пересечений. Однако дополнительные данные свидетельствуют о том, что возможности человека сильно различаются, а индивидуальные различия, а также геометрия графиков, по-видимому, влияют на производительность при выполнении задачи. Тем не менее, результаты показывают, что производительность компьютера на TSP может быть улучшена за счет понимания и эмуляции методов, используемых людьми для решения этих проблем, а также привели к новому пониманию механизмов человеческого мышления. Первый выпуск Journal of Problem Solving был посвящен теме человеческого фактора в TSP, а в обзоре 2011 года были перечислены десятки статей по этой теме.

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

Естественное вычисление

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

Контрольные точки

Для тестирования алгоритмов TSP TSPLIB представляет собой библиотеку примеров экземпляров TSP, и связанные проблемы поддерживаются, см. Внешнюю ссылку TSPLIB. Многие из них представляют собой списки реальных городов и макеты реальных печатных схем .

Популярная культура

  • «Коммивояжер » режиссера Тимоти Ланзона - это история четырех математиков, нанятых правительством США для решения самой труднодостижимой проблемы в истории компьютерных наук: P против NP .

Смотрите также

Примечания

использованная литература

дальнейшее чтение

внешние ссылки