Алгоритм Кристофидеса
Алгоритм Кристофидеса или алгоритм Кристофидеса-Сердюкова — это алгоритм поиска приближенных решений задачи коммивояжера в случаях, когда расстояния образуют метрическое пространство (они симметричны и подчиняются неравенству треугольника ). [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]
- Создайте минимальное связующее дерево T of G .
- Пусть O — множество вершин нечетной степени в T . По о согласовании лемме O имеет четное число вершин.
- минимального веса Найдите идеальное паросочетание M в подграфе, индуцированном в G с помощью O .
- Объедините ребра M и T, чтобы сформировать связный мультиграф H , в котором каждая вершина имеет четную степень.
- Сформируйте эйлерову схему в H .
- Превратите схему, найденную на предыдущем шаге, в гамильтонову схему, пропуская повторяющиеся вершины ( сокращение ).
Шаги 5 и 6 не обязательно дают только один результат; по существу, эвристика может дать несколько разных путей.
Вычислительная сложность
[ редактировать ]В наихудшем случае сложность алгоритма определяется шагом идеального сопоставления, который имеет сложность. [2] Газета Сердюкова утверждала сложность, [4] потому что автору был известен только менее эффективный алгоритм идеального сопоставления. [3]
Коэффициент аппроксимации
[ редактировать ]Стоимость решения, полученного алгоритмом, находится в пределах 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 ), умноженной на оптимален для геометрических экземпляров TSP в
- время;
это называется схемой аппроксимации полиномиального времени (PTAS). [10] Санджив Арора и Джозеф С.Б. Митчелл были награждены премией Гёделя в 2010 году за одновременное открытие PTAS для евклидовой TSP.
Ссылки
[ редактировать ]- ^ Jump up to: а б с Гудрич, Майкл Т .; Тамассиа, Роберто (2015), «18.1.2 Алгоритм аппроксимации Кристофидеса», Разработка и применение алгоритмов , Wiley, стр. 513–514 .
- ^ Jump up to: а б Кристофидес, Никос (1976), Анализ наихудшего случая новой эвристики для задачи коммивояжера (PDF) , Отчет 388, Высшая школа промышленного управления, CMU, заархивировано (PDF) из оригинала 21 июля 2019 г.
- ^ Jump up to: а б ван Беверн, Рене; Слугина, Виктория А. (2020), «Историческая справка об алгоритме приближения 3/2 для метрической задачи коммивояжера», Historia Mathematica , 53 : 118–127, arXiv : 2004.02437 , doi : 10.1016/j.hm. 2020.04.003 , S2CID 214803097
- ^ Jump up to: а б Serdyukov, Anatoliy (1978), "О некоторых экстремальных обходах в графах" [On some extremal walks in graphs] (PDF) , Upravlyaemye Sistemy (Управляемые системы) (in Russian), 17 : 76–79
- ^ Блазер, Маркус (2008), «Metric TSP» , в Као, Минг-Янг (редактор), Энциклопедия алгоритмов} , Springer-Verlag, стр. 517–519, ISBN 9780387307701 .
- ^ Карлин, Анна Р .; Кляйн, Натан; Гаран, Шаян Овейс (30 августа 2020 г.). «(Немного) улучшенный алгоритм аппроксимации для метрического TSP». arXiv : 2007.01409 [ cs.DS ].
- ^ Кларрайх, Эрика (8 октября 2020 г.). «Учёные-компьютерщики побили рекорд коммивояжёра» . Журнал Кванта . Проверено 10 октября 2020 г.
- ^ Карлин, Анна Р.; Кляйн, Натан; Гаран, Шаян Овейс (15 июня 2021 г.), «(немного) улучшенный алгоритм аппроксимации для метрического TSP» , Труды 53-го ежегодного симпозиума ACM SIGACT по теории вычислений , Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники, стр. 32–45, arXiv : 2007.01409 , doi : 10.1145/3406325.3451009 , ISBN 978-1-4503-8053-9 , получено 20 апреля 2022 г. ( версия 2023 г. )
- ^ «ACM SIGACT — Премия STOC за лучшую бумагу» . www.sigact.org . Проверено 20 апреля 2022 г.
- ^ Санджив Арора, Схемы полиномиальной аппроксимации для евклидовой TSP и других геометрических задач, Журнал ACM 45 (5) 753–782, 1998.