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

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

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

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

1. Создаём минимальное остовное дерево T графа G.
2. Пусть O будет набором вершин с нечётными степенями в T. Согласно лемме о рукопожатиях, O имеет чётное число вершин.
3. Находим совершенное паросочетание M минимального веса в порождённом подграфе, заданным вершинами из O.
4. Комбинируем рёбра M и T с образованием связного мультиграфа H, в котором каждая вершина имеет чётную степень.
5. Образуем эйлеров цикл в H.
6. Преобразуем цикл, найденный на предыдущем шаге, в гамильтонов цикл путём пропуска повторяющихся вершин (сокращение).

Стоимость решения, полученного алгоритмом, лежит в границах 3/2 от оптимального. Для доказательства этого факта предположим, что C является оптимальным обходом задачи коммивояжёра. Удаление ребра из C даёт стягивающее дерево, которое должно иметь вес, не меньший веса минимального стягивающего дерева, откуда следует, что ${\displaystyle w(T)\leqslant w(C)}$. Далее нумеруем вершины O в циклическом порядке по C и делим C на два множества путей — одно имеет нечётные номера первых вершины в циклическом порядке, а второе имеет чётные номера. Каждый набор путей соответствует совершенному паросочетанию множества O, которое сочетает в пару две конечные точки каждого пути, а вес этого сочетания не превосходит веса путей. Поскольку эти два множества путей разбивают рёбра C, одно из этих двух множеств имеет максимум половину веса C, и благодаря неравенству треугольника их соответствующее паросочетание имеет вес, который также не менее половины веса C. Совершенное паросочетание минимального веса не может иметь больший вес, так что ${\displaystyle w(M)\leqslant w(C)/2}$. Сложение весов T и M даёт вес эйлерова цикла, который не превосходит ${\displaystyle 3w(C)/2}$. Благодаря неравенству треугольника сокращение не увеличивает вес, так что вес результата также не превосходит ${\displaystyle 3w(C)/2}$^[1].

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

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

• NIST Christofides Algorithm Definition