Введение
Приближение для задачи коммивояжера. Алгоритм Кристофидеса или алгоритм Кристофидеса — Сердюкова — это алгоритм для поиска приближенных решений задачи коммивояжера для экземпляров, в которых расстояния образуют метрическое пространство (они симметричны и удовлетворяют неравенству треугольника). Это алгоритм аппроксимации, который гарантирует, что его решения будут отличаться от оптимального решения не более чем в 3/2 раза, и назван в честь Никоса Кристофидеса и Анатолия И. Сердюкова (Анатолий Иванович Сердюков); последний открыл его независимо в 1976 году (однако публикация датирована 1978 годом).
The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality). It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and Anatoliy I. Serdyukov (Анатолий Иванович Сердюков); the latter discovered it independently in 1976 (but the publication is dated 1978).
Алгоритм
Пусть G = (V, w) будет заданием задачи коммивояжера. То есть, G — полный граф на множестве вершин V, а функция w присваивает каждому ребру G неотрицательный вещественный вес. Согласно неравенству треугольника, для любых трех вершин u, v и x должно выполняться условие: w(u, v) + w(v, x) ≥ w(u, x). Тогда алгоритм можно описать псевдокодом следующим образом.
According to the triangle inequality, for every three vertices u, v, and x, it should be the case that w(uv) + w(vx) ≥ w(ux). Then the algorithm can be described in pseudocode as follows.
Пример
При условии: полный граф, веса ребер которого удовлетворяют неравенству треугольника. Вычислить минимальное остовное дерево T. Вычислить множество вершин O с нечетной степенью в T. Построить подграф G, используя только вершины из O. Найти минимальный по весу совершенныйMatching M в этом подграфе. Объединить Matching и остовное дерево 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 содержит пересекающиеся линии, которые, как доказано, не являются самым коротким маршрутом.