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

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

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

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

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

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

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

• 1
• 2 Описание
  • 2.1 Как проблема графа
  • 2.2 Асимметричный и симметричный История
  • 2.3 Связанные проблемы
• 3 Формулировки целочисленного линейного программирования
  • 3.1 Миллера - Такера - Формулировка Землина
  • 3.2 Формулировка Данцига - Фулкерсона - Джонсона
• 4 Вычисление решений
  • 4.1 Точные алгоритмы
  • 4.2 Эвристические и приближенные алгоритмы
    • 4.2.1 Конструктивная эвристика
      • 4.2.1.1 Алгоритм Христофидеса и Сердюкова
    • 4.2.2 Итерационное улучшение
    • 4.2.3 Попарный обмен
    • 4.2.4 Эвристика k-opt, или Лин - Кернигана
    • 4.2.5 Эвристика V-opt
    • 4.2.6 Рандомизированное улучшение
      • 4.2.6.1 Оптимизация муравьиной колонии
• 5 Особые случаи
  • 5.1 Метрика
  • 5.2 Евклидова
  • 5.3 Асимметричная
    • 5.3.1 Преобразование в симметричную
  • 5.4 Проблема аналитика
  • 5.5 Длина пути для случайных наборов точек в квадрате
    • 5.5.1 Верхняя граница
    • 5.5.2 Нижняя граница
• 6 Сложность выч ислений
  • 6.1 Сложность аппроксимации
• 7 Производительность человека и животных
• 8 Естественные вычисления
• 9 Контрольные показатели
• 10 Популярная культура
• 11 См. Также
• 12 Примечания
• 13 Ссылки
• 14 Дополнительная литература
• 15 Внешние ссылки

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

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

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

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

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

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

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

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

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

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

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

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

В 2020 году был разработан слегка улучшенный алгоритм аппроксимации.

Как графа

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

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

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

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

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

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

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

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

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

$xij\; =\; \{1\; путь\; идет\; из\; города\; i\; в\; город\; j\; 0,\; иначе\; \{\backslash \; displaystyle\; x\_\; \{ij\}\; =\; \{\backslash \; begin\; \{cases\}\; 1\; \{\backslash \; text\; \{путь\; идет\; из\; города\}\}\; i\; \{\backslash \; text\; \{в\; город\}\}\; j\; \backslash \backslash \; 0\; \{\backslash \; text\; \{else\}\}\; \backslash \; end\; \{cases\}\}\; \}$

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

$min\; \sum \; i\; =\; 1\; n\; \sum \; j\; \ne \; i,\; j\; =\; 1\; ncijxij:\; xij\; \in \; \{0,\; 1\}\; i,\; j\; =\; 1,\dots ,\; n;\; ui\; \in \; Z\; i\; =\; 2,\dots ,\; n;\; \sum \; i\; =\; 1,\; i\; \ne \; jnxij\; =\; 1\; j\; =\; 1,\dots ,\; n;\; \sum \; j\; =\; 1,\; j\; \ne \; inxij\; =\; 1\; i\; Знак\; равно\; 1,\dots ,\; n;\; ui\; -\; uj\; +\; nxij\; \le \; n\; -\; 1\; 2\; \le \; i\; \ne \; j\; \le \; n;\; 1\; \le \; ui\; \le \; n\; -\; 1\; 2\; \le \; i\; \le \; n.\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; min\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \backslash \; sum\; \_\; \{j\; \backslash \; neq\; i,\; j\; =\; 1\}\; ^\; \{n\}\; c\_\; \{ij\}\; x\_\; \{ij\}\; \backslash \; двоеточие\; \backslash \backslash \; x\_\; \{ij\}\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; i,\; j\; =\; 1,\; \backslash \; ldots,\; n;\; \backslash \backslash \; u\_\; \{i\}\; \backslash \; in\; \backslash \; mathbf\; \{Z\}\; i\; =\; 2,\; \backslash \; ldots,\; n;\; \backslash \backslash \; \backslash \; sum\; \_\; \{i\; =\; 1,\; i\; \backslash \; neq\; j\}\; ^\; \{n\}\; x\_\; \{ij\}\; =\; 1\; j\; =\; 1,\; \backslash \; ldots,\; n;\; \backslash \backslash \; \backslash \; sum\; \_\; \{j\; =\; 1,\; j\; \backslash \; neq\; i\}\; ^\; \{n\}\; x\_\; \{ij\}\; =\; 1\; i\; =\; 1,\; \backslash \; ldots,\; n;\; \backslash \backslash \; u\_\; \{i\}\; -u\_\; \{j\}\; +\; nx\_\; \{ij\}\; \backslash \; leq\; n-1\; 2\; \backslash \; leq\; i\; \backslash \; neq\; j\; \backslash \; leq\; n;\; \backslash \; \backslash \; 1\; \backslash \; leq\; u\_\; \{i\}\; \backslash \; leq\; n-1\; 2\; \backslash \; leq\; i\; \backslash \; leq\; n.\; \backslash \; End\; \{align\}\}\}$

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

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

