Задача коммивояжера

NP-трудная задача комбинаторной оптимизации

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

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

Задача о путешествующем покупателе , задача о маршрутизации транспортного средства и задача о кольцевой звезде ^[1] представляют собой три обобщения задачи TSP.

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

Описание

Как графическая задача

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

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

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

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

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

• Эквивалентная формулировка в терминах теории графов такова: если задан полный взвешенный граф (где вершины представляют города, ребра представляют дороги, а веса — стоимость или расстояние этой дороги), найдите гамильтонов цикл с наименьшим весом. Это более общая задача, чем задача о гамильтоновом пути , которая спрашивает только, существует ли гамильтонов путь (или цикл) в неполном невзвешенном графе.
• Требование возвращения в исходный город не изменяет вычислительную сложность задачи; см. задачу о гамильтоновом пути .
• Другая связанная проблема — задача коммивояжера с узким местом : найти гамильтонов цикл в взвешенном графе с минимальным весом самого тяжелого ребра . Реальный пример — избегать узких улиц с большими автобусами. ^[15] Проблема имеет большое практическое значение, помимо очевидных областей транспортировки и логистики. Классический пример — производство печатных плат : планирование маршрута сверлильного станка для сверления отверстий в печатной плате. В роботизированной обработке или сверлении «города» — это детали для обработки или отверстия (разных размеров) для сверления, а «стоимость поездки» включает время на переоснащение робота (задача последовательности работ для одного станка). ^[16]
• Обобщенная задача коммивояжера , также известная как «задача путешествующего политика», имеет дело со «штатами», в которых есть (один или несколько) «городов», и продавец должен посетить ровно один город из каждого штата. Одно применение встречается при заказе решения задачи раскроя , чтобы минимизировать смену ножей. Другое касается сверления в производстве полупроводников ; см., например, патент США 7,054,798 . Нун и Бин продемонстрировали, что обобщенную задачу коммивояжера можно преобразовать в стандартную задачу коммивояжера с тем же количеством городов, но измененной матрицей расстояний .
• Задача последовательного упорядочения решает проблему посещения набора городов, где между городами существуют отношения предшествования.
• Распространенный вопрос на собеседовании в Google — как маршрутизировать данные между узлами обработки данных; маршруты различаются в зависимости от времени передачи данных, но узлы также различаются по вычислительной мощности и объему хранения, что усугубляет проблему, куда отправлять данные.
• Задача путешествующего покупателя касается покупателя, которому поручено купить набор продуктов. Он может купить эти продукты в нескольких городах, но по разным ценам, и не все города предлагают одинаковые продукты. Цель состоит в том, чтобы найти маршрут между подмножеством городов, который минимизирует общие затраты (стоимость поездки + стоимость покупки) и позволяет купить все требуемые продукты.

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

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

Общим для обеих этих формул является то, что города обозначаются числами и за стоимость (расстояние) от города до города принимается . Основными переменными в формулировках являются: ${\displaystyle 1,\ldots ,n}$ ${\displaystyle c_{ij}>0}$ ${\displaystyle i}$ ${\displaystyle j}$

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

Именно потому, что это переменные 0/1, формулировки становятся целочисленными программами; все остальные ограничения являются чисто линейными. В частности, цель программы — минимизировать длину тура

${\displaystyle \sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}.}$

Без дополнительных ограничений будет эффективно охватывать все подмножества набора ребер, что очень далеко от наборов ребер в туре, и допускает тривиальный минимум, где все . Таким образом, обе формулировки также имеют ограничения, что в каждой вершине есть ровно одно входящее ребро и одно исходящее ребро, что может быть выражено линейными уравнениями ${\displaystyle \{x_{ij}\}_{i,j}}$ ${\displaystyle x_{ij}=0}$ ${\displaystyle 2n}$

${\displaystyle \sum _{i=1,i\neq j}^{n}x_{ij}=1}$для и для ${\displaystyle j=1,\ldots ,n}$ ${\displaystyle \sum _{j=1,j\neq i}^{n}x_{ij}=1}$ ${\displaystyle i=1,\ldots ,n.}$

Они гарантируют, что выбранный набор ребер локально выглядит как набор тура, но все еще допускают решения, нарушающие глобальное требование, что существует один тур, который посещает все вершины, поскольку выбранные ребра могут составлять несколько туров, каждый из которых посещает только подмножество вершин; возможно, именно это глобальное требование делает TSP сложной проблемой. Формулировки MTZ и DFJ различаются тем, как они выражают это конечное требование в виде линейных ограничений.

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

