Алгоритм Кристофидеса
Приближение для задачи коммивояжера

Алгоритм Христофидеса или алгоритм Христофидеса–Сердюкова — это алгоритм для нахождения приближённых решений задачи коммивояжёра в случаях, когда расстояния образуют метрическое пространство (они симметричны и подчиняются неравенству треугольника ). [1] Это приближённый алгоритм , который гарантирует, что его решения будут находиться в пределах множителя 3/2 от оптимальной длины решения, и назван в честь Никоса Христофидеса и Анатолия Ивановича Сердюкова ; последний открыл его независимо в 1976 году (но публикация датирована 1978 годом). [2] [3] [4]

Алгоритм

Пусть G = ( V , w ) — пример задачи коммивояжера. То есть G — полный граф на множестве вершин V , а функция w присваивает неотрицательный действительный вес каждому ребру G . Согласно неравенству треугольника, для каждых трех вершин u , v , и x должно быть так, что w ( uv ) + w ( vx ) ≥ w ( ux ) .

Тогда алгоритм можно описать на псевдокоде следующим образом. [1]

  1. Создайте минимальное остовное дерево T графа G.
  2. Пусть O — множество вершин с нечетной степенью в T. По лемме о рукопожатии O имеет четное число вершин.
  3. Найдите минимальное по весу совершенное паросочетание M в подграфе , индуцированном в G элементом O.
  4. Объедините ребра M и T, чтобы сформировать связный мультиграф H , в котором каждая вершина имеет четную степень.
  5. Образуем эйлеров контур в H.
  6. Превратите контур, найденный на предыдущем шаге, в гамильтонов контур, пропуская повторяющиеся вершины ( сокращение ).

Шаги 5 и 6 не обязательно дают только один результат; как таковой эвристика может дать несколько различных путей.

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

В худшем случае сложность алгоритма определяется шагом идеального соответствия, который имеет сложность. [2] В статье Сердюкова заявлена ​​сложность, [4] поскольку автору был известен только менее эффективный алгоритм идеального соответствия. [3] О ( н 3 ) {\displaystyle O(n^{3})} О ( н 3 бревно ⁡ н ) {\displaystyle O(n^{3}\log n)}

Коэффициент аппроксимации

Стоимость решения, полученного с помощью алгоритма, находится в пределах 3/2 от оптимума. Чтобы доказать это, пусть C будет оптимальным туром коммивояжера. Удаление ребра из C дает остовное дерево, которое должно иметь вес не меньше веса минимального остовного дерева, что подразумевает, что w ( T ) ≤ w ( C ) - нижняя граница стоимости оптимального решения.

Алгоритм решает проблему, что T не является туром, путем идентификации всех вершин нечетной степени в T ; поскольку сумма степеней в любом графе четна (по лемме о рукопожатии ), существует четное число таких вершин. Алгоритм находит идеальное паросочетание M минимального веса среди вершин нечетной степени.

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

Так как эти два набора путей разделяют ребра C , один из двух наборов имеет не более половины веса C , и благодаря неравенству треугольника его соответствующее паросочетание имеет вес, который также не более половины веса C. Совершенное паросочетание с минимальным весом не может иметь большего веса, поэтому w ( M ) ≤ w ( C )/2 . Сложение весов T и M дает вес эйлерова тура, не более 3 w ( C )/2 . Благодаря неравенству треугольника, даже если эйлеров тур может повторно посещать вершины, сокращение не увеличивает вес, поэтому вес выхода также не более 3 w ( C )/2 . [1]

Нижние границы

Существуют входные данные для задачи коммивояжера, которые заставляют алгоритм Кристофидеса находить решение, коэффициент аппроксимации которого произвольно близок к 3/2 . Один из таких классов входных данных образован путем из n вершин , где ребра пути имеют вес 1 , вместе с набором ребер, соединяющих вершины, отстоящие друг от друга на два шага в пути с весом 1 + ε для числа ε, выбранного близким к нулю, но положительным.

Все оставшиеся ребра полного графа имеют расстояния, заданные кратчайшими путями в этом подграфе. Тогда минимальное остовное дерево будет задано путем длиной n − 1 , и единственные две нечетные вершины будут конечными точками пути, чье идеальное паросочетание состоит из одного ребра с весом приблизительно n /2 .

Объединение дерева и сопоставления представляет собой цикл без возможных сокращений и с весом приблизительно 3 n /2 . Однако оптимальное решение использует ребра веса 1 + ε вместе с двумя ребрами веса 1 , инцидентными конечным точкам пути, и имеет общий вес (1 + ε )( n − 2) + 2 , близкий к n для малых значений ε . Следовательно, мы получаем коэффициент аппроксимации 3/2. [5]

