Просмотр кода страницы Задача коммивояжёра

{{значения|TSP}}
[[Файл:TSP Deutschland 3.png|мини|Это оптимальный маршрут коммивояжёра через 14 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных {{num|43589145600}} вариантов.]]
'''Задача [[коммивояжёр]]а''' (или '''TSP''' от {{lang-en|travelling salesman problem}}) — одна из самых известных задач [[Комбинаторная оптимизация|комбинаторной оптимизации]], заключающаяся в поиске самого выгодного [[маршрут (теория графов)|маршрута]], проходящего через указанные города ровно по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди [[Гамильтонов цикл|гамильтоновых циклов]]. Существует несколько частных случаев общей постановки задачи, в частности, [[геометрическая задача коммивояжёра]] (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), [[метрическая задача коммивояжёра]] (когда на матрице стоимостей выполняется [[неравенство треугольника]]), [[Симметричная задача коммивояжёра|симметричная]] и [[Асимметричная задача коммивояжёра|асимметричная задачи коммивояжёра]]. Также существует обобщение задачи, так называемая [[обобщённая задача коммивояжёра]].

Оптимизационная постановка задачи относится к классу [[NP-трудность|NP-трудных]] задач, впрочем, как и большинство её частных случаев. Версия «decision problem» (то есть такая, в которой ставится вопрос, существует ли маршрут не длиннее, чем заданное значение {{mvar|k}}) относится к классу [[NP-полная задача|NP-полных задач]]. Задача коммивояжёра относится к числу [[Трансвычислительная задача|трансвычислительных]]: уже при относительно небольшом числе городов (>66) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.

