Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Алгоритм [ править ]

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

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

  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 . [1]

Нижние границы [ править ]

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

Пример [ править ]

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Удалите повторяющиеся вершины, дав результат алгоритма

Ссылки [ править ]

  1. ^ a b c Гудрич, Майкл Т .; Тамассия, Роберто (2015), «18.1.2 Алгоритм приближения Кристофидеса», Разработка алгоритмов и приложения , Wiley, стр. 513–514.
  2. ^ Кристофидес, Никос (1976), Анализ наихудшего случая новой эвристики для задачи коммивояжера (PDF) , Отчет 388, Высшая школа промышленного администрирования, CMU
  3. ^ ван Беверн, Рене; Слугина, Виктория А. (2020), «Историческая заметка об алгоритме приближения 3/2 для метрической задачи коммивояжера», Historia Mathematica , arXiv : 2004.02437 , doi : 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 . Проверено 10 октября 2020 .
  7. ^ Blaser, Маркус (2008), "Метрика TSP" , в Као, Мин-Ян (ред.), Энциклопедия алгоритмов} , Springer-Verlag, стр. 517-519, ISBN 9780387307701.

Внешние ссылки [ править ]

  • Определение алгоритма NIST Christofides