Jump to content

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

Алгоритм Кристофидеса или алгоритм Кристофидеса-Сердюкова — это алгоритм поиска приближенных решений задачи коммивояжера в случаях, когда расстояния образуют метрическое пространство (они симметричны и подчиняются неравенству треугольника ). [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 of G .
  2. Пусть O — множество вершин нечетной степени в T . По о согласовании лемме O имеет четное число вершин.
  3. минимального веса Найдите идеальное паросочетание M в подграфе, индуцированном в G с помощью O .
  4. Объедините ребра M и T, чтобы сформировать связный мультиграф H , в котором каждая вершина имеет четную степень.
  5. Сформируйте эйлерову схему в H .
  6. Превратите схему, найденную на предыдущем шаге, в гамильтонову схему, пропуская повторяющиеся вершины ( сокращение ).

Шаги 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.

  1. ^ Jump up to: а б с Гудрич, Майкл Т .; Тамассиа, Роберто (2015), «18.1.2 Алгоритм аппроксимации Кристофидеса», Разработка и применение алгоритмов , Wiley, стр. 513–514 .
  2. ^ Jump up to: а б Кристофидес, Никос (1976), Анализ наихудшего случая новой эвристики для задачи коммивояжера (PDF) , Отчет 388, Высшая школа промышленного управления, CMU, заархивировано (PDF) из оригинала 21 июля 2019 г.
  3. ^ Jump up to: а б ван Беверн, Рене; Слугина, Виктория А. (2020), «Историческая справка об алгоритме приближения 3/2 для метрической задачи коммивояжера», Historia Mathematica , 53 : 118–127, arXiv : 2004.02437 , doi : 10.1016/j.hm. 2020.04.003 , S2CID   214803097
  4. ^ Jump up to: а б Serdyukov, Anatoliy (1978), "О некоторых экстремальных обходах в графах" [On some extremal walks in graphs] (PDF) , Upravlyaemye Sistemy (Управляемые системы) (in Russian), 17 : 76–79
  5. ^ Блазер, Маркус (2008), «Metric TSP» , в Као, Минг-Янг (редактор), Энциклопедия алгоритмов} , Springer-Verlag, стр. 517–519, ISBN  9780387307701 .
  6. ^ Карлин, Анна Р .; Кляйн, Натан; Гаран, Шаян Овейс (30 августа 2020 г.). «(Немного) улучшенный алгоритм аппроксимации для метрического TSP». arXiv : 2007.01409 [ cs.DS ].
  7. ^ Кларрайх, Эрика (8 октября 2020 г.). «Учёные-компьютерщики побили рекорд коммивояжёра» . Журнал Кванта . Проверено 10 октября 2020 г.
  8. ^ Карлин, Анна Р.; Кляйн, Натан; Гаран, Шаян Овейс (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 г. )
  9. ^ «ACM SIGACT — Премия STOC за лучшую бумагу» . www.sigact.org . Проверено 20 апреля 2022 г.
  10. ^ Санджив Арора, Схемы полиномиальной аппроксимации для евклидовой TSP и других геометрических задач, Журнал ACM 45 (5) 753–782, 1998.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: c760e132746ea6b82f61a86ce0889b81__1720455960
URL1:https://arc.ask3.ru/arc/aa/c7/81/c760e132746ea6b82f61a86ce0889b81.html
Заголовок, (Title) документа по адресу, URL1:
Christofides algorithm - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)