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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

Описание

Как задача о графе

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

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

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

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

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

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

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

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

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

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

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

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

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

$\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.$

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

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

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

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

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

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

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

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

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

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

${\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 и определите:

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

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

${\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 не может сформировать подобход, поэтому возвращаемое решение представляет собой один обход, а не объединение меньших обходов. Поскольку это приводит к экспоненциальному числу возможных ограничений, на практике это решается с помощью генерации строк .

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

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

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

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

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

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

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

Улучшить эти временные рамки представляется трудной задачей. Например, не установлено, является ли классический точный алгоритм для TSP, работающий во времени, $O(1.9999^{n})$ существует. Лучший на данный момент квантово- точный алгоритм для TSP, предложенный Амбайнисом и др. бежит во времени $O(1.728^{n})$.

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

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

Решение задачи TSP с 7 городами с использованием простого алгоритма ветвей и границ. Примечание. Количество перестановок намного меньше, чем при переборе.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Парный обмен

Пример итерации с двумя вариантами

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

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

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

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

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

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

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

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

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

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

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

Ограничивающая эвристика вставки

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

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

Основная статья: Алгоритмы оптимизации колонии муравьев

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

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

1) An ant chooses a path among all possible paths and lays a pheromone trail on it. 2) All the ants are travelling on different paths, laying a trail of pheromones proportional to the quality of the solution. 3) Each edge of the best path is more reinforced than others. 4) Evaporation ensures that the bad solutions disappear. The map is a work of Yves Aubry [2].

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

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

Метрика

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

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

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

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

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

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

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

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

евклидов

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

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

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

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

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

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

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

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

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

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

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

	А	Б	С
А		1	2
Б	6		3
С	5	4

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

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

	А	Б	С	А'	Б'	С'
А				− ш	6	5
Б				1	− ш	4
С				2	3	− ш
А'	− ш	1	2
Б'	6	− ш	3
С'	5	4	− ш

