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

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

До 2020 года это было лучшее коэффициент аппроксимации это было доказано для задачи коммивояжера на общих метрических пространствах (хотя для некоторых частных случаев известны более точные приближения). В июле 2020 года Карлин, Кляйн и Гаран выпустили препринт с новым алгоритмом, который, как они объявили, имеет коэффициент аппроксимации 1,5-10.−36.[5][6]

Алгоритм

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

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

  1. Создать минимальное остовное дерево Т из грамм.
  2. Позволять О - множество вершин с нечетными степень в Т. Посредством лемма о рукопожатии, О имеет четное количество вершин.
  3. Найдите минимальный вес идеальное соответствие M в индуцированный подграф заданные вершинами из О.
  4. Совместите края M и Т сформировать связанный мультиграф ЧАС в котором каждая вершина имеет четную степень.
  5. Для мужчин Контур Эйлера в ЧАС.
  6. Превратите схему, найденную в предыдущем шаге, в Гамильтонова схема пропуская повторяющиеся вершины (сокращение).

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

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

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

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

Пример

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

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

  1. ^ а б c Гудрич, Майкл Т.; Тамассия, Роберто (2015), «18.1.2 Алгоритм аппроксимации Христофидеса», Разработка алгоритмов и приложения, Wiley, стр. 513–514..
  2. ^ Христофидес, Христофидес (1976), Анализ наихудшего случая новой эвристики для задачи коммивояжера (PDF), Отчет 388, Высшая школа промышленного администрирования, CMU
  3. ^ ван Беверн, Рене; Слугина, Виктория А. (2020), «Историческая справка об алгоритме приближения 3/2 для метрической задачи коммивояжера», Historia Mathematica, arXiv:2004.02437, Дои:10.1016 / j.hm.2020.04.003, S2CID  214803097
  4. ^ Сердюков, Анатолий Иванович (1978), "О некоторых экстремальных обходах в графах" [О некоторых экстремальных прогулках в графах] (PDF), Управляемые системы (на русском), 17: 76–79
  5. ^ Карлин, Анна Р .; Кляйн, Натан; Гаран, Шаян Овейс (30.08.2020). «(Немного) улучшенный алгоритм аппроксимации для метрической TSP». arXiv:2007.01409 [cs.DS ].
  6. ^ Кларрайх, Эрика. "Компьютерные ученые побили рекорд коммивояжера". Журнал Quanta. Получено 2020-10-10.
  7. ^ Блейзер, Маркус (2008), «Метрическая ТСП», в Као, Мин-Ян (ред.), Энциклопедия алгоритмов}, Springer-Verlag, стр. 517–519, ISBN  9780387307701.

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