В дополнение к переменным, указанным выше, для каждой из них существует фиктивная переменная , которая отслеживает порядок посещения городов, начиная с города ; интерпретация заключается в том, что город посещается до города Для заданного тура (закодированного в значениях переменных ) можно найти удовлетворяющие значения для переменных, сделав их равными количеству ребер вдоль этого тура при переходе из города в город ^[22] ${\displaystyle x_{ij}}$ ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle u_{i}}$ ${\displaystyle 1}$ ${\displaystyle u_{i}<u_{j}}$ ${\displaystyle i}$ ${\displaystyle j.}$ ${\displaystyle x_{ij}}$ ${\displaystyle u_{i}}$ ${\displaystyle u_{i}}$ ${\displaystyle 1}$ ${\displaystyle i.}$

Поскольку линейное программирование отдает предпочтение нестрогим неравенствам ( ) по сравнению со строгими ( ), мы хотели бы наложить ограничения, чтобы ${\displaystyle \geq }$ ${\displaystyle >}$

${\displaystyle u_{j}\geq u_{i}+1}$если ${\displaystyle x_{ij}=1.}$

Простое требование не достигнет этого, потому что это также требует когда, что не является правильным. Вместо этого MTZ использует линейные ограничения ${\displaystyle u_{j}\geq u_{i}+x_{ij}}$ ${\displaystyle u_{j}\geq u_{i}}$ ${\displaystyle x_{ij}=0,}$ ${\displaystyle n(n-1)}$

${\displaystyle u_{i}-u_{j}+1\leq (n-1)(1-x_{ij})}$для всех отдельных ${\displaystyle i,j\in \{2,\dotsc ,n\},}$

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

Способ, которым переменные затем обеспечивают посещение всех городов одним туром, заключается в том, что они увеличиваются по крайней мере на каждый шаг по маршруту, а уменьшение допускается только там, где маршрут проходит через город.  Это ограничение будет нарушено каждым туром, который не проходит через город,  поэтому единственный способ удовлетворить ему — сделать так, чтобы маршрут, проходящий через город,  также проходил через все остальные города. ${\displaystyle u_{i}}$ ${\displaystyle 1}$ ${\displaystyle 1.}$ ${\displaystyle 1,}$ ${\displaystyle 1}$

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

${\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;\\\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}+1\leq {}&(n-1)(1-x_{ij})&&2\leq i\neq j\leq n;\\2\leq u_{i}\leq {}&n&&2\leq i\leq n.\end{aligned}}}$

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

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

Обозначьте города цифрами 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}}}\leq |Q|-1&&\forall Q\subsetneq \{1,\ldots ,n\},|Q|\geq 2.\\\end{aligned}}}$

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

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

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

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

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

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

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

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

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

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

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

Решение TSP с 7 городами с использованием простого алгоритма Branch and bound. Примечание: количество перестановок намного меньше, чем при поиске методом грубой силы

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

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

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

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

Выделяют несколько категорий эвристик.

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

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

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

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

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

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

Создание соответствия

Использование эвристики сокращенного метода на графике, созданном сопоставлением выше

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

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

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

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

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

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

Парный обмен

Пример итерации с 2 вариантами

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

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

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

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

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

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

В-opt эвристический

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

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

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

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

Эвристика ограничения вставки

Это начинается с под-тура, такого как выпуклая оболочка , а затем вставляются другие вершины. ^[36]

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

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

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

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

Алгоритм оптимизации колонии муравьев для TSP с 7 городами: красные и толстые линии на карте феромонов указывают на наличие большего количества феромонов

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

Метрическая

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

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

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

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

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

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

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

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

Евклидов

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

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

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

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

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

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

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

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

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

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

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

Вес − 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} }$

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

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

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

Предположим, что являются независимыми случайными величинами с равномерным распределением в квадрате , и пусть будет кратчайшей длиной пути (т.е. решением TSP) для этого набора точек, согласно обычному евклидову расстоянию . Известно ^[9], что, почти наверняка, ${\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}^{*}]}$

Почти наверняка предел может не существовать, если независимые местоположения заменить наблюдениями из стационарного эргодического процесса с равномерными маргинальными значениями. ^[44] ${\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}}}$
• Немногое ^[45] доказало , следовательно , позже улучшено Карлоффом (1987) : ${\displaystyle L_{n}^{*}\leq {\sqrt {2n}}+1.75}$ ${\displaystyle \beta \leq {\sqrt {2}}}$ ${\displaystyle \beta \leq 0.984{\sqrt {2}}}$
• Фитчер ^[46] эмпирически предположил верхнюю границу . ${\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}}.}$

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

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

• На данный момент лучшая ^{[ когда? ]} нижняя граница — ^[47]

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

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

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

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

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

Сложность вычислений

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

Сложность аппроксимации

В общем случае нахождение кратчайшего маршрута коммивояжера является NPO -полной задачей. ^[52] Если мера расстояния является метрикой ( и, следовательно, симметричной), задача становится APX -полной, ^[53] и алгоритм Христофидеса и Сердюкова аппроксимирует ее с точностью до 1,5. ^{[54] [55] [10]}

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

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

