Алгоритм Христофидеса - Christofides algorithm

Христофидес алгоритм или алгоритм Христофидеса-Сердюки представляет собой алгоритм для нахождения приближенных решений к задаче коммивояжера , на тех случаях , когда расстояния образуют метрическое пространство (они симметричны и подчиняются неравенство треугольника ). Это приближенный алгоритм, который гарантирует, что его решения будут в пределах 3/2 от оптимальной длины решения, и назван в честь Никоса Христофидеса и Анатолия Сердюкова , которые независимо открыли его в 1976 году.

Этот алгоритм до сих пор остается лучшим алгоритмом аппроксимации полиномиальным временем, который был тщательно проверен соответствующим научным сообществом для решения задачи коммивояжера на общих метрических пространствах. Однако в июле 2020 года Карлин, Кляйн и Гаран выпустили препринт, в котором они представили новый алгоритм аппроксимации и заявили, что его коэффициент аппроксимации составляет 1,5 - 10 −36 . Их метод следует принципам, аналогичным алгоритму Кристофидеса, но использует случайно выбранное дерево из тщательно подобранного случайного распределения вместо минимального остовного дерева.

Алгоритм

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

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

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

Коэффициент приближения

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

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

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

Пример

Metrischer Graph mit 5 Knoten.svg Дано: полный граф, веса ребер которого подчиняются неравенству треугольника
Кристофидес MST.svg Вычислить минимальное остовное дерево T
V'.svg Вычислить множество вершин O нечетной степени в T
G V'.svg Сформируем подграф графа G, используя только вершины графа O
Christofides Matching.svg Построить совершенное паросочетание M минимального веса в этом подграфе
TuM.svg Объедините сопоставление и остовное дерево T M, чтобы сформировать эйлеров мультиграф
Eulertour.svg Рассчитать тур Эйлера
Эйлертур bereinigt.svg Удалите повторяющиеся вершины, дав результат алгоритма

Рекомендации

внешняя ссылка