$nk\; \le \; (N\; -\; 1)\; К,\; \{\backslash \; Displaystyle\; NK\; \backslash \; Leq\; (N-1)\; к,\}$

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

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

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

$ui\; -\; uj\; \le \; n\; -\; 1,\; \{\backslash \; displaystyle\; u\_\; \{i\}\; -u\_\; \{j\}\; \backslash \; leq\; n-1,\}$

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

$ui\; -\; uj\; +\; nxij\; =\; (t)\; -\; (t\; +\; 1)\; +\; n\; =\; n\; -\; 1,\; \{\backslash \; displaystyle\; u\_\; \{i\}\; -u\_\; \{j\}\; +\; nx\_\; \{ij\}\; =\; (t)\; -\; (t\; +\; 1)\; +\; n\; =\; n-1,\}$

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

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

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

$xij\; =\; \{1\; путь\; идет\; из\; города\; i\; в\; город\; j\; 0\; в\; противном\; случае\; \{\backslash \; displaystyle\; x\_\; \{ij\}\; =\; \{\backslash \; begin\; \{cases\}\; 1\; \{\backslash \; text\; \{путь\; идет\; от\; города\}\}\; i\; \{\backslash \; text\; \{к\; городу\}\}\; j\; \backslash \backslash \; 0\; \{\backslash \; text\; \{else\}\}\; \backslash \; end\; \{cases\; \}\}\}$

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

$мин\; \sum \; i\; =\; 1\; n\; j\; \ne \; i,\; j\; =\; 1\; ncijxij:\; xij\; \in \; \{0,\; 1\}\; i,\; j\; =\; 1,\dots ,\; n;\; \sum \; i\; =\; 1,\; i\; \ne \; jnxij\; =\; 1\; j\; =\; 1,\dots ,\; n;\; \sum \; j\; =\; 1,\; j\; \ne \; inxij\; =\; 1\; i\; =\; 1,\dots ,\; n;\; \sum \; i\; \in \; Q\; \sum \; j\; \ne \; i,\; j\; \in \; Q\; xij\; \le \; |\; Q\; |\; -\; 1\; \forall \; Q\; ⊊\; \{1,\dots ,\; n\},\; |\; Q\; |\; \ge \; 2\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; min\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \backslash \; sum\; \_\; \{j\; \backslash \; neq\; i,\; j\; =\; 1\}\; ^\; \{n\}\; c\_\; \{ij\}\; x\_\; \{\; ij\}\; \backslash \; двоеточие\; \backslash \backslash \; x\_\; \{ij\}\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; i,\; j\; =\; 1,\; \backslash \; ldots,\; n;\; \backslash \backslash \; \backslash \; sum\; \_\; \{i\; =\; 1,\; i\; \backslash \; neq\; j\}\; ^\; \{n\}\; x\_\; \{ij\}\; =\; 1\; j\; =\; 1,\; \backslash \; ldots,\; n;\; \backslash \backslash \; \backslash \; sum\; \_\; \{\; j\; =\; 1,\; j\; \backslash \; neq\; i\}\; ^\; \{n\}\; x\_\; \{ij\}\; =\; 1\; i\; =\; 1,\; \backslash \; ldots,\; n;\; \backslash \backslash \; \backslash \; sum\; \_\; \{i\; \backslash \; in\; Q\}\; \{\backslash \; sum\; \_\; \{j\; \backslash \; neq\; i,\; j\; \backslash \; in\; Q\}\; \{x\_\; \{ij\}\}\}\; \backslash \; leq\; |\; Q\; |\; -1\; \backslash \; forall\; Q\; \backslash \; subsetneq\; \backslash \; \{1,\; \backslash \; ldots,\; n\; \backslash \},\; |\; Q\; |\; \backslash \; geq\; 2\; \backslash \backslash \backslash \; конец\; \{выровнено\}\}\}$

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

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

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

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

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

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

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

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

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

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

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