Эффективность человека и животных

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

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

Натуральные вычисления

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

Показатели

Для бенчмаркинга алгоритмов TSP поддерживается библиотека примеров TSP и связанных с ними проблем TSPLIB ^{[76] ; см. внешнюю ссылку TSPLIB. Многие из них представляют собой списки реальных городов и макеты реальных} печатных плат .

Массовая культура

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

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

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

Примечания

1. Лаббе, Мартина; Лапорт, Гилберт; Мартин, Инмакулада Родригес; Гонсалес, Хуан Хосе Саласар (май 2004 г.). «Проблема кольцевой звезды: многогранный анализ и точный алгоритм». Сети . 43 (3): 177–189. дои : 10.1002/net.10114. ISSN  0028-3045.
2. См. задачу кругосветного путешествия TSP, которая уже решена с точностью до 0,05% от оптимального решения. [1]
3. "Der Handlungsreisende – wie er sein soll und Was er zu tun Hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur" ​​(Коммивояжер - каким он должен быть и какой он должен сделать, чтобы получить комиссионные и быть уверенным в счастливом успехе своего дела – старый комиссар -путешественник )
4. Обсуждение ранних работ Гамильтона и Киркмана можно найти в книге «Теория графов, 1736–1936» Биггса, Ллойда и Уилсона (Clarendon Press, 1986).
5. Цитируется и английский перевод в Schrijver (2005). Оригинал на немецком языке: «Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden» Эта проблема является естественной, если вы не хотите, чтобы это произошло, если вы хотите, чтобы это произошло, если вы не хотите, чтобы это произошло. nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., Liefert im allgemeinen nicht den kürzesten Weg."
6. Лоулер, EL (1985). Задача коммивояжера: путеводитель по комбинаторной оптимизации (переиздание с исправлениями. ред.). John Wiley & sons. ISBN 978-0-471-90413-7.
7. Робинсон, Джулия (5 декабря 1949 г.). О гамильтоновой игре (задача коммивояжера) (PDF) (Технический отчет). Санта-Моника, Калифорния: The RAND Corporation. RM-303 . Получено 2 мая 2020 г. – через Defense Technical Information Center.
8. Подробное рассмотрение связи между Менгером и Уитни, а также развития изучения TSP можно найти в работе Schrijver (2005).
9. Бирдвуд, Хэлтон и Хаммерсли (1959).
10. van Bevern, René; Slugina, Viktoriia A. (2020). «Историческая заметка об алгоритме 3/2-аппроксимации для метрической задачи коммивояжера». Historia Mathematica . 53 : 118–127. arXiv : 2004.02437 . doi : 10.1016/j.hm.2020.04.003. S2CID  214803097.
11. Кларрайх, Эрика (30 января 2013 г.). «Ученые-компьютерщики нашли новые короткие пути для печально известной проблемы коммивояжера». WIRED . Получено 14 июня 2015 г.
12. Кларрайх, Эрика (8 октября 2020 г.). «Ученые-компьютерщики побили рекорд коммивояжера». Журнал Quanta . Получено 13 октября 2020 г.
13. Карлин, Анна Р.; Кляйн, Натан; Гаран, Шаян Овейс (2021), «(Немного) улучшенный алгоритм аппроксимации для метрической задачи TSP», в Хуллер, Самир ; Уильямс, Вирджиния Василевска (ред.), STOC '21: 53-й ежегодный симпозиум ACM SIGACT по теории вычислений, виртуальное мероприятие, Италия, 21–25 июня 2021 г. , стр. 32–45, arXiv : 2007.01409 , doi : 10.1145/3406325.3451009, ISBN 978-1-4503-8053-9, S2CID  220347561
14. Rego, César; Gamboa, Dorabela; Glover, Fred; Osterman, Colin (2011), «Эвристика задачи коммивояжера: ведущие методы, реализации и последние достижения», European Journal of Operational Research , 211 (3): 427–441, doi :10.1016/j.ejor.2010.09.010, MR  2774420, S2CID  2856898.
15. «Как исправить маршруты школьных автобусов? Позвоните в MIT в Wall Street Journal» (PDF) .
16. Бехзад, Араш; Модаррес, Мохаммад (2002), «Новое эффективное преобразование обобщенной задачи коммивояжера в задачу коммивояжера», Труды 15-й Международной конференции по системной инженерии (Лас-Вегас)
17. Пападимитриу, CH; Стейглиц, K. (1998), Комбинаторная оптимизация: алгоритмы и сложность , Минеола, Нью-Йорк: Довер, стр.308-309.
18. Такер, AW (1960), «О направленных графах и целочисленных программах», Математический исследовательский проект IBM (Принстонский университет)
19. Данциг, Джордж Б. (1963), Линейное программирование и расширения , Принстон, Нью-Джерси: PrincetonUP, стр. 545–547, ISBN 0-691-08000-3 , шестое издание, 1974. 
20. Веледницкий, Марк (2017). «Короткое комбинаторное доказательство того, что многогранник DFJ содержится в многограннике MTZ для асимметричной задачи коммивояжера». Operations Research Letters . 45 (4): 323–324. arXiv : 1805.06997 . doi :10.1016/j.orl.2017.04.010. S2CID  6941484.
21. Бекташ, Толга; Гувейя, Луис (2014). «Реквием по ограничениям исключения подтура Миллера–Таккера–Землина?». Европейский журнал операционных исследований . 236 (3): 820–832. doi :10.1016/j.ejor.2013.07.038.
22. CE Miller, AW Tucker и RA Zemlin. 1960. Формулировка задач коммивояжера с помощью целочисленного программирования. J. ACM 7, 4 (октябрь 1960), 326–329. DOI:https://doi.org/10.1145/321043.321046
23. Данциг, Г.; Фулкерсон, Р.; Джонсон, С. (ноябрь 1954 г.). «Решение проблемы крупномасштабного коммивояжера». Журнал Американского общества исследования операций . 2 (4): 393–410. doi :10.1287/opre.2.4.393.
24. Беллман (1960), Беллман (1962), Хелд и Карп (1962)
25. Вёгингер (2003).
26. Амбайнис, Андрис; Балодис, Каспарс; Ираидс, Янис; Кокайнис, Мартинс; Прусис, Кришьянис; Вигров, Евгений (2019). «Квантовое ускорение для алгоритмов динамического программирования с экспоненциальным временем». Материалы тридцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 1783–1793. дои : 10.1137/1.9781611975482.107. ISBN 978-1-61197-548-2. S2CID  49743824.
27. Падберг и Ринальди (1991).
28. Задача коммивояжера - Branch and Bound на YouTube . Как отсечь бесплодные ветви, используя сокращенные строки и столбцы, как в венгерском матричном алгоритме
29. Эпплгейт, Дэвид; Биксби, Роберт; Хватал, Вашек; Кук, Уильям; Хельсгаун, Келд (июнь 2004 г.). «Оптимальный тур по Швеции» . Проверено 11 ноября 2020 г.
30. Johnson, DS ; McGeoch, LA (1997). «Задача коммивояжера: пример локальной оптимизации» (PDF) . В Aarts, EHL; Lenstra, JK (ред.). Локальный поиск в комбинаторной оптимизации . Лондон: John Wiley and Sons Ltd. стр. 215–310.
31. Гутина, Грегори; Йеоб, Андерс; Зверович, Алексей (15 марта 2002 г.). «Коммивояжер не должен быть жадным: анализ доминирования эвристик жадного типа для TSP». Дискретная прикладная математика . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 .>
32. Зверович, Алексей; Чжан, Вэйсюн; Йео, Андерс; МакГеоч, Лайл А.; Гутин, Грегори; Джонсон, Дэвид С. (2007), «Экспериментальный анализ эвристик для ATSP», Задача коммивояжера и ее вариации , Комбинаторная оптимизация, Springer, Бостон, Массачусетс, стр. 445–487, CiteSeerX 10.1.1.24.2386 , doi :10.1007/0-306-48213-4_10, ISBN  978-0-387-44459-8
33. Rosenkrantz, DJ; Stearns, RE; Lewis, PM (14–16 октября 1974 г.). Приближенные алгоритмы для задачи коммивояжера . 15-й ежегодный симпозиум по теории коммутации и автоматов (SWAT 1974). doi :10.1109/SWAT.1974.4.
34. Ray, SS; Bandyopadhyay, S.; Pal, SK (2007). «Генетические операторы для комбинаторной оптимизации в TSP и упорядочении генов микрочипов». Applied Intelligence . 26 (3): 183–195. CiteSeerX 10.1.1.151.132 . doi :10.1007/s10489-006-0018-y. S2CID  8130854. 
35. Канг, AB; Реда, S. (2004). «Совпадение дважды и сшивание: новая эвристика построения тура TSP». Operations Research Letters . 32 (6): 499–509. doi :10.1016/j.orl.2004.04.001.
36. Алатарцев, Сергей; Августин, Маркус; Ортмейер, Франк (2 июня 2013 г.). «Constricting Insertion Heuristic for Traveling Salesman Problem with Neighborhoods» (PDF) . Труды Международной конференции по автоматизированному планированию и составлению расписаний . 23 : 2–10. doi :10.1609/icaps.v23i1.13539. ISSN  2334-0843. S2CID  18691261.
37. Дориго, Марко; Гамбарделла, Лука Мария (1997). «Колонии муравьев для задачи коммивояжера». Biosystems . 43 (2): 73–81. Bibcode :1997BiSys..43...73D. CiteSeerX 10.1.1.54.7734 . doi :10.1016/S0303-2647(97)01708-5. PMID  9231906. S2CID  8243011. 
38. Quintas, LV; Supnick, Fred (1965). «О некоторых свойствах кратчайших гамильтоновых цепей». The American Mathematical Monthly . 72 (9): 977–980. doi :10.2307/2313333. JSTOR  2313333. MR  0188872.
39. Пападимитриу (1977).
40. Аллендер и др. (2007).
41. Ларсон и Одони (1981).
42. Арора (1998).
43. Йонкер, Рой; Волгенант, Тон (1983). «Преобразование асимметричных задач коммивояжера в симметричные». Operations Research Letters . 2 (161–163): 1983. doi :10.1016/0167-6377(83)90048-2.
44. Арлотто, Алессандро; Стил, Дж. Майкл (2016), «Теорема Бирдвуда–Халтона–Хаммерсли для стационарных эргодических последовательностей: контрпример», Анналы прикладной теории вероятностей , 26 (4): 2141–2168, arXiv : 1307.0221 , doi : 10.1214/15-AAP1142, S2CID  8904077
45. Фью, Л. (1955). «Кратчайший путь и кратчайшая дорога через n точек». Mathematika . 2 (2): 141–144. doi :10.1112/s0025579300000784.
46. Фихтер, К.-Н. (1994). "Параллельный алгоритм поиска с запретами для больших задач коммивояжера". Disc. Applied Math . 51 (3): 243–267. doi : 10.1016/0166-218X(92)00033-I .
47. Штайнербергер (2015).
48. Хелд, М.; Карп, Р. М. (1970). «Задача коммивояжера и минимальные остовные деревья». Исследование операций . 18 (6): 1138–1162. doi :10.1287/opre.18.6.1138.
49. Goemans, Michel X. ; Bertsimas, Dimitris J. (1991). «Вероятностный анализ нижней границы Хельда и Карпа для евклидовой задачи коммивояжера». Математика исследования операций . 16 (1): 72–89. doi :10.1287/moor.16.1.72.
50. "ошибка". about.att.com .
51. Кристин Л. Валенсуэла и Антония Дж. Джонс. Архивировано 25 октября 2007 г. на Wayback Machine.
52. Орпонен, П.; Маннила, Х. (1987). О приближении сохраняющих редукций: полные проблемы и надежные меры (отчет). Кафедра компьютерных наук, Хельсинкский университет. Технический отчет C-1987–28.
53. Пападимитриу и Яннакакис (1993).
54. Христофидес (1976).
55. Сердюков, Анатолий И. (1978), «О некоторых экстремальных обходах в графах» [О некоторых экстремальных блужданиях в графах] (PDF) , Управляемые системы (на русском языке), 17 : 76–79
56. Берман и Карпински (2006).
57. Свенссон, Ола; Тарнавски, Якуб; Вег, Ласло А. (2018). «Алгоритм аппроксимации с постоянным множителем для асимметричной задачи коммивояжера». Труды 50-го ежегодного симпозиума ACM SIGACT по теории вычислений . Stoc 2018. Лос-Анджелес, Калифорния, США: ACM Press. стр. 204–213. doi :10.1145/3188745.3188824. ISBN 978-1-4503-5559-9. S2CID  12391033.
58. Трауб, Вера ; Вайген, Йенс (8 июня 2020 г.). «Улучшенный алгоритм аппроксимации для ATSP». Труды 52-го ежегодного симпозиума ACM SIGACT по теории вычислений . Stoc 2020. Чикаго, Иллинойс: ACM. стр. 1–13. arXiv : 1912.00670 . doi : 10.1145/3357713.3384233. ISBN 978-1-4503-6979-4. S2CID  208527125.
59. Карпински, Лэмпис и Шмид (2015).
60. Косараджу, Парк и Штейн (1994).
61. Сердюков (1984).
62. Хассин и Рубинштейн (2000).
63. Макгрегор, Дж. Н.; Ормерод, Т. (июнь 1996 г.), «Человеческая деятельность в задаче коммивояжера», Perception & Psychophysics , 58 (4): 527–539, doi : 10.3758/BF03213088 , PMID  8934685.
64. Драй, Мэтью; Ли, Майкл Д.; Викерс, Дуглас; Хьюз, Питер (2006). «Человеческая производительность при визуальном представлении задач коммивояжера с различным количеством узлов». Журнал решения проблем . 1 (1). CiteSeerX 10.1.1.360.9763 . doi :10.7771/1932-6246.1004. ISSN  1932-6246. 
65. Rooij, Iris Van; Stege, Ulrike; Schactman, Alissa (1 марта 2003 г.). «Выпуклая оболочка и пересечения маршрутов в евклидовой задаче коммивояжера: выводы для исследований человеческой производительности». Memory & Cognition . 31 (2): 215–220. CiteSeerX 10.1.1.12.6117 . doi :10.3758/bf03194380. ISSN  0090-502X. PMID  12749463. S2CID  18989303. 
66. МакГрегор, Джеймс Н.; Чу, Юн (2011). «Человеческая деятельность в роли коммивояжера и связанные с ней проблемы: обзор». Журнал решения проблем . 3 (2). doi : 10.7771/1932-6246.1090 . ISSN  1932-6246.
67. MacGregor, James N.; Chronicle, Edward P.; Ormerod, Thomas C. (1 марта 2004 г.). «Выпуклая оболочка или избегание пересечения? Эвристика решения в задаче коммивояжера». Memory & Cognition . 32 (2): 260–270. doi : 10.3758/bf03196857 . ISSN  0090-502X. PMID  15190718.
68. Викерс, Дуглас; Майо, Тереза; Хайтманн, Меган; Ли, Майкл Д.; Хьюз, Питер (2004). «Интеллект и индивидуальные различия в производительности при решении трех типов визуально представленных задач оптимизации». Личность и индивидуальные различия . 36 (5): 1059–1071. doi :10.1016/s0191-8869(03)00200-9.
69. Кирицис, Маркос; Гулливер, Стивен Р.; Фередоес, Ева (12 июня 2017 г.). «Признание нарушений эвристики пересечения-избегания при решении евклидовой задачи коммивояжера». Психологические исследования . 82 (5): 997–1009. doi :10.1007/s00426-017-0881-7. ISSN  0340-0727. PMID  28608230. S2CID  3959429.
70. Кирицис, Маркос; Блатрас, Джордж; Гулливер, Стивен; Варела, Василики-Алексия (11 января 2017 г.). «Чувство направления и добросовестность как предикторы производительности в евклидовой задаче коммивояжера». Heliyon . 3 (11): e00461. Bibcode :2017Heliy...300461K. doi : 10.1016/j.heliyon.2017.e00461 . PMC 5727545 . PMID  29264418. 
71. Кирицис, Маркос; Гулливер, Стивен Р.; Фередоес, Ева; Дин, Шахаб Уд (декабрь 2018 г.). «Поведение человека в евклидовой задаче коммивояжера: вычислительное моделирование эвристик и фигуральных эффектов». Cognitive Systems Research . 52 : 387–399. doi : 10.1016/j.cogsys.2018.07.027. S2CID  53761995.
72. MacGregor, James N.; Chu, Yun (2011), «Человеческая деятельность в роли коммивояжера и связанные с этим проблемы: обзор», Journal of Problem Solving , 3 (2), doi : 10.7771/1932-6246.1090.
73. Журнал решения проблем 1(1), 2006, получено 06.06.2014.
74. Гибсон, Бретт; Уилкинсон, Мэтью; Келли, Дебби (1 мая 2012 г.). «Пусть голубь водит автобус: голуби могут планировать будущие маршруты в комнате». Animal Cognition . 15 (3): 379–391. doi :10.1007/s10071-011-0463-9. ISSN  1435-9456. PMID  21965161. S2CID  14994429.
75. Джонс, Джефф; Адамацкий, Эндрю (2014), «Вычисление задачи коммивояжера с помощью уменьшающегося пятна» (PDF) , Natural Computing : 2, 13, arXiv : 1303.4969 , Bibcode : 2013arXiv1303.4969J
76. "TSPLIB". comopt.ifi.uni-heidelberg.de . Получено 10 октября 2020 г. .
77. Geere, Duncan (26 апреля 2012 г.). «Фильм «Коммивояжер» рассматривает последствия, если P равно NP». Wired UK . Получено 26 апреля 2012 г.
78. Когда Мона Лиза — NP-Hard Эвелин Лэмб, Scientific American, 31 апреля 2015 г.