== История ==
С задачей коммивояжёра связана задача о поиске [[гамильтонов цикл|гамильтонового цикла]]. Примером такой задачи является [[задача о ходе коня|задача о ходе шахматного коня]], известная по крайней мере с XVIII века{{sfn|''Gross J. L., Yellen J.'' Graph theory and its applications, 2006|loc=с. 275}}. [[Эйлер, Леонард|Леонард Эйлер]] посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию», датированную 1759 годом<ref>Euler, Leonhard, [https://scholarlycommons.pacific.edu/euler-works/309/ Solution d’une question curieuse que ne paroit soumise à aucune analyse] {{Wayback|url=https://scholarlycommons.pacific.edu/euler-works/309/ |date=20210819195423 }}, Mémoires de l’académie des sciences de Berlin, 15 (1759) 1766, p. 310—337.</ref>. Другим примером задачи на поиск гамильтонового цикла является [[икосиан]]: математическая головомка, в которой надо пройти по [[додекаэдр]]у (графу с 20 узлами) побывав в каждой вершине ровно один раз. Эта задача была предложена [[Гамильтон, Уильям Роуэн|Уильямом Гамильтоном]] в XIX веке, он же определил класс таких путей.

В 1832 году издана книга с названием «Коммивояжёр — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера» ({{lang-de|Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur}}), в которой описана задача, но математический аппарат для её решения не применяется. Зато в ней предложены примеры маршрутов для некоторых регионов Германии и Швейцарии.

Первые упоминания в качестве математической задачи на [[Оптимизация|оптимизацию]] принадлежат [[Менгер, Карл (младший)|Карлу Менгеру]], который сформулировал её на математическом коллоквиуме в 1930 году так:
{{цитата|Мы называем задачей посыльного (поскольку этот вопрос возникает у каждого почтальона, в частности, её решают многие путешественники) задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно.}}
[[Файл:WilliamRowanHamilton.jpeg|thumb|Гамильтон Уильям Роуэн]]

Вскоре появилось известное сейчас название ''задача странствующего торговца'' ({{lang-en|traveling salesman problem}}), которую предложил [[Уитни, Хасслер|Хасслер Уитни]] ({{lang-en|Hassler Whitney}}) из [[Принстонский университет|Принстонского университета]].

Вместе с простотой определения и сравнительной простотой нахождения хороших решений задача коммивояжёра отличается тем, что нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины XX века исследование задачи коммивояжёра имеет не столько практический смысл, сколько теоретический в качестве модели для разработки новых алгоритмов оптимизации.

Многие современные распространенные методы [[Комбинаторная оптимизация|дискретной оптимизации]], такие как [[Алгоритм Гомори|метод отсечений]], [[метод ветвей и границ|ветвей и границ]] и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжёра.

В 1950-е и 1960-е годы задача коммивояжёра привлекла внимание ученых в США и Европе. Важный вклад в исследование задачи принадлежит [[Данциг, Джордж|Джорджу Данцигу]], Делберту Рею Фалкерсону ({{lang-en|Delbert Ray Fulkerson}}) и Селмеру Джонсону ({{lang-en|Selmer M. Johnson}}), которые в 1954 году в институте [[RAND (корпорация)|RAND Corporation]] сформулировали задачу в виде задачи дискретной оптимизации и применили для её решения [[Алгоритм Гомори|метод отсечений]]. Используя этот метод, они построили путь коммивояжёра для одной частной постановки задачи с 49 городами и обосновали его оптимальность. В 1960-е и 1970-е годы задача изучалась многими учеными как теоретически, так и с точки зрения её приложений в информатике, экономике, химии и биологии.

[[Карп, Ричард Мэннинг|Ричард Карп]] в 1972 году доказал [[NP-полная задача|NP-полноту]] задачи поиска гамильтоновых путей, из чего, благодаря полиномиальной сводимости, вытекала NP-трудность задачи коммивояжёра. На основе этих свойств им было приведено теоретическое обоснование сложности поиска решений задачи на практике.

Больших успехов удалось достичь в конце 1970-х и 1980-х годах, когда Мартин Грётчел ({{lang-de|Martin Grötschel}}), Манфред Падберг ({{lang-de|Manfred Padberg}}) и Джованни Ринальди ({{lang-it|Giovanni Rinaldi}}) и другие, с применением новых методов деления плоскостью, ветвей и границ вычислили решение для отдельного случая задачи с 2393 городами.

В 1990-е годы Дэвид Аплгейт ({{lang-en|David Applegate}}), Роберт Биксби ({{lang-en|Robert Bixby}}), Вашек Хватал ({{lang-cs|Vašek Chvátal}}) и Уильям Кук ({{lang-en|William Cook}}) установили рекорды по программе Конкорд. Герхард Райнельт ({{lang-de|Gerhard Reinelt}}) создал TSPLIB — набор стандартизованных экземпляров задачи коммивояжёра различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33 810 узлами была решена программой ''Конкорд'': был вычислен путь длиной в 66 048 945 и доказано отсутствие более коротких путей. В апреле 2006 было найдено решение для экземпляра с 85 900 узлами. Используя [[метод декомпозиции|методы декомпозиции]], можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее, чем на 1 % больше оптимальной.

== Формальное определение ==

=== Представление в виде графа ===
[[Файл:Weighted_K4.svg|thumb|Симметричная задача для четырёх городов.]]
Для возможности применения математического аппарата для решения задачи её следует представить в виде [[Математическая модель|математической модели]]. Задачу коммивояжёра можно представить в виде модели на [[Граф (математика)|графе]], то есть, используя вершины и ребра между ними. Таким образом, вершины графа соответствуют городам, а рёбра <math>\left ( i,j \right )</math> между вершинами <math>i</math> и <math>j</math> — пути сообщения между этими городами. Каждому ребру <math>\left ( i,j \right )</math> можно сопоставить критерий выгодности маршрута <math>c_{ij} \geqslant 0</math>, который можно понимать как, например, расстояние между городами, время или стоимость поездки.

[[Гамильтонов граф|Гамильтоновым циклом]] называется маршрут, включающий ровно по одному разу каждую вершину графа.

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

Таким образом, решение задачи коммивояжёра — это нахождение гамильтонова цикла минимального веса в [[Полный граф|полном]] взвешенном графе.

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

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

В случае симметричной задачи все пары ребер между одними и теми же вершинами имеют одинаковую длину, то есть, для ребра <math>\left ( i,j \right )</math> одинаковы длины <math>c_{ij} = c_{ji}</math>. В симметричном случае количество возможных маршрутов вдвое меньше асимметричного случая. Симметричная задача моделируется неориентированным графом (см. рисунок).

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

==== Метрическая задача ====
Симметричную задачу коммивояжёра называют ''метрической'', если относительно длин ребер выполняется [[неравенство треугольника]]. Условно говоря, в таких задачах обходные пути длиннее прямых, то есть ребро от вершины <math>i</math> до вершины <math>j</math> никогда не бывает длиннее пути через промежуточную вершину <math>k</math>:
: <math>c_{ij} \leqslant c_{ik} + c_{kj}</math>.
Такое свойство длины ребер определяет [[Измеримое множество|измеримое пространство]] на множестве ребер и меру расстояния, удовлетворяющую интуитивному пониманию расстояния.

Распространенные на практике функции расстояния являются также метриками и удовлетворяют неравенству треугольника:
* ''Евклидово расстояние'' в евклидовой задаче коммивояжёра,
* ''Манхэттенская метрика'' (также квартальная метрика) прямоугольной задачи коммивояжёра, в которой расстояние между вершинами на решетке равно сумме расстояний по оси ординат и абсцисс,
* ''Максимальная метрика'', определяющая расстояние между вершинами решетчатого графа как максимальное значение расстояния вдоль оси ординат и абсцисс.

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

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

Если на практике в условиях задачи разрешается посещать города несколько раз, то симметричную задачу можно свести к метрической. Для этого задачу рассматривают на так называемом графе расстояний. Этот граф имеет такое же множество вершин, как и исходный, и является полностью связным. Длина рёбер <math>c_{ij}</math> между вершинами <math>i</math> и <math>j</math> на графе расстояний соответствует длине кратчайшего расстояния между вершинами <math>i</math> и <math>j</math> в исходном графе. Для определённых таким образом длин <math>c_{ij}</math> выполняется неравенство треугольника, и каждому маршруту на графе расстояний всегда соответствует маршрут с возможными повторениями вершин в исходном графе.

=== Формулировка в виде задачи дискретной оптимизации ===
Одним из подходов к решению задачи является формулировка её в виде задачи дискретной оптимизации, при этом решения представляются в виде переменных, а связи — в виде отношений неравенства между ними. Таким образом, возможно несколько вариантов. Например, симметричную задачу можно представить в виде множества ребер <math>V</math>. Каждому ребру <math>\{i, j\}</math> сопоставляется двоичная переменная <math>x_{ij} \in \{0,1\}</math>, равная 1, если ребро принадлежит маршруту, и 0 — в противном случае. Произвольный маршрут можно представить в виде значений множества переменных принадлежности, но не каждое такое множество определяет маршрут. Условием того, что значения множества переменных определяют маршрут, являются описанные далее линейные неравенства.
[[Файл:TSP_degree_constraints.png|thumb|Условие кратности: каждая вершина должна иметь одно входное и одно выходное ребро маршрута.]]
Каждая вершина должна сообщаться через пару ребер с остальным вершинам, то есть, через входное и выходное ребро:
: <math>\forall i \in V,\; \sum_{j \in V \setminus \{i\}} x_{ij} = 2 \qquad (1)</math>
В сумме каждое слагаемое <math>x_{ij}</math> равно или 1 (принадлежит маршруту) или 0 (не принадлежит). То есть, полученная сумма равна количеству ребер в маршруте, имеющих вершину <math>i</math> на одном из концов. Она равна 2, так как каждая вершина имеет входное и выходное ребро. В приведенном рядом рисунке вершина <math>i</math> показана с входным и выходными ребрами, а ребра маршрута обозначены толстыми линиями. Рядом с ребрами указаны длины <math>x_{ij}</math>, прилагаемые к указанной выше сумме.
[[Файл:TSP_short_cycles.png|thumb|Циклы: переменные удовлетворяют условию кратности, но не определяют маршрут.]]
Описанные ранее условия кратности выполняются не только маршрутами, но и значениями переменных, соответствующих отдельным циклам, где каждая вершина принадлежит лишь одному циклу (см. рисунок). Чтобы избежать подобных случаев, должны выполняться так называемые неравенства циклов (или условия устранения подмаршрутов), которые были определены Данцигом, Фалкерсоном и Джонсоном в [[1954 год]]у под названием ''условия петель'' ({{lang-en|loop conditions}}). Этими неравенствами определялось дополнительное условие того, что каждое множество вершин <math>S \subset V</math> является либо пустым, либо содержит все вершины, сочетающееся с остальным вершинам через минимум два ребра:
: <math>\sum_{i \in S, \; j \notin S} x_{ij} \geqslant 2 \qquad (2)</math>

для всех множеств вершин <math>S</math>, где <math>1 \leqslant |S| \leqslant |V|-1</math>. Эта сумма равна сумме длин ребер маршрута между вершиной <math>i \in S</math> и вершиной <math>j \notin S</math>. Чтобы устранить лишние неравенства, можно ограничиться множествами вершин <math>S</math> с минимум двумя и максимум <math>|V| - 2</math> вершинами. На рисунке рядом ребра <math>\{i,j\}</math> с длинами <math>x_{ij} = 1</math> обозначены толстыми линиями, остальные ребра имеют длину <math>x_{ij} = 0</math>. Введение дополнительных условий (2) для множества вершин <math>S</math>, состоящего из трех левых вершин, будет гарантировать, что <math>S</math> сочетается через минимум два ребра маршрута с тремя вершинами справа, чтобы устранить оба цикла. Количество неравенств устранения циклов согласно Данцигу, Фалкерсону и Джонсону равняется <math>2^{n}-2(n-1)</math>.

В [[1960 год]]у Миллер, Такер и Землин изобрели альтернативные условия устранения подмаршрутов путём введения <math>n</math> новых переменных, определяющих порядок посещенных городов, требующих только <math>n^2 - n + 1</math> дополнительных неравенств. Более того, из-за двойственности <math>x_{ij}</math> в формулировках Миллера, Такера и Землина задача коммивояжёра остается NP-сложной.

Так, каждый вектор с элементами, равными 0 и 1, удовлетворяющий всем неравенствам, определяет корректный маршрут, который является решением переформулированной задачи коммивояжёра: вычислить
: <math>\min \; \left\{ \sum_{i \in V} \sum_{j \in V \setminus \{i\}} c_{ij} x_{ij} \;|\; x \mbox{ valid (1) (2),}\; x_{ij} \in \{0,1\} \right\}. \qquad (3)</math>
Поскольку переменные <math>x_{ij}</math> имеют значения только 0 и 1, сумма равна общей длине <math>c_{ij}</math> ребер <math>\{i,j\}</math>, принадлежащих маршруту.

Количество неравенств типа (2) растет [[Экспоненциальная сложность|экспоненциально]] по мере увеличения количества городов, поскольку почти каждое из <math>2^{|V|}</math> подмножеств узлов определяет одно неравенство. Эту задачу можно решить применением [[Алгоритм Гомори|метода отсечения плоскостью]], благодаря которому неравенства добавляются, только когда эти неравенства действительно необходимы. С геометрической точки зрения, линейные неравенства можно представить как [[гиперплоскость|гиперплоскости]] в пространстве переменных. Множество векторов, удовлетворяющих этим неравенствам, образуют в таком пространстве [[политоп]] (многомерный многогранник), или многомерный многоугольник, точная форма определяется длинами <math>c_{ij}</math> и является в основном неизвестной. Однако, можно показать, что условия (1) и (2) определяют грани (фацет) политопа, то есть боковые поверхности политопа с наивысшей размерностью. Поэтому они относятся к самым сильным линейным неравенствам, которые могут описывать маршрут. Также существует много разных граней, определяемых неравенствами, известными лишь в немногих случаях. Хотя (1) и (2) вместе с ограничениями полностью моделируют задачу только для двоичных векторов, эти неравенства могут использоваться в [[метод ветвей и границ|методе ветвей и границ]], чтобы отбросить решения методами линейной оптимизации с нецелыми координатами (см. раздел точные методы ниже).

== Алгоритмическая сложность ==
Поскольку коммивояжёр в каждом из городов встает перед выбором следующего города из тех, что он ещё не посетил, существует <math>(n-1)!</math> маршрутов для асимметричной и <math>(n-1)!/2</math> маршрутов для симметричной задачи коммивояжёра. Таким образом, размер пространства поиска [[Временная сложность алгоритма|факториально]] зависит от количества городов.

Различные варианты задачи коммивояжёра (метрическая, симметричная и асимметричная) NP-эквивалентны. Согласно распространенной, но недоказанной гипотезе о неравенстве классов сложности P и NP, не существует детерминированной [[машина Тьюринга|машины Тьюринга]], способной находить решения экземпляров задачи за полиномиальное время в зависимости от количества городов.

Также известно, что при условии <math>P \neq NP</math> не существует алгоритма, который для некоторого полинома <math>p</math> вычислял бы такие решения задачи коммивояжёра, которые отличались бы от оптимального максимум на коэффициент <math>2^{p(n)}</math>.

На практике поиск строго оптимального маршрута требуется не всегда.
Существуют алгоритмы поиска приближенных решений для метрической задачи за полиномиальное время и нахождения маршрута максимум вдвое длиннее оптимального. До сих пор не известен ни один алгоритм с полиномиальным временем, который бы гарантировал точность лучшую, чем 1,5 от оптимальной. По предположению <math>P \neq NP</math>, существует (неизвестная) константа <math>c > 0</math>, такая, что ни один алгоритм с полиномиальным временем не может гарантировать точность <math>1 + c</math>. Как было показано Арора, для евклидовой задачи коммивояжёра существует схема полиномиального времени [[Приближенная схема полиномиального времени|PTAS]] для поиска приближённого решения.

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

== Замкнутый и незамкнутый варианты задачи ==
В замкнутом варианте задачи коммивояжёра требуется посетить все вершины графа, после чего вернуться в исходную вершину. Незамкнутый вариант отличается от замкнутого тем, что в нём не требуется возвращаться в стартовую вершину.

Незамкнутый вариант задачи сводится к замкнутому путём замены весов дуг, входящих
в стартовую вершину, на число 0. Оптимальный замкнутый маршрут коммивояжёра в таком графе соответствует оптимальному незамкнутому маршруту в исходном графе.

Чтобы свести замкнутый вариант к незамкнутому, нужно определить число <math>K</math>, строго превосходящее вес любого маршрута коммивояжёра в заданном графе (например, в качестве <math>K</math> можно взять сумму максимальных по весу дуг, выходящих из каждой вершины, увеличенную на 1). Затем нужно добавить к графу новую вершину <math>v_n</math> (предполагаем, что вершины исходного графа пронумерованы числами от 0 до <math>n-1</math>, при этом стартовая вершина имеет номер 0). Стоимости дуг, выходящих и входящих в вершину <math>v_n</math>, определяются следующим образом:

* <math>c_{n, i} = 3K</math>
* <math>c_{0, n} = 3K</math>
* <math>c_{i, n} = c_{i, 0} + 2K</math> при <math>i</math> от <math>1</math> до <math>n-1</math>

Оптимальный незамкнутый маршрут коммивояжёра в таком графе соответствует оптимальному замкнутому маршруту коммивояжёра в исходном графе и имеет стоимость на <math>2K</math> больше.

== Методы решения ==

=== Простейшие ===
* [[полный перебор]]
* [[случайный перебор]]
* [[жадные алгоритмы]]
** [[Алгоритм ближайшего соседа в задаче коммивояжёра|метод ближайшего соседа]]
** [[метод включения ближайшего города]]
** [[метод самого дешёвого включения]]
* [[Минимальное остовное дерево|метод минимального остовного дерева]]
* [[Алгоритм имитации отжига|метод имитации отжига]]

Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра — методы [[Эвристический алгоритм|эвристические]]. Большинство эвристических методов находит не самый эффективный маршрут, а [[приближённое решение]]. Зачастую востребованы так называемые [[any-time-алгоритмы]]{{Уточнить}}<!-- может, это называется как-нибудь по-русски?-->, то есть, постепенно улучшающие некоторое текущее приближенное решение.

Примером простейшего метода решения метрического варианта задачи является использование минимальных остовных деревьев, дающее решение с фактором аппроксимации <math>2</math> и имеющее временную сложность <math>O(n^2 \log n)</math>. Идея заключается в том, что каждый связный граф содержит нижний порог стоимости его подграфа — минимальное остовное дерево, и в том, что любой цикл, посещающий каждую вершину графа минимум один раз, может быть трансформирован в оптимальный с точки зрения стоимости маршрут при использовании метрики:

# Найди минимальное остовное дерево <math>T</math> графа <math>G</math>.
# Создай граф <math>T'</math>, удвоив все рёбра в <math>T</math>. Так все вершины в <math>T'</math> имеют чётное количество рёбер.
# Найди в <math>T'</math> [[эйлеров цикл]] <math>C'</math>.
# Сократи <math>C'</math>, пропуская удвоенные рёбра, получив цикл <math>C</math>.
# Выведи <math>C</math>.

Значение фактора аппроксимации доказывается следующим образом: Пусть <math>T</math> — минимальное остовное дерево, <math>T'</math> — то же дерево, но с удвоенными рёбрами, <math>C'</math> — эйлеров цикл на графе <math>T'</math>, <math>C</math> — результат работы алгоритма, <math>C^*</math> — минимальный маршрут. Заметим, что <math>c(T) \leqslant c(C^* - e) \leqslant c(C^*)</math>, а также <math>c(C) \leqslant c(C') = 2 \cdot c(T) </math>. Тогда фактор аппроксимации равен <math>\frac{C}{C^*} \leqslant \frac{2 \cdot c(T)}{c(C^*)} \leqslant \frac{2 \cdot c(C^*)}{c(C^*)} = 2</math>.

