Проблема коммивояжера

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

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

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

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

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

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

История [ править ]

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

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

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

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

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

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

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

В 1976 году Христофидес и Сердюков независимо друг от друга сделали большой шаг вперед в этом направлении: ^[12] алгоритм Христофидес-Сердюков дает решение , что, в худшем случае, не более чем в 1,5 раза больше , чем оптимальное решение. Поскольку алгоритм был настолько простым и быстрым, многие надеялись, что он уступит место почти оптимальному методу решения. Это остается методом наихудшего сценария. Однако для довольно общего частного случая проблемы в 2011 году она была преодолена с небольшим отрывом ^[13].

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

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

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

В 2020 году был разработан несколько улучшенный алгоритм аппроксимации. ^{[15] [16]}

Описание [ править ]

Как проблема с графиком [ править ]

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

Асимметричный и симметричный [ править ]

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

Связанные проблемы [ править ]

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

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

ЦП можно сформулировать как целочисленную линейную программу . ^{[19] [20] [21]} Известно несколько формулировок. Двумя примечательными формулировками являются формулировка Миллера – Таккера – Землина (MTZ) и формула Данцига – Фулкерсона – Джонсона (DFJ). Состав DFJ сильнее, хотя формула MTZ все еще полезна в определенных условиях. ^{[22] [23]}

Формулировка Миллера-Таккера-Землина [ править ]

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

${\displaystyle x_{ij}={\begin{cases}1&{\text{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise}}\end{cases}}}$

Для i = 1,…, n , пусть будет фиктивной переменной и, наконец, принять расстояние от города i до города j . Тогда TSP можно записать в виде следующей задачи целочисленного линейного программирования:${\displaystyle u_{i}}$${\displaystyle c_{ij}>0}$

${\displaystyle {\begin{aligned}\min &\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}\colon &&\\&x_{ij}\in \{0,1\}&&i,j=1,\ldots ,n;\\&u_{i}\in \mathbf {Z} &&i=2,\ldots ,n;\\&\sum _{i=1,i\neq j}^{n}x_{ij}=1&&j=1,\ldots ,n;\\&\sum _{j=1,j\neq i}^{n}x_{ij}=1&&i=1,\ldots ,n;\\&u_{i}-u_{j}+nx_{ij}\leq n-1&&2\leq i\neq j\leq n;\\&1\leq u_{i}\leq n-1&&2\leq i\leq n.\end{aligned}}}$

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

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

${\displaystyle nk\leq (n-1)k,}$

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

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

Без потери общности, определите тур как начинающийся (и заканчивающийся) в городе 1. Выберите, будет ли посещаться город i на шаге t ( i , t = 1, 2, ..., n). потом${\displaystyle u_{i}=t}$

${\displaystyle u_{i}-u_{j}\leq n-1,}$

поскольку не может быть больше n и может быть не меньше 1; следовательно, ограничения выполняются всякий раз , когда For :${\displaystyle u_{i}}$${\displaystyle u_{j}}$${\displaystyle x_{ij}=0.}$${\displaystyle x_{ij}=1}$

${\displaystyle u_{i}-u_{j}+nx_{ij}=(t)-(t+1)+n=n-1,}$

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

Формулировка Данцига – Фулкерсона – Джонсона [ править ]

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

${\displaystyle x_{ij}={\begin{cases}1&{\text{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise}}\end{cases}}}$

Возьмем расстояние от города i до города j . Тогда TSP можно записать в виде следующей задачи целочисленного линейного программирования:${\displaystyle c_{ij}>0}$

${\displaystyle {\begin{aligned}\min &\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}\colon &&\\&\sum _{i=1,i\neq j}^{n}x_{ij}=1&&j=1,\ldots ,n;\\&\sum _{j=1,j\neq i}^{n}x_{ij}=1&&i=1,\ldots ,n;\\&\sum _{i\in Q}{\sum _{j\neq i,j\in Q}{x_{ij}}}\geq 1&&\forall Q\subsetneq \{1,\ldots ,n\},|Q|\geq 2\\\end{aligned}}}$

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

Вычисление решения [ править ]

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

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

Точные алгоритмы [ править ]

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

Одним из первых приложений динамического программирования является алгоритм Хельда – Карпа, который решает проблему во времени . ^[24] Эта граница также была достигнута с помощью исключения-включения в попытке предшествовать подходу динамического программирования.${\displaystyle O(n^{2}2^{n})}$

Уточнение этих временных рамок кажется трудным. Например, не было определено, существует ли точный алгоритм для TSP, который выполняется во времени . ^[25]${\displaystyle O(1.9999^{n})}$

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

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