Ссылки

• Эпплгейт, Д. Л.; Биксби, Р. М.; Хватал, В.; Кук, У. Дж. (2006), Задача коммивояжера , Princeton University Press, ISBN 978-0-691-12993-8.
• Аллендер, Эрик; Бюргиссер, Питер; Кьельдгаард-Педерсен, Йохан; Митерсен, Питер Бро (2007), «О сложности численного анализа» (PDF) , SIAM J. Comput. , 38 (5): 1987–2006, CiteSeerX  10.1.1.167.5495 , doi : 10.1137/070697926.
• Арора, Санджив (1998), «Схемы полиномиального времени аппроксимации для евклидовой задачи коммивояжера и других геометрических задач» (PDF) , Журнал ACM , 45 (5): 753–782, doi :10.1145/290179.290180, MR  1668147, S2CID  3023351.
• Бирдвуд, Дж.; Хэлтон, Дж. Х.; Хаммерсли, Дж. М. (октябрь 1959 г.), «Кратчайший путь через множество точек», Труды Кембриджского философского общества , 55 (4): 299–327, Bibcode : 1959PCPS...55..299B, doi : 10.1017/s0305004100034095, ISSN  0305-0041, S2CID  122062088.
• Беллман, Р. (1960), «Комбинаторные процессы и динамическое программирование», в Беллман, Р.; Холл, М. младший (ред.), Комбинаторный анализ, Труды симпозиумов по прикладной математике 10 , Американское математическое общество, стр. 217–249.
• Беллман, Р. (1962), «Динамическое программирование решения задачи коммивояжера», Журнал Ассоциации вычислительной техники , 9 : 61–63, doi : 10.1145/321105.321111 , S2CID  15649582.
• Берман, Петр; Карпински, Марек (2006), "Алгоритм аппроксимации 8/7 для (1,2)-TSP", Труды 17-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA '06), стр. 641–648, CiteSeerX  10.1.1.430.2224 , doi :10.1145/1109557.1109627, ISBN 978-0-89871-605-4, S2CID  9054176, ECCC  TR05-069.
• Кристофидес, Н. (1976), Анализ наихудшего случая новой эвристики для задачи коммивояжера , Технический отчет 388, Высшая школа промышленного администрирования, Университет Карнеги-Меллона, Питтсбург.
• Хассин, Р.; Рубинштейн, С. (2000), «Лучшие приближения для максимального TSP», Information Processing Letters , 75 (4): 181–186, CiteSeerX  10.1.1.35.7209 , doi :10.1016/S0020-0190(00)00097-1.
• Хельд, М.; Карп, Р.М. (1962), «Подход динамического программирования к задачам последовательности», Журнал Общества промышленной и прикладной математики , 10 (1): 196–210, doi :10.1137/0110015.
• Каплан, Х.; Левенштейн, Л.; Шафрир, Н.; Свириденко, М. (2004), «Алгоритмы аппроксимации для асимметричной задачи коммивояжера путем разложения направленных регулярных мультиграфов», Труды 44-го симпозиума IEEE по основам вычислительной науки , стр. 56–65.
• Карпински, М.; Лампис, М.; Шмид, Р. (2015), «Новые границы неаппроксимируемости для TSP», Журнал компьютерных и системных наук , 81 (8): 1665–1677, arXiv : 1303.6437 , doi : 10.1016/j.jcss.2015.06.003
• Косараджу, SR; Парк, JK; Стайн, C. (1994), «Длинные туры и короткие суперструны»", Труды 35-го ежегодного симпозиума IEEE по основам вычислительной науки , IEEE Computer Society, стр. 166–177.
• Ларсон, Ричард К.; Одони, Амедео Р. (1981), "6.4.7: Применение сетевых моделей § Проблемы маршрутизации §§ Евклидова задача коммутации трафика", Исследования городских операций , Prentice-Hall, ISBN 978-0-13-939447-8, OCLC  6331426.
• Падберг, М.; Ринальди, Г. (1991), «Алгоритм ветвей и отсечений для решения крупномасштабных симметричных задач коммивояжера», SIAM Review , 33 : 60–100, doi : 10.1137/1033004, S2CID  18516138.
• Пападимитриу, Христос Х. (1977), «Евклидова задача коммивояжера является NP-полной», Теоретическая информатика , 4 (3): 237–244, doi : 10.1016/0304-3975(77)90012-3 , MR  0455550.
• Пападимитриу, Христос Х.; Яннакакис, Михалис (1993), «Задача коммивояжера с расстояниями один и два», Математика исследования операций , 18 : 1–11, doi :10.1287/moor.18.1.1.
• Schrijver, Alexander (2005). «Об истории комбинаторной оптимизации (до 1960 г.)». В K. Aardal ; GL Nemhauser ; R. Weismantel (ред.). Handbook of Discrete Optimization (PDF) . Amsterdam: Elsevier. стр. 1–68.
• Сердюков, А.И. (1984), «Алгоритм с оценкой для задачи коммивояжера о максимуме»», Управляемые системы , 25 : 80–86..
• Штайнербергер, Стефан (2015), «Новые границы константы коммивояжера», Достижения в прикладной теории вероятностей , 47 (1): 27–36, arXiv : 1311.6338 , Bibcode : 2013arXiv1311.6338S, doi : 10.1239/aap/1427814579, S2CID  119293287.
• Woeginger, GJ (2003), «Точные алгоритмы для NP-трудных задач: обзор», Комбинаторная оптимизация – Эврика, ты уменьшаешься! Конспект лекций по информатике, т. 2570 , Springer, стр. 185–207.

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