Вес − w «призрачных» ребер, связывающих призрачные узлы с соответствующими исходными узлами, должен быть достаточно низким, чтобы гарантировать, что все призрачные ребра должны принадлежать любому оптимальному симметричному решению TSP на новом графе ( w = 0 не всегда достаточно мало ). Как следствие, в оптимальном симметричном туре каждый исходный узел появляется рядом со своим узлом-призраком (например, возможный путь $\mathrm {A\to A'\to C\to C'\to B\to B'\to A}$), и снова объединив исходный и призрачный узлы, мы получим (оптимальное) решение исходной асимметричной задачи (в нашем примере $\mathrm {A\to C\to B\to A}$).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Лучший на данный момент нижняя граница

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

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

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

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

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

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

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

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

В общем случае поиск кратчайшего тура коммивояжера является NPO -полным. Если мера расстояния является метрикой ( и, следовательно, симметричной), проблема становится APX -полной, а алгоритм Христофидеса и Сердюкова аппроксимирует его с точностью до 1,5.

Если расстояния ограничены 1 и 2 (но все равно являются метрическими), то коэффициент аппроксимации становится 8/7. В асимметричном случае с неравенством треугольника в 2018 году Свенссон, Тарнавски и Вег разработали аппроксимацию постоянного фактора. Алгоритм Веры Трауб и Йенса Вигена достигает коэффициента производительности $22+\varepsilon$. Самая известная граница неаппроксимируемости — 75/74.

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

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

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

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

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

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

Тесты

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

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

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

См. также

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

Ссылки

• Эпплгейт, ДЛ; Биксби, РМ; Хватал, В.; Кук, WJ (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) , Journal of the ACM , 45 (5): 753–782, doi : 10.1145/290179.290180 , MR   1668147 , S2CID   3023351 .
• Бердвуд, Дж.; Хэлтон, Дж. Х.; Хаммерсли, Дж. М. (октябрь 1959 г.), «Кратчайший путь через множество точек» , Proceedings of the Cambridge Philosophical Society , 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», Proc. 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), «Алгоритмы аппроксимации асимметричного TSP путем разложения направленных регулярных мультиграфов», В сб. 44-й симпозиум IEEE. по основам информатики. Sci , стр. 56–65 .
• Карпинский, М.; Лампис, М.; Шмид, Р. (2015), «Новые границы неаппроксимируемости для TSP», Журнал компьютерных и системных наук , 81 (8): 1665–1677, arXiv : 1303.6437 , doi : 10.1016/j.jcss.2015.06.003
• Косараджу, СР; Парк, Дж. К.; Штейн, К. (1994), «Длинные туры и короткие суперструны» , Proc. 35-я Энн. IEEE симп. по основам информатики. Sci , Компьютерное общество IEEE, стр. 166–177 .
• Ларсон, Ричард К.; Одони, Амедео Р. (1981), «6.4.7: Применение сетевых моделей § Проблемы маршрутизации §§ Евклидово TSP» , Исследование городских операций , Прентис-Холл, ISBN  978-0-13-939447-8 , OCLC   6331426 .
• Падберг, М.; Ринальди, Г. (1991), «Алгоритм ветвей и разрезов для решения крупномасштабных симметричных задач коммивояжера», SIAM Review , 33 : 60–100, doi : 10.1137/1033004 , S2CID   18516138 .
• Пападимитриу, Христос Х. (1977), «Евклидова задача коммивояжера NP-полна», Theoretical Computer Science , 4 (3): 237–244, doi : 10.1016/0304-3975(77)90012-3 , MR   0455550 .
• Пападимитриу, Христос Х.; Яннакакис, Михалис (1993), «Задача коммивояжера с расстояниями один и два», Mathematics of Operations Research , 18 : 1–11, doi : 10.1287/moor.18.1.1 .
• Шрийвер, Александр (2005). «К истории комбинаторной оптимизации (до 1960 г.)». В К. Аардале ; Г. Л. Немхаузер ; Р. Вейсмантель (ред.). Справочник по дискретной оптимизации (PDF) . Амстердам: Эльзевир. стр. 1–68.
• Сердюков А.И. (1984), "Алгоритм с оценкой максимума для задачи коммивояжера ", Управляемые системы , 25 : 80–86 .
• Штайнербергер, Стефан (2015), «Новые границы константы коммивояжера», « Достижения в области прикладной теории вероятностей » , 47 (1): 27–36, arXiv : 1311.6338 , Bibcode : 2013arXiv1311.6338S , doi : 10.1239/aap/1427814579 , S2CID   119293287 .
• Вегингер, Г.Дж. (2003), «Точные алгоритмы для решения NP-сложных задач: обзор», Комбинаторная оптимизация – Эврика, ты уменьшаешься! Конспекты лекций по информатике, вып. 2570 , Спрингер, стр. 185–207 .

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

• Адлеман, Леонард (1994), «Молекулярное вычисление решений комбинаторных задач» (PDF) , Science , 266 (5187): 1021–4, Бибкод : 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). В погоне за коммивояжером: математика на грани вычислений . Издательство Принстонского университета. ISBN  978-0-691-15270-7 .
• Кук, Уильям ; Эспиноза, Дэниел; Гойкулеа, Маркос (2007), «Вычисления с неравенством домино-паритета для TSP», Журнал INFORMS on Computing , 19 (3): 356–365, doi : 10.1287/ijoc.1060.0204
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (31 июля 2009 г.). «35.2: Задача коммивояжера» . Введение в алгоритмы (2-е изд.). МТИ Пресс. стр. 1027–1033. ISBN  978-0-262-03384-8 .
• Данциг, Великобритания ; Фулкерсон, Р .; Джонсон, С.М. (1954), «Решение крупномасштабной задачи коммивояжера» , Operations Research , 2 (4): 393–410, doi : 10.1287/opre.2.4.393 , JSTOR   166695 , S2CID   44960960
• Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). «A2.3: ND22–24». Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. стр. 211–212. ISBN  978-0-7167-1044-8 .
• Голдберг, Делавэр (1989), «Генетические алгоритмы в поиске, оптимизации и машинном обучении», Чтение: Аддисон-Уэсли , Нью-Йорк: Аддисон-Уэсли, Bibcode : 1989gaso.book.....G , ISBN  978-0-201-15767-3
• Гутин Г.; Йео, А.; Зверович А. (15 марта 2002 г.). «Коммивояжер не должен быть жадным: анализ доминирования эвристик жадного типа для TSP» . Дискретная прикладная математика . 117 (1–3): 81–86. дои : 10.1016/S0166-218X(01)00195-0 . ISSN   0166-218X .
• Гутин Г.; Пуннен, AP (18 мая 2007 г.). Задача коммивояжера и ее варианты . Спрингер США. ISBN  978-0-387-44459-8 .
• Джонсон, Д.С .; МакГеоч, Луизиана (1997), «Проблема коммивояжера: пример локальной оптимизации», в Aarts, EHL; Ленстра, Дж. К. (ред.), Локальный поиск в комбинаторной оптимизации (PDF) , John Wiley and Sons Ltd., стр. 215–310.
• Лоулер, Эл.; Шмойс, Д.Б.; Кан, AHG Риннуй; Ленстра, Дж. К. (1985). Задача коммивояжера . Джон Уайли и сыновья, Инкорпорейтед. ISBN  978-0-471-90413-7 .
• МакГрегор, JN; Ормерод, Т. (1996), «Человеческая деятельность в задаче коммивояжера», Perception & Psychophysicals , 58 (4): 527–539, doi : 10.3758/BF03213088 , PMID   8934685 , S2CID   38355042
• Медведев Андрей; Ли, Майкл; Бутавичиус, Маркус; Викерс, Дуглас (1 февраля 2001 г.). «Работа человека в решении визуально представленных задач коммивояжера». Психологические исследования . 65 (1): 34–45. дои : 10.1007/s004260000031 . ISSN   1430-2772 . ПМИД   11505612 . S2CID   8986203 .
• Митчелл, JSB (1999), «Гильотинные подразделения аппроксимируют полигональные подразделения: простая схема аппроксимации с полиномиальным временем для геометрических TSP, 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 Journal по вычислительной технике . 6 (5). SIAM (Общество промышленной и прикладной математики): 563–581. дои : 10.1137/0206041 . S2CID   14764079 .
• Уолшоу, Крис (2000), Многоуровневый подход к задаче коммивояжера , CMS Press
• Уолшоу, Крис (2001), Многоуровневый алгоритм Лина-Кернигана-Хельсгауна для задачи коммивояжера , CMS Press

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

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