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

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

Алгоритм

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

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

Создайте минимальное связующее дерево $T$ of $G$ .
Пусть $O$ — множество вершин нечетной степени в $T$ . По о рукопожатии лемме $O$ имеет четное число вершин.
минимального веса Найдите идеальное паросочетание $M$ в подграфе, индуцированном в $G$ с помощью $O$ .
Объедините ребра $M$ и $T,$ чтобы сформировать связный мультиграф $H$ , в котором каждая вершина имеет четную степень.
Сформируйте эйлерову схему в $H$ .
Превратите схему, найденную на предыдущем шаге, в гамильтонову схему, пропуская повторяющиеся вершины ( сокращение ).

Шаги 5 и 6 не обязательно дают только один результат; по существу, эвристика может дать несколько разных путей.

Вычислительная сложность

В наихудшем случае сложность алгоритма определяется шагом идеального сопоставления, который имеет $O(n^{3})$ сложность. ^[2] Serdyukov's paper claimed $O(n^{3}\log n)$ сложность, ^[4] потому что автору был известен только менее эффективный алгоритм идеального сопоставления. ^[3]

Коэффициент аппроксимации

Стоимость решения, полученного алгоритмом, находится в пределах $3/2$ от оптимального.Чтобы доказать это, пусть $C$ — оптимальный тур коммивояжера. Удаление ребра из $C$ создает остовное дерево, которое должно иметь вес не ниже веса минимального остовного дерева, а это означает, что $w (T) \leq w (C)$ - нижняя граница стоимости оптимального решения.

Алгоритм решает проблему, заключающуюся в том, что $T$ не является обходом, путем идентификации всех вершин нечетной степени в $T$ ; поскольку сумма степеней в любом графе четная (по лемме о рукопожатии ), то таких вершин четное количество. минимального веса $Алгоритм находит идеальное паросочетание M$ среди паросочетаний нечетной степени.

Затем пронумеруйте вершины $O$ в циклическом порядке вокруг $C$ и разделите $C$ на два набора путей: те, в которых первая вершина пути в циклическом порядке имеет нечетное число, и те, в которых первая вершина пути имеет четное число. .Каждый набор путей соответствует идеальному сопоставлению $O$ , которое соответствует двум конечным точкам каждого пути, и вес этого сопоставления не более чем равен весу путей. Фактически каждая конечная точка пути будет соединена с другой конечной точкой, которая также имеет нечетное количество посещений из-за характера тура.

Поскольку эти два набора путей разделяют ребра $C$ , один из двух наборов имеет не более половины веса $C$ который также составляет не более половины веса $C.$ , и благодаря неравенству треугольника его соответствующее паросочетание имеет вес , Совершенное паросочетание минимального веса не может иметь большего веса, поэтому $w (M) \leq 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 \cup 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. ⁻³⁶. Это рандомизированный алгоритм , который следует тем же принципам, что и алгоритм Кристофидеса, но вместо минимального остовного дерева использует случайно выбранное дерево из тщательно выбранного случайного распределения. ^[6]^[7] Доклад был опубликован на STOC'21. ^[8] где он получил награду за лучшую бумагу. ^[9]

В частном случае евклидова пространства для любого c > 0, где d — количество измерений в евклидовом пространстве, существует алгоритм за полиномиальное время, который находит обход длиной не более (1 + 1/ c ), умноженной на оптимален для геометрических экземпляров TSP в

O\left(n(\log n)^{(O(c{\sqrt {d}}))^{d-1}}\right)

время;

это называется схемой аппроксимации полиномиального времени (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.

Внешние ссылки

Определение алгоритма Кристофидеса NIST

[gt-1] Jump up to: ^а ^б ^с Гудрич, Майкл Т .; Тамассиа, Роберто (2015), «18.1.2 Алгоритм аппроксимации Кристофидеса», Разработка и применение алгоритмов , Wiley, стр. 513–514 .

[cri-2] Jump up to: ^а ^б Кристофидес, Никос (1976), Анализ наихудшего случая новой эвристики для задачи коммивояжера (PDF) , Отчет 388, Высшая школа промышленного управления, CMU, заархивировано (PDF) из оригинала 21 июля 2019 г.

[vabe-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

[ser-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]