Однако вышеописанный метод можно оптимизировать, увеличивая число рёбер у вершин с нечётным количеством соседей на 1, что соответствует паросочетанию «нечётных» вершин. Важно заметить, что количество «нечётных» вершин всегда чётно, исходя из [[Лемма о рукопожатиях|леммы о рукопожатиях]]. В таком случае оптимизированный алгоритм имеет фактор аппроксимации <math>3/2</math> и временную сложность <math>O(n^3)</math>. Перед доказательством покажем, что <math>c(M) \leqslant c(C^*)/2</math>, где <math>M</math> — паросочетание, а <math>C^*</math> — оптимальный маршрут: Пусть <math>U</math> — множество «нечётных» вершин минимального остовного дерева <math>T</math>, а <math>C''</math> — цикл, полученный из <math>C^*</math> путем пропуска вершин <math>V \setminus U</math>. Очевидно, что <math>C''</math> имеет чётную длину, а также два непересекающихся максимальных паросочетания <math>M_1</math> и <math>M_2</math>, для которых справедливо <math>c(M) \leqslant c(M_1)</math> и <math>c(M) \leqslant c(M_2)</math>. Из этого следует, что <math>2 \cdot c(M) \leqslant c(M_1) + c(M_2) = c(C'') \leqslant c(C^*)</math>, а значит <math>c(M) \leqslant c(C^*)/2</math>. Исходя из этого найдем фактор аппроксимации алгоритма: <math>\frac{c(C)}{c(C^*)} \leqslant \frac{c(T)+c(M)}{c(C^*)} \leqslant \frac{c(C^*) + c(C^*)/2}{c(C^*)} \leqslant \frac{1.5 \cdot c(C^*)}{c(C^*)} = 1.5</math>.