• Алгоритмы прогрессивного улучшения, использующие методы, напоминающие линейное программирование . Работает до 200 городов.
• Реализации ветвей и границ и генерации разрезов для конкретных задач ( ветвей и разрезов ^[26] ); это метод выбора для решения больших примеров. Этот подход является текущим рекордом, решая случай с 85 900 городами, см. Applegate et al. (2006) .

Точное решение для 15 112 немецких городов из TSPLIB было найдено в 2001 году с использованием метода секущих плоскостей, предложенного Джорджем Данцигом , Рэем Фулкерсоном и Селмером М. Джонсоном в 1954 году и основанным на линейном программировании . Вычисления проводились в сети из 110 процессоров, расположенных в Университете Райса и Принстонском университете . Общее время вычислений было эквивалентно 22,6 года на одном процессоре Alpha 500 МГц . В мае 2004 года проблема коммивояжера о посещении всех 24 978 городов Швеции была решена: был найден тур протяженностью около 72 500 километров, и было доказано, что более короткого тура не существует. ^[27] В марте 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%. ^[14]

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

Конструктивная эвристика [ править ]

Ближайший сосед (NN) алгоритм (а жадный алгоритм ) позволяет приказчику выбрать ближайший Непосещенный город , как его следующий шаг. Этот алгоритм быстро дает эффективный короткий маршрут. Для N городов, случайно распределенных на плоскости, алгоритм в среднем дает путь на 25% длиннее кратчайшего из возможных. ^[28] Однако существует множество специально организованных распределений городов, которые заставляют алгоритм NN указывать наихудший маршрут. ^[29] Это верно как для асимметричных, так и для симметричных TSP. ^[30] Rosenkrantz et al. ^[31] показали, что алгоритм NN имеет коэффициент аппроксимации${\displaystyle \Theta (\log |V|)}$для случаев, удовлетворяющих неравенству треугольника. Вариант алгоритма NN, называемый оператором ближайшего фрагмента (NF), который соединяет группу (фрагмент) ближайших непосещаемых городов, может находить более короткие маршруты с последовательными итерациями. ^[32] Оператор NF также может применяться к начальному решению, полученному с помощью алгоритма NN, для дальнейшего улучшения в элитарной модели, где принимаются только лучшие решения.

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

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

Алгоритм Христофидеса и Сердюкова [ править ]

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

Этот алгоритм смотрит на вещи по-другому, используя результат теории графов, который помогает улучшить LB TSP, который возник в результате удвоения стоимости минимального связующего дерева. Имея эйлеров граф, мы можем найти эйлеров тур во времени. ^[8] Итак, если бы у нас был эйлеров граф с городами из TSP в качестве вершин, то мы могли бы легко увидеть, что мы могли бы использовать такой метод для поиска эйлерова тура, чтобы найти решение TSP. По треугольному неравенству мы знаем, что тур TSP не может быть длиннее, чем тур Эйлера, и поэтому у нас есть LB для TSP. Такой метод описан ниже.${\displaystyle O(n)}$

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

Чтобы улучшить нижнюю границу, необходим лучший способ создания графа Эйлера. Согласно треугольному неравенству, лучший эйлеров граф должен иметь ту же стоимость, что и тур лучшего коммивояжера, следовательно, поиск оптимальных эйлеровых графов не менее сложен, чем TSP. Один из способов сделать это - сопоставление минимального веса с использованием алгоритмов . ^[8]${\displaystyle O(n^{3})}$

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

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

Попарный обмен [ править ]

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

Для евклидовых примеров эвристика с двумя вариантами дает в среднем решения, которые примерно на 5% лучше, чем алгоритм Кристофидеса. Если мы начнем с начального решения, сделанного с помощью жадного алгоритма , среднее количество ходов снова сильно уменьшится и составит . Однако для случайных запусков среднее количество ходов равно . Однако, хотя это небольшое увеличение размера, начальное количество ходов для небольших задач в 10 раз больше для случайного запуска по сравнению с тем, которое выполняется с помощью жадной эвристики. Это связано с тем, что такая эвристика с двумя вариантами использует «плохие» части решения, такие как пересечения. Эти типы эвристик часто используются в эвристиках задач маршрутизации транспортных средств для повторной оптимизации решений маршрутов. ^[28]${\displaystyle O(n)}$${\displaystyle O(n\log(n))}$

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-опт. Методы Лин-Керниган-Джонсон вычисляют тур Лин-Кернигана, а затем возмущают тур тем, что было описано как мутация, которая удаляет по крайней мере четыре ребра и повторно соединяет тур другим способом, тогда V-забываем новый тур. Мутации часто бывает достаточно, чтобы переместить тур за пределы локального минимума, установленного Лин-Керниган. Методы V -opt широко считаются наиболее мощными эвристиками для решения проблемы и способны решать особые случаи, такие как проблема цикла Гамильтона и другие неметрические TSP, которые не удается решить с помощью других эвристик. В течение многих лет Лин-Керниган-Джонсон выявлял оптимальные решения для всех операторов связи, для которых было известно оптимальное решение, и определял наиболее известные решения для всех других поставщиков услуг связи, на которых был опробован этот метод.

