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

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

Алгоритм

Пусть $G = (V, w)$ будет представителем задачи коммивояжёра. То есть Шаблон:Mvar является полным графом на множестве вершин Шаблон:Mvar, а функция Шаблон:Mvar назначает неотрицательные вещественные веса каждому ребру графа Шаблон:Mvar. Согласно неравенству треугольника для любых трёх вершин Шаблон:Mvar, Шаблон:Mvar и Шаблон:Mvar должно выполняться $w (u v) + w (v x) ⩾ w (u x)$ .

Алгоритм можно описать на псевдокоде следующим образомШаблон:Sfn.

Создаём минимальное остовное дерево Шаблон:Mvar графа Шаблон:Mvar.
Пусть Шаблон:Mvar будет набором вершин с нечётными степенями в Шаблон:Mvar. Согласно лемме о рукопожатиях, Шаблон:Mvar имеет чётное число вершин.
Находим совершенное паросочетание Шаблон:Mvar минимального веса в порождённом подграфе, заданным вершинами из Шаблон:Mvar.
Комбинируем рёбра Шаблон:Mvar и Шаблон:Mvar с образованием связного мультиграфа Шаблон:Mvar, в котором каждая вершина имеет чётную степень.
Образуем эйлеров цикл в Шаблон:Mvar.
Преобразуем цикл, найденный на предыдущем шаге, в гамильтонов цикл путём пропуска повторяющихся вершин (сокращение).

Аппроксимационный коэффициент

Стоимость решения, полученного алгоритмом, лежит в границах 3/2 от оптимального. Для доказательства этого факта предположим, что Шаблон:Mvar является оптимальным обходом задачи коммивояжёра. Удаление ребра из Шаблон:Mvar даёт стягивающее дерево, которое должно иметь вес, не меньший веса минимального стягивающего дерева, откуда следует, что $w (T) ⩽ w (C)$ . Далее нумеруем вершины Шаблон:Mvar в циклическом порядке по Шаблон:Mvar и делим Шаблон:Mvar на два множества путей — одно имеет нечётные номера первых вершины в циклическом порядке, а второе имеет чётные номера. Каждый набор путей соответствует совершенному паросочетанию множества Шаблон:Mvar, которое сочетает в пару две конечные точки каждого пути, а вес этого сочетания не превосходит веса путей. Поскольку эти два множества путей разбивают рёбра Шаблон:Mvar, одно из этих двух множеств имеет максимум половину веса Шаблон:Mvar, и благодаря неравенству треугольника их соответствующее паросочетание имеет вес, который также не менее половины веса Шаблон:Mvar. Совершенное паросочетание минимального веса не может иметь больший вес, так что $w (M) ⩽ w (C) / 2$ . Сложение весов Шаблон:Mvar и Шаблон:Mvar даёт вес эйлерова цикла, который не превосходит $3 w (C) / 2$ . Благодаря неравенству треугольника сокращение не увеличивает вес, так что вес результата также не превосходит $3 w (C) / 2$ Шаблон:Sfn.

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

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

Пример

	Дано: полный граф, веса рёбер которого удовлетворяют неравенству треугольника
	Вычисляем минимальное остовное дерево Шаблон:Mvar
	Вычисляем множество вершин Шаблон:Mvar с нечётной степенью в Шаблон:Mvar
	Образуем подграф графа Шаблон:Mvar, используя лишь вершины множества Шаблон:Mvar
	Строим совершенное паросочетание минимального веса Шаблон:Mvar в этом подграфе
	Объединяем паросочетание и стягивающее дерево Шаблон:Math для образования эйлерова мультиграфа
	Вычисляем эйлеров обход
	Удаляем повторяющиеся вершины и получаем результирующий обход