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

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

Алгоритм

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

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

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

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

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

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

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

Пример

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

Ссылки

• NIST Christofides Algorithm Definition