Рандомизированное улучшение [ править ]

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

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

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

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

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

Особые случаи [ править ]

Метрика [ править ]

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

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

${\displaystyle d_{AB}\leq d_{AC}+d_{CB}}$.

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

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

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

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

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

Евклидово [ править ]

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

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

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

${\displaystyle O\left(n(\log n)^{(O(c{\sqrt {d}}))^{d-1}}\right),}$

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

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

Асимметричный [ править ]

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

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

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

Асимметричные веса пути

	А	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 не всегда достаточно низкое ). Как следствие, в оптимальном симметричном туре каждый исходный узел появляется рядом со своим призрачным узлом (например, возможный путь ), и, снова объединяя исходный и призрачный узлы, мы получаем (оптимальное) решение исходной асимметричной проблемы (в нашем пример, ).${\displaystyle \mathrm {A\to A'\to C\to C'\to B\to B'\to A} }$${\displaystyle \mathrm {A\to C\to B\to A} }$

Проблема аналитика [ править ]

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

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

Предположим, что это независимые случайные величины с равномерным распределением в квадрате , и пусть будет длина кратчайшего пути (то есть решение TSP) для этого набора точек в соответствии с обычным евклидовым расстоянием . Известно ^[11], что почти наверняка${\displaystyle X_{1},\ldots ,X_{n}}$${\displaystyle n}$${\displaystyle [0,1]^{2}}$${\displaystyle L_{n}^{\ast }}$

${\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta \qquad {\text{when }}n\to \infty ,}$

где - положительная постоянная, которая явно не известна. Поскольку (см. Ниже), из теоремы об ограниченной сходимости следует, что , следовательно, нижняя и верхняя оценки вытекают из оценок .${\displaystyle \beta }$${\displaystyle L_{n}^{*}\leq 2{\sqrt {n}}+2}$${\displaystyle \beta =\lim _{n\to \infty }\mathbb {E} [L_{n}^{*}]/{\sqrt {n}}}$${\displaystyle \beta }$${\displaystyle \mathbb {E} [L_{n}^{*}]}$

Почти верный предел as может не существовать, если независимые местоположения заменены наблюдениями из стационарного эргодического процесса с однородными маргиналами. ^[40]${\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta }$${\displaystyle n\to \infty }$${\displaystyle X_{1},\ldots ,X_{n}}$

Верхняя граница [ править ]

• Можно , следовательно , использовать наивный путь, который монотонно посещает точки внутри каждого из срезов ширины в квадрате.${\displaystyle L^{*}\leq 2{\sqrt {n}}+2}$${\displaystyle \beta \leq 2}$${\displaystyle {\sqrt {n}}}$${\displaystyle 1/{\sqrt {n}}}$
• Лишь немногие ^[41] доказано , следовательно , в дальнейшем улучшена за счет Карлофф (1987): .${\displaystyle L_{n}^{*}\leq {\sqrt {2n}}+1.75}$${\displaystyle \beta \leq {\sqrt {2}}}$${\displaystyle \beta \leq 0.984{\sqrt {2}}}$
• Некоторое исследование сообщило ^[42] о верхней границе этого .${\displaystyle \beta \leq 0.92\dots }$
• В некоторых исследованиях ^[43] сообщается о верхней границе этого значения .${\displaystyle \beta \leq 0.73\dots }$

Нижняя граница [ править ]

• Наблюдая, что это больше, чем кратное расстояние между и ближайшей точкой , можно получить (после коротких вычислений)${\displaystyle \mathbb {E} [L_{n}^{*}]}$${\displaystyle n}$${\displaystyle X_{0}}$${\displaystyle X_{i}\neq X_{0}}$

${\displaystyle \mathbb {E} [L_{n}^{*}]\geq {\tfrac {1}{2}}{\sqrt {n}}.}$

• Лучшая нижняя граница получается ^[11] , наблюдая, что это больше, чем умноженное на сумму расстояний между ближайшими и вторыми ближайшими точками , что дает${\displaystyle \mathbb {E} [L_{n}^{*}]}$${\displaystyle {\tfrac {1}{2}}n}$${\displaystyle X_{0}}$${\displaystyle X_{i},X_{j}\neq X_{0}}$

${\displaystyle \mathbb {E} [L_{n}^{*}]\geq \left({\tfrac {1}{4}}+{\tfrac {3}{8}}\right){\sqrt {n}}={\tfrac {5}{8}}{\sqrt {n}},}$

• В настоящее время ^[42] наилучшая нижняя граница

${\displaystyle \mathbb {E} [L_{n}^{*}]\geq ({\tfrac {5}{8}}+{\tfrac {19}{5184}}){\sqrt {n}},}$

• Хелд и Карп ^[44] представили алгоритм с полиномиальным временем, который обеспечивает численные нижние границы для и, таким образом, для которого кажется хорошим с точностью до более или менее 1%. ^[45] В частности, Дэвид С. Джонсон ^[46] получил нижнюю оценку компьютерным экспериментом:${\displaystyle L_{n}^{*}}$${\displaystyle \beta (\simeq L_{n}^{*}/{\sqrt {n}})}$

${\displaystyle L_{n}^{*}\gtrsim 0.7080{\sqrt {n}}+0.522,}$

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

${\displaystyle L_{n}^{*}\gtrsim 0.7078{\sqrt {n}}+0.551}$.

Вычислительная сложность [ править ]

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

Сложность приближения [ править ]

В общем случае поиск кратчайшего тура коммивояжера - это НКО . ^[48] Если мера расстояния является метрикой (и, следовательно, симметричной), задача становится APX- полной ^[49], и алгоритм Христофидеса и Сердюкова приближает ее с точностью до 1,5. ^{[50] [51] [12]} В препринте 2020 года эта оценка улучшена . ^[52] Самая известная граница неприближаемости - 123/122. ^[53]${\displaystyle 1.5-10^{-36}}$

Если расстояния ограничены 1 и 2 (но по-прежнему являются метрикой), коэффициент аппроксимации становится 8/7. ^[54] В асимметричном случае с неравенством треугольника до недавнего времени были известны только логарифмические гарантии производительности. ^[55] В 2018 г. Свенссон, Тарнавски и Вег разработали приближение постоянного множителя. ^[56] Лучший алгоритм Трауба и Вигена на сегодняшний день достигает коэффициента производительности . ^[57] Самая известная граница неприближаемости - 75/74. ^[53]${\displaystyle 22+\varepsilon }$

Соответствующая задача максимизации поиска самого длинного путешествия коммивояжера аппроксимируется в пределах 63/38. ^[58] Если функция расстояния симметрична, самый длинный маршрут может быть аппроксимирован в пределах 4/3 с помощью детерминированного алгоритма ^[59] и с помощью рандомизированного алгоритма. ^[60]${\displaystyle {\tfrac {1}{25}}(33+\varepsilon )}$

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

TSP, в частности евклидов вариант проблемы, привлек внимание исследователей когнитивной психологии . Было замечено, что люди могут создавать почти оптимальные решения быстро, почти линейно, с производительностью, которая колеблется от 1% менее эффективной для графов с 10-20 узлами и на 11% менее эффективной для графов с 120 узлов. ^{[61] [62]} Очевидная легкость, с которой люди точно генерируют почти оптимальные решения проблемы, привела исследователей к гипотезе о том, что люди используют одну или несколько эвристик, причем двумя наиболее популярными теориями, возможно, являются гипотеза выпуклой оболочки и пересечение -эвристика предотвращения. ^{[63] [64] [65]}Однако дополнительные данные свидетельствуют о том, что возможности человека весьма различны, а индивидуальные различия, а также геометрия графиков, по-видимому, влияют на производительность при выполнении задачи. ^{[66] [67] [68]} Тем не менее, результаты показывают, что производительность компьютера на TSP может быть улучшена путем понимания и имитации методов, используемых людьми для решения этих проблем, ^[69], а также привели к новому пониманию механизмов человеческого мысль. ^[70] Первый выпуск « Журнала решения проблем» был посвящен теме участия человека в TSP ^[71], а в обзоре 2011 года перечислены десятки статей по этой теме. ^[70]

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

Естественное вычисление [ править ]

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

Контрольные показатели [ править ]

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

Популярная культура [ править ]

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

См. Также [ править ]

• Проблема канадского путешественника
• Точный алгоритм
• Проблема проверки маршрута (также известная как "проблема китайского почтальона")
• Задайте задачу TSP
• Семь мостов Кенигсберга
• Задача коммивояжера Штайнера
• Метро Вызов
• Tube Challenge
• Проблема с маршрутизацией автомобиля
• Исследование графа

Заметки [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

На Викискладе есть средства массовой информации, связанные с проблемой коммивояжера .

• Задача коммивояжера у машины обратного пути (архивировано 17 декабря 2013 г.) в Университете Ватерлоо
• TSPLIB в Гейдельбергском университете
• Задача коммивояжера от Джона Маклоуна в демонстрационном проекте Wolfram Demonstrations Project
• Инструмент визуализации TSP