• алгоритмы прогрессивного улучшения, используемые методы, напоминающие линейное программирование. Хорошо работает до 200 городов.
• Реализации ветвления и привязки и генерации разрезов для конкретных задач (ветвей и разрезов ); это метод выбора для решения больших примеров. Этот подход удерживает текущий рекорд, решая случай с 85 900 городами, см. Эпплгейт и др. (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 CPU-лет (Cook et al. 2006). В апреле 2006 г. пример с 85 900 точками был решен с помощью Concorde TSP Solver, что заняло более 136 процессорных лет, см. Эпплгейт и др. (2006).

Были разработаны эвристические и аппроксимирующие алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итерационное улучшение

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

Парный обмен

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метрика

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

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

$d\; AB\; \le \; d\; AC\; +\; d\; CB\; \{\backslash \; displaystyle\; d\_\; \{AB\}\; \backslash \; leq\; d\_\; \{AC\}\; +\; d\_\; \{CB\}\}$.

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

Вот несколько показателей показателей TSP для различных показателей.

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

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

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

Евклидово

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

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

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

$О\; (N\; (журнал\; \; N)\; (O\; (cd))\; d\; -\; 1),\; \{\backslash \; displaystyle\; O\; \backslash \; left\; (n\; (\backslash \; log\; n)\; ^\; \{(O\; (c\; \{\backslash \; sqrt\; \{d\}\}))\; ^\; \{d-1\}\}\; \backslash \; right),\}$

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

На науку проститутки простые эвристики с более слабыми гарантиями.

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

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

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

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

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

	A	B	C
A		1	2
B	6		3
C	5	4

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

Веса симметричных путей

	A	B	C	A′	B′	C ′
A				−w	6	5
B				1	−w	4
C				2	3	−w
A ′	−w	1	2
B ′	6	−w	3
C ′	5	4	−w

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

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

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

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

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

$L\; n\; \ast \; n\; \to \; \beta \; при\; n\; \to \; \infty ,\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{L\_\; \{n\}\; ^\; \{*\}\}\; \{\backslash \; sqrt\; \{n\}\}\}\; \backslash \; rightarrow\; \backslash \; beta\; \backslash \; qquad\; \{\; \backslash \; text\; \{when\}\}\; n\; \backslash \; to\; \backslash \; infty,\}$

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

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

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

• Один имеет $L\; \ast \; \le \; 2\; n\; +\; 2\; \{\backslash \; displaystyle\; L\; ^\; \{*\}\; \backslash \; leq\; 2\; \{\backslash \; sqrt\; \{n\}\}\; +\; 2\}$, и, следовательно, $\beta \; \le \; 2\; \{\backslash \; displaystyle\; \backslash \; beta\; \backslash \; leq\; 2\}$, используя наивный путь, который vi монотонно размещает точки внутри каждого из $n\; \{\backslash \; displaystyle\; \{\backslash \; sqrt\; \{\; n\}\}\}$срезов шириной $1\; /\; n\; \{\backslash \; displaystyle\; 1\; /\; \{\backslash \; sqrt\; \{n\}\}\}$в квадрате.
• Мало кто доказал $L\; n\; \ast \; \le \; 2\; n\; +\; 1.75\; \{\backslash \; displaystyle\; L\_\; \{n\}\; ^\; \{*\}\; \backslash \; leq\; \{\backslash \; sqrt\; \{2n\}\}\; +\; 1.75\}$, следовательно, $\beta \; \le \; 2\; \{\backslash \; displaystyle\; \backslash \; beta\; \backslash \; leq\; \{\backslash \; sqrt\; \{2\}\}\}$, позже улучшенный Karloff (1987): $\beta \; \le \; 0,984\; 2\; \{\backslash \; displaystyle\; \backslash \; beta\; \backslash \; leq\; 0.984\; \{\backslash \; sqrt\; \{2\}\}\}$.
• В некоторых исследованиях сообщалось, что верхняя граница $\beta \; \le \; 0,92\dots \; \{\backslash \; displaystyle\; \backslash \; beta\; \backslash \; leq\; 0.92\; \backslash \; dots\}$.
• Некоторое исследование показало, что верхняя граница $\beta \; \le \; 0,73\dots \; \{\backslash \; displaystyle\; \backslash \; beta\; \backslash \; leq\; 0.73\; \backslash \; dots\}$.

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