• Adleman, Leonard (1994), "Молекулярное вычисление решений комбинаторных задач" (PDF) , Science , 266 (5187): 1021–4, Bibcode :1994Sci...266.1021A, CiteSeerX  10.1.1.54.2565 , doi :10.1126/science.7973651, PMID  7973651, архивировано из оригинала (PDF) 6 февраля 2005 г.
• Бабин, Жильбер; Дено, Стефани; Лапортей, Жильбер (2005), «Улучшения эвристики Or-opt для симметричной задачи коммивояжера», Журнал Общества операционных исследований , Cahiers du GERAD, G-2005-02 (3), Монреаль: Группа исследований в области анализа решений: 402–407, CiteSeerX  10.1.1.89.9953 , JSTOR  4622707
• Кук, Уильям (2012). В погоне за коммивояжером: математика на пределе вычислений . Princeton University Press. ISBN 978-0-691-15270-7.
• Кук, Уильям ; Эспиноза, Дэниел; Гойкулеа, Маркос (2007), «Вычисления с неравенствами домино-четности для задачи коммивояжера», журнал INFORMS Journal on Computing , 19 (3): 356–365, doi :10.1287/ijoc.1060.0204
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (31 июля 2009 г.). "35.2: Задача коммивояжера". Введение в алгоритмы (2-е изд.). MIT Press. стр. 1027–1033. ISBN 978-0-262-03384-8.
• Данциг, ГБ ; Фулкерсон, Р .; Джонсон, С.М. (1954), «Решение задачи крупномасштабного коммивояжера», Исследование операций , 2 (4): 393–410, doi :10.1287/opre.2.4.393, JSTOR  166695, S2CID  44960960
• Garey, Michael R.; Johnson, David S. (1979). "A2.3: ND22–24". Computers and Intractability: A Guide to the Theory of NP-completeness. WH Freeman. стр. 211–212. ISBN 978-0-7167-1044-8.
• Голдберг, Д.Э. (1989), «Генетические алгоритмы в поиске, оптимизации и машинном обучении», Чтение: Addison-Wesley , Нью-Йорк: Addison-Wesley, Bibcode : 1989gaso.book.....G, ISBN 978-0-201-15767-3
• Гутин, Г.; Йео, А.; Зверович, А. (15 марта 2002 г.). «Коммивояжер не должен быть жадным: анализ доминирования эвристик жадного типа для TSP». Дискретная прикладная математика . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 . ISSN  0166-218X.
• Гутин, Г.; Пуннен, А. П. (18 мая 2007 г.). Задача коммивояжера и ее вариации. Springer US. ISBN 978-0-387-44459-8.
• Джонсон, Д.С.; МакГеох, Л.А. (1997), «Задача коммивояжера: пример локальной оптимизации», в Aarts, EHL; Ленстра, Дж.К. (ред.), Локальный поиск в комбинаторной оптимизации (PDF) , John Wiley and Sons Ltd., стр. 215–310
• Лоулер, Э. Л.; Шмойс, Д. Б.; Кан, А. Х. Г. Ринной; Ленстра, Дж. К. (1985). Задача коммивояжера. John Wiley & Sons, Incorporated. ISBN 978-0-471-90413-7.
• MacGregor, JN; Ormerod, T. (1996), «Человеческая деятельность в задаче коммивояжера», Perception & Psychophysics , 58 (4): 527–539, doi : 10.3758/BF03213088 , PMID  8934685, S2CID  38355042
• Медведев, Андрей; Ли, Майкл; Бутавичус, Маркус; Викерс, Дуглас (1 февраля 2001 г.). «Человеческая производительность при визуальном представлении задач коммивояжера». Психологические исследования . 65 (1): 34–45. doi :10.1007/s004260000031. ISSN  1430-2772. PMID  11505612. S2CID  8986203.
• Митчелл, Дж. С. Б. (1999), «Гильотинные подразделения приближают полигональные подразделения: простая полиномиальная схема аппроксимации для геометрических задач коммивояжера, k -MST и связанных с ними задач», SIAM Journal on Computing , 28 (4): 1298–1309, doi :10.1137/S0097539796309764
• Рао, С.; Смит, В. (1998). «Аппроксимация геометрических графов с помощью «гаечных ключей» и «баньянов»". STOC '98: Труды тридцатого ежегодного симпозиума ACM по теории вычислений . С. 540–550. CiteSeerX  10.1.1.51.8676 .
• Розенкранц, Дэниел Дж.; Стернс, Ричард Э.; Льюис, Филип М. II (1977). «Анализ нескольких эвристик для задачи коммивояжера». Журнал SIAM по вычислениям . 6 (5). SIAM (Общество промышленной и прикладной математики): 563–581. doi :10.1137/0206041. S2CID  14764079.
• Уолшоу, Крис (2000), Многоуровневый подход к проблеме коммивояжера , CMS Press
• Уолшоу, Крис (2001), Многоуровневый алгоритм Лин-Кернигана-Хелсгауна для задачи коммивояжера, CMS Press

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

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