Пример

Дано: полный граф, веса ребер которого подчиняются неравенству треугольника.
Вычислить минимальное остовное дерево T
Вычислить множество вершин O с нечетной степенью в T
Образуем подграф G, используя только вершины O
Построить минимальное по весу идеальное паросочетание M в этом подграфе
Объединить дерево соответствия и остовное дерево T ∪ M, чтобы сформировать эйлеров мультиграф
Вычислить цикл Эйлера

Здесь цикл идет по пути A->B->C->A->D->E->A. Также допустимо A->B->C->A->E->D->A.
Удалим повторяющиеся вершины, что даст выход алгоритма.

Если бы использовался альтернативный маршрут, то сокращение пути было бы от C до E, что приводит к более короткому маршруту (A->B->C->E->D->A), если это евклидов граф, поскольку маршрут A->B->C->D->E->A имеет пересекающиеся линии, что, как доказано, не является кратчайшим маршрутом.

Дальнейшее развитие событий

Этот алгоритм по-прежнему остается лучшим полиномиальным алгоритмом аппроксимации времени для указанной задачи, который был тщательно рецензирован соответствующим научным сообществом для задачи коммивояжера на общих метрических пространствах. В июле 2020 года Карлин, Кляйн и Гаран выпустили препринт, в котором они представили новый алгоритм аппроксимации и заявили, что его коэффициент аппроксимации составляет 1,5 − 10 −36 . Их алгоритм является рандомизированным и следует принципам, аналогичным алгоритму Кристофидеса, но использует случайно выбранное дерево из тщательно выбранного случайного распределения вместо минимального остовного дерева. [6] [7] Статья была опубликована на STOC'21 [8] , где она получила награду за лучшую статью. [9]

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

О ( н ( бревно ⁡ н ) ( О ( с г ) ) г − 1 ) {\displaystyle O\left(n(\log n)^{(O(c{\sqrt {d}}))^{d-1}}\right)} время;

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

Ссылки

  1. ^ abc Goodrich, Michael T. ; Tamassia, Roberto (2015), "18.1.2 Алгоритм приближения Христофидеса", Algorithm Design and Applications , Wiley, стр. 513–514.
  2. ^ ab Christofides, Nicos (1976), Анализ наихудшего случая новой эвристики для задачи коммивояжера (PDF) , Отчет 388, Высшая школа промышленного администрирования, CMU, архив (PDF) из оригинала 21 июля 2019 г.
  3. ^ ab van Bevern, René; Slugina, Viktoriia A. (2020), "Историческая заметка об алгоритме 3/2-аппроксимации для метрической задачи коммивояжера", Historia Mathematica , 53 : 118–127, arXiv : 2004.02437 , doi : 10.1016/j.hm.2020.04.003, S2CID  214803097
  4. ^ ab Сердюков, Анатолий (1978), «О некоторых экстремальных обходах в графах» [О некоторых экстремальных блужданиях в графах] (PDF) , Управляемые системы (Управляемые системы) (на русском языке), 17 : 76–79
  5. ^ Блазер, Маркус (2008), «Метрическая TSP», в Као, Минг-Янг (редактор), Энциклопедия алгоритмов} , Springer-Verlag, стр. 517–519, ISBN 9780387307701.
  6. ^ Карлин, Анна Р.; Кляйн, Натан; Гаран, Шаян Овейс (30.08.2020). «(Немного) улучшенный алгоритм аппроксимации для метрической задачи коммивояжера». arXiv : 2007.01409 [cs.DS].
  7. ^ Кларрайх, Эрика (8 октября 2020 г.). «Ученые-компьютерщики побили рекорд коммивояжера». Журнал Quanta . Получено 10 октября 2020 г.
  8. ^ Карлин, Анна Р.; Кляйн, Натан; Гаран, Шаян Овейс (2021-06-15), "(Немного) улучшенный алгоритм аппроксимации для метрической задачи TSP", Труды 53-го ежегодного симпозиума ACM SIGACT по теории вычислений , Нью-Йорк, США: Ассоциация вычислительной техники, стр. 32–45, arXiv : 2007.01409 , doi : 10.1145/3406325.3451009, ISBN 978-1-4503-8053-9, получено 2022-04-20(версия 2023 года)
  9. ^ "ACM SIGACT - STOC Best Paper Award". www.sigact.org . Получено 20 апреля 2022 г.
  10. ^ Санджив Арора, Схемы аппроксимации полиномиального времени для евклидовых задач коммивояжера и других геометрических задач, Журнал ACM 45(5) 753–782, 1998.
  • Определение алгоритма NIST Christofides
Взято с "https://en.wikipedia.org/w/index.php?title=Christofides_algorithm&oldid=1250833332"