• , наблюдая, что $E\; [L\; n\; \ast ]\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{E\}\; [L\_\; \{n\}\; ^\; \{*\}]\}$больше чем $n\; \{\backslash \; displaystyle\; n\}$раз расстояние между $X\; 0\; \{\backslash \; displaystyle\; X\_\; \{0\}\}$и ближайшая точка $X\; i\; \ne \; X\; 0\; \{\backslash \; displaystyle\; X\_\; \{i\}\; \backslash \; neq\; X\_\; \{0\}\}$, получается (после короткого вычисления)

$E\; [L\; n\; \ast ]\; \ge \; 1\; 2\; п.\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{E\}\; [L\_\; \{n\}\; ^\; \{*\}]\; \backslash \; geq\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\; \{\backslash \; sqrt\; \{n\}\}.\}$

• Лучшая нижняя граница получается при наблюдении что $E\; [L\; n\; *]\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{E\}\; [L\_\; \{n\}\; ^\; \{*\}]\}$больше, чем $1\; 2\; n\; \{\backslash \; displaystyle\; \{\backslash \; tfrac\; \{1\; \}\; \{2\}\}\; n\}$, умноженное на величину расстояний между $X\; 0\; \{\backslash \; displaystyle\; X\_\; \{0\}$и ближайшей и второй ближайшими точками $Икс\; я,\; Икс\; j\; \ne \; Икс\; 0\; \{\backslash \; displaystyle\; X\_\; \{i\},\; X\_\; \{j\}\; \backslash \; neq\; X\_\; \{0\}\}$, что дает

$E\; [L\; n\; \ast ]\; \ge \; (1\; 4\; +\; 3\; 8)\; п\; =\; 5\; 8\; N,\; \{\backslash \; Displaystyle\; \backslash \; mathbb\; \{E\}\; [L\_\; \{n\}\; ^\; \{*\}]\; \backslash \; geq\; \backslash \; left\; (\{\backslash \; tfrac\; \{1\}\; \{4\}\}\; +\; \{\backslash \; tfrac\; \{3\}\; \{8\}\}\; \backslash \; right)\; \{\backslash \; sqrt\; \{n\}\}\; =\; \{\backslash \; tfrac\; \{5\}\; \{8\}\}\; \{\backslash \; sqrt\; \{n\}\},\}$

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

$E\; [L\; n\; *]\; \ge \; (\; 5\; 8\; +\; 19\; 5184)\; n,\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{E\}\; [L\_\; \{n\}\; ^\; \{*\}]\; \backslash \; geq\; (\{\backslash \; tfrac\; \{5\}\; \{8\}\}\; +\; \{\backslash \; tfrac\; \{19\}\; \{5184\}\})\; \{\backslash \; sqrt\; \{n\}\},\}$

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

$L\; n\; \ast \; \gtrsim \; 0,7080\; n\; +\; 0,522,\; \{\backslash \; displaystyle\; L\_\; \{n\}\; ^\; \{*\}\; \backslash \; gtrsim\; 0.7080\; \{\backslash \; sqrt\; \{n\}\}\; +\; 0,522,\}$

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

$L\; n\; \ast \; \gtrsim \; 0,7078\; n\; +\; 0,551\; \{\backslash \; displaystyle\; L\_\; \{n\}\; ^\; \{*\}\; \backslash \; gtrsim\; 0.7078\; \{\backslash \; sqrt\; \{n\}\}\; +\; 0.551\}$.

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

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

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

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

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

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

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

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

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

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

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