Существуют также постановки, в которых задача коммивояжёра становится [[NP-полная задача|NP-полной]]. Обычно такие постановки выглядят следующим образом: существует ли на заданном графе {{mvar|G}} такой обход, что его стоимость не превышает {{mvar|x}}. Часто на ней проводят обкатку новых подходов к эвристическому сокращению [[Полный перебор|полного перебора]].

На практике применяются различные модификации более эффективных методов: [[метод ветвей и границ]] и [[генетический алгоритм|метод генетических алгоритмов]], а также [[Муравьиный алгоритм|алгоритм муравьиной колонии]].

=== Метод ветвей и границ ===
{{главная|Метод ветвей и границ}}
Можно найти точное решение задачи коммивояжёра, то есть «вручную» вычислить длины всех возможных маршрутов и выбрать маршрут с наименьшей длиной. Однако даже для небольшого количества городов решать задачу таким способом практически невозможно. Для простого варианта, симметричной задачи с <math>n</math> городами, существует <math>(n-1)!/2</math> возможных маршрутов, то есть для 15 городов существует 43 миллиарда маршрутов и для 18 городов уже 177 триллионов. То, как стремительно растет продолжительность вычислений, можно показать на следующем примере. Если бы существовало устройство, находящее решение для 30 городов за час, то для двух дополнительных городов требуется в тысячу раз больше времени; то есть, более чем 40 суток.
[[Файл:TSP_cutting_plane.png|thumb|Задача коммивояжёра для трех городов: красная пунктирная плоскость <math>x_1 + x_2 + x_3 \geqslant 2</math> отсекает все недопустимые решения с максимум одним ребром. Все точки в красном политопе удовлетворяют этому неравенству, и единственная допустимая точка это (1, 1, 1).]]

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