• Адлеман, Леонард ( 1994), «Молекулярное вычисление решений комбинаторных задач» (PDF), Science, 266 (5187): 1021–4, Bibcode : 1994Sci... 266.1021A, CiteSeerX 10.1.1.54.2565, doi : 10.1126 / science.7973651, PMID 7973 651, заархивировано из оригинала (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 9780691152707.
• Кук, Уильям ; Эспиноза, Даниэль; Goycoolea, Marcos (2007), «Вычисления с неравенствами домино-четности для TSP», INFORMS Journal on Computing, 19 (3): 356–365, doi : 10.1287 / ijoc.1060.0204
• Cormen, Thomas H. ; Лейзерсон, Чарльз Э. ; Ривест, Рональд Л. ; Стейн, Клиффорд (31 июля 2009 г.). «35.2: Задача коммивояжера». Введение в алгоритмы (2-е изд.). MIT Press. С. 1027–1033. ISBN 9780262033848.
• Данциг, Г. Б. ; Фулкерсон Р. ; Джонсон, С.М. (1954), «Решение крупномасштабной задачи коммивояжера», Исследование операций, 2 (4): 393–410, doi : 10.1287 / opre.2.4.393, JSTOR 166695, S2CID 44960960
• Garey, Michael R.; Джонсон, Дэвид С. (1979). «A2.3: ND22–24». Компьютеры и неразрешимость: Руководство по теории NP-полноты. В. Х. Фриман. С. 211–212. ISBN 9780716710448.
• Голдберг, DE (1989), «Генетические алгоритмы в поиске, оптимизации и машинном обучении», чтение: Аддисон-Уэсли, Нью-Йорк: Аддисон-Уэсли, Bibcode : 1989gaso.book..... G, ISBN 978-0-201-15767-3
• Гутин, Г.; Yeo, A.; Зверович, А. (15 марта 2002 г.). «Коммивояжер не должен быть жадным: анализ доминирования жадных эвристик для TSP». Дискретная прикладная математика. 117 (1–3): 81–86. DOI : 10.1016 / S0166-218X (01) 00195-0. ISSN 0166-218X.
• Гутин, Г.; Пуннен, А. П. (18 мая 2007 г.). Задача коммивояжера и ее варианты. Springer США. ISBN 9780387444598.
• Джонсон, Д.С. ; McGeoch, L.A. (1997), "Проблема коммивояжера: пример локальной оптимизации", в Aarts, E.H.L.; Ленстра, Дж. К. (ред.), Локальный поиск в комбинаторной оптимизации (PDF), John Wiley and Sons Ltd., стр. 215–310
• Лоулер, Э. Л.; Шмойс, Д. Б.; Кан, А. Х. Г. Риннуй; Ленстра, Дж. К. (1985). Задача коммивояжера. John Wiley Sons, Incorporated. ISBN 9780471904137.
• MacGregor, J.N.; Ормерод, Т. (1996), «Человеческая деятельность по проблеме коммивояжера» (PDF), Perception Psychophysics, 58 (4): 527–539, doi : 10.3758 / BF03213088, PMID 8934685, S2CID 38355042, заархивировано из оригинал (PDF) от 29 декабря 2009 г.
• Mitchell, JSB (1999), «Гильотинные подразделения аппроксимируют многоугольные подразделения: простая схема аппроксимации полиномиальным временем для геометрической TSP, k-MST и связанных задач», SIAM Journal on Computing, 28 (4): 1298–1309, doi : 10.1137 / S0097539796309764
• Rao, S.; Смит, W. (1998), «Аппроксимация геометрических графов с помощью гаечных ключей и бананов», Proceedings, pp. 540–550, CiteSeerX 10.1.1.51. 8676
• Rosenkrantz, Daniel J.; Стернс, Ричард Э.; Льюис, Филип М., II (1977). «Анализ нескольких эвристик для задачи коммивояжера». SIAM Journal on Computing. SIAM (Общество промышленной и прикладной математики). 6 (5): 563–581. DOI : 10.1137 / 0206041. S2CID 14764079.
• Медведев Андрей; Ли, Майкл; Бутавичус, Марк; Викерс, Дуглас (1 февраля 2001 г.). «Возможности человека при решении визуально представленных задач коммивояжера». Психологические исследования. 65 (1): 34–45. doi : 10.1007 / s004260000031. ISSN 1430-2772. PMID 11505612. S2CID 8986203.
• Уолшоу, Крис (2000), Многоуровневый подход к проблеме коммивояжера, CMS Press
• Уолшоу, Крис (2001), Многоуровневый Лин-Керниган -Алгоритм Хельсгауна для задачи коммивояжера, CMS Press

На Wikimedia Commons есть материалы, связанные с проблемой коммивояжера.

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