В геометрической интерпретации эти методы рассматривают задачу как выпуклый политоп, то есть многомерный многоугольник в <math>m</math>-мерном единичном кубе <math>[0,1]^m</math>, где <math>m</math> равно количеству ребер в графе. Каждая вершина этого единичного куба соответствует маршруту, то есть вектору с элементами 0/1, что удовлетворяет описанным выше линейным неравенствам. Гиперплоскости, описываемые этими неравенствами, отсекают такие ребра единичного куба, которые не соответствуют ни одному маршруту.

На рисунке рядом показано применение метода для задачи с тремя узлами. В соответствие трем возможным ребрам между вершинами сопоставляются бинарные переменные <math>x_1,\, x_2</math> и <math>x_3</math>. В этом случае существует лишь один возможный маршрут, а именно тот, что проходит через три вершины. Этот маршрут удовлетворяет неравенству <math>x_1 + x_2 + x_3 \geqslant 2</math>, которое утверждает, что маршрут должен проходить через минимум две вершины. Кроме этого маршрута, что соответствует вектору (1,1,1), неравенству удовлетворяют также все точки в отмеченной красным части этого неравенства. Плоскости, проходящие через красные линии, отсекают все углы, отвечающие несуществующим маршрутам с максимум одним ребром, а именно, ноль-вектор (0, 0, 0), единичные векторы (1, 0, 0), (0, 1, 0) и (0, 0, 1). Сильное неравенство <math>x_1 + x_2 + x_3 \geqslant 3</math> отсечет от единичного куба все, кроме единственной допустимой точки (1, 1, 1). В этом отдельном случае тот же эффект можно получить тремя неравенствами типа (1).

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

Однако этого метода для быстрого поиска маршрутов обычно недостаточно. Основное преимущество точных методов заключается в том, что имея достаточно времени, они вычисляют кратчайший маршрут.
Имея нижнюю границу для оптимальных решений, можно оценить то, насколько отличается найденный маршрут от оптимального. Например, имея нижнюю границу на уровне 100, и после нахождения маршрута длиной 102, оптимальный маршрут может находиться в пределах от 100 до 102. Так называемый ''интервал оптимальности'', или максимальное относительное расстояние между длиной оптимального маршрута и кратчайшим известным маршрутом составит (102—100)/100 = 2 %, то есть длина найденного маршрута 102 максимум на 2 % отличается от оптимальной. Когда длина вычисленного маршрута равна длине предыдущего, считается, что найденное решение является оптимальным. Для поиска маршрутов приемлемой длины точные методы могут комбинироваться с эвристическими.

Метод ветвей и границ для решения задачи коммивояжёра был предложен в [[1963 год]]у группой авторов (Дж. Литл, К. Мурти, Д. Суини, К. Кэрол)<ref>Кэрел К. , Литл Д. , Мурти К. , Суини Д. АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧИ О КОММИВОЯЖЕРЕ // Экономика и математические методы. — 1965. — T. 1. — Выпуск № 1 °C. 94-107 .</ref>.

=== Метод эластичной сети ===
{{См. также|Упругая карта|Выпуклая оболочка}}
{{переработать раздел|дата=2016-05-07}}<!-- Слишком туманно написано, невозможно понять в чём заключается метод -->

==== История ====
В 1987 году его использовали Дурбин (Durbin) и Уиллшоу (Willshaw), указавшие аналогию с механизмами установления упорядоченных нейронных связей<ref>{{Статья|автор=Richard Durbin, David Willshaw|заглавие=An analogue approach to the travelling salesman problem using an elastic net method|ссылка=http://www.nature.com/nature/journal/v326/n6114/abs/326689a0.html|язык=en|издание=Nature|год=1987-04-22|том=326|выпуск=6114|страницы=689–691|doi=10.1038/326689a0|archivedate=2016-04-23|archiveurl=https://web.archive.org/web/20160423174407/http://www.nature.com/nature/journal/v326/n6114/abs/326689a0.html}}</ref>.

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

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

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

Дурбин и Уиллшоу показали, что для задачи с 30 городами, рассмотренной Хопфилдом и Танком, метод эластичной сети генерирует наикратчайший маршрут примерно за 1000
итераций. Для 100 городов найденный этим методом маршрут лишь на 1 % превосходил оптимальный.

=== Муравьиный алгоритм ===
{{главная|Муравьиный алгоритм}}

=== Генетический алгоритм ===
{{главная|Генетический алгоритм}}

=== Алгоритм динамического программирования ===
Основная идея заключается в вычислении и запоминании пути от исходного города и до каждого из остальных городов, затем суммирования этой величины с путем из каждого из остальных городов до оставшихся городов и т. д. Преимущество данного метода <math>D</math> перед методом полного перебора <math>F</math> заключается в существенном сокращении полного объёма вычислений <math>P_{D}=(6n-1)-n2^{n-1}+4n(n-1)2^{n-2}, P_{F}= n! \approx n^ne^{-n}\sqrt{2 \pi n}, P_{D} \ll P_{F}</math> за счет заметного увеличения объёма памяти <math>Q_{D} \sim 2^n \sqrt{\frac{2n}{\pi}}, Q_{F}= 2, Q_{D} \gg Q_{F}</math><ref>''Корбут А. А., Финкельштейн Ю. Ю.'' Дискретное программирование. — М., Наука, 1969. — C. 258—264</ref>.

== См. также ==<!--эти все ссылки должны быть в статье, а не в этой секции-->
* [[Исследование операций]]
* [[Математическое программирование]]
* [[Транспортная логистика]]
* [[Проблема Штейнера]]

== Примечания ==
{{примечания}}

== Литература ==
* {{source|Q21694522|part=Глава 3. Метод грубой силы: Задача коммивояжёра|pages=159—160}}
* {{книга
|автор = Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн
|заглавие = '''Алгоритмы: построение и анализ'''
|оригинал = Introduction to Algorithms
|ссылка = 
|издание = 2-е изд
|место =  М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
|год = 2006
|страницы = 1296
|isbn = 0-07-013151-1
}}
* {{книга
|автор = В.И. Мудров
|заглавие = '''Задача о коммивояжёре'''
|оригинал = 
|ссылка = 
|издание = 
|место =  М.
|издательство = [[Знание (издательство, Москва)|«Знание»]]
|год = 1969
|страницы = 62
|isbn = 
}}
* {{книга
|автор = Ежов А., Шумский С.
|заглавие = '''Нейрокомпьютинг и его применения в экономике и бизнесе '''
|оригинал = 
|ссылка = 
|издание = 
|место =  М.
|издательство = [[МИФИ]]
|год = 1998
|страницы = 216
|isbn = 
}}
* {{h|''Gross J. L., Yellen J.'' Graph theory and its applications, 2006|3=
''Gross J. L., Yellen J.'' Graph theory and its applications. Second edition. Boca Raton—London—New York: Chapman & Hall/CRC, 2006.
}}

{{rq|style|refless}}
{{NP-полные задачи}}

[[Категория:Теория графов]]
[[Категория:Вычислительные задачи теории графов]]
[[Категория:Комбинаторика]]
[[Категория:NP-полные задачи]]
[[Категория:Гамильтоновы пути и циклы]]
[[Категория:Исследование операций]]
[[Категория:Задача коммивояжёра|*]]