Русская Википедия:Алгоритм Кристофидеса
Алгоритм Кристофидеса или алгоритм Кристофидеса-Сердюкова — это алгоритм поиска приближённых решений задачи коммивояжёра для случаев, когда расстояния образуют метрическое пространство (симметричны и удовлетворяют неравенству треугольника)Шаблон:Sfn. Алгоритм является аппроксимационным алгоритмом, который гарантирует, что решения находятся в пределах 3/2 от длины оптимального решения. Алгоритм назван именем Никоса Кристофидеса и Анатолия Ивановича Сердюкова, которые независимо друг от друга нашли его в 1976[1][2][3], и он обладает лучшим аппроксимационным коэффициентом, который был доказан для задачи коммивояжёра на метрических пространствах общего вида, хотя известны лучшие приближения для некоторых специальных случаев.
Алгоритм
Пусть <math>G = (V,w)</math> будет представителем задачи коммивояжёра. То есть Шаблон:Mvar является полным графом на множестве вершин Шаблон:Mvar, а функция Шаблон:Mvar назначает неотрицательные вещественные веса каждому ребру графа Шаблон:Mvar. Согласно неравенству треугольника для любых трёх вершин Шаблон:Mvar, Шаблон:Mvar и Шаблон:Mvar должно выполняться <math>w(uv) + w(vx) \geqslant w(ux)</math>.
Алгоритм можно описать на псевдокоде следующим образомШаблон:Sfn.
- Создаём минимальное остовное дерево Шаблон:Mvar графа Шаблон:Mvar.
- Пусть Шаблон:Mvar будет набором вершин с нечётными степенями в Шаблон:Mvar. Согласно лемме о рукопожатиях, Шаблон:Mvar имеет чётное число вершин.
- Находим совершенное паросочетание Шаблон:Mvar минимального веса в порождённом подграфе, заданным вершинами из Шаблон:Mvar.
- Комбинируем рёбра Шаблон:Mvar и Шаблон:Mvar с образованием связного мультиграфа Шаблон:Mvar, в котором каждая вершина имеет чётную степень.
- Образуем эйлеров цикл в Шаблон:Mvar.
- Преобразуем цикл, найденный на предыдущем шаге, в гамильтонов цикл путём пропуска повторяющихся вершин (сокращение).
Аппроксимационный коэффициент
Стоимость решения, полученного алгоритмом, лежит в границах 3/2 от оптимального. Для доказательства этого факта предположим, что Шаблон:Mvar является оптимальным обходом задачи коммивояжёра. Удаление ребра из Шаблон:Mvar даёт стягивающее дерево, которое должно иметь вес, не меньший веса минимального стягивающего дерева, откуда следует, что <math>w(T) \leqslant w(C)</math>. Далее нумеруем вершины Шаблон:Mvar в циклическом порядке по Шаблон:Mvar и делим Шаблон:Mvar на два множества путей — одно имеет нечётные номера первых вершины в циклическом порядке, а второе имеет чётные номера. Каждый набор путей соответствует совершенному паросочетанию множества Шаблон:Mvar, которое сочетает в пару две конечные точки каждого пути, а вес этого сочетания не превосходит веса путей. Поскольку эти два множества путей разбивают рёбра Шаблон:Mvar, одно из этих двух множеств имеет максимум половину веса Шаблон:Mvar, и благодаря неравенству треугольника их соответствующее паросочетание имеет вес, который также не менее половины веса Шаблон:Mvar. Совершенное паросочетание минимального веса не может иметь больший вес, так что <math>w(M) \leqslant w(C)/2</math>. Сложение весов Шаблон:Mvar и Шаблон:Mvar даёт вес эйлерова цикла, который не превосходит <math>3w(C)/2</math>. Благодаря неравенству треугольника сокращение не увеличивает вес, так что вес результата также не превосходит <math>3w(C)/2</math>Шаблон:Sfn.
Нижние границы
Существуют экземпляры задачи коммивояжёра, на которых алгоритм Кристофидеса находит решение, которое произвольно близко 3/2. Один из таких классов задач сформирован путём из Шаблон:Mvar вершин с весами рёбер Шаблон:Math вместе с набором рёбер, соединяющих вершины, отстоящие вдоль пути на два шага, с весами <math>1 + \epsilon</math>, где <math>\epsilon</math> выбирается близким к нулю, но положительным. Все оставшиеся рёбра полного графа имеют расстояния, равные кратчайшим путям в этом подграфе. Тогда минимальное стягивающее дерево будет задано путём длины <math>n - 1</math> и только две нечётные вершины будут конечными точками пути и его совершенное паросочетание состоит из одного ребра с весом примерно Шаблон:Math. Объединение дерева и паросочетания является циклом без сокращений вершин и весом примерно <math>3n/2</math>. Однако оптимальное решение использует рёбра весом <math>1 + \epsilon</math> вместе с двумя рёбрами веса Шаблон:Math, инцидентных концам пути, и его полный вес равен <math>(1 + \epsilon)(n - 2) + 2</math>, что близко к Шаблон:Mvar для малых значений <math>\epsilon</math>. Отсюда мы получаем аппроксимационный коэффициент 3/2Шаблон:Sfn.
Пример
| Файл:Metrischer Graph mit 5 Knoten.svg | Дано: полный граф, веса рёбер которого удовлетворяют неравенству треугольника |
| Файл:Christofides MST.svg | Вычисляем минимальное остовное дерево Шаблон:Mvar |
| Файл:V'.svg | Вычисляем множество вершин Шаблон:Mvar с нечётной степенью в Шаблон:Mvar |
| Файл:G V'.svg | Образуем подграф графа Шаблон:Mvar, используя лишь вершины множества Шаблон:Mvar |
| Файл:Christofides Matching.svg | Строим совершенное паросочетание минимального веса Шаблон:Mvar в этом подграфе |
| Файл:TuM.svg | Объединяем паросочетание и стягивающее дерево Шаблон:Math для образования эйлерова мультиграфа |
| Файл:Eulertour.svg | Вычисляем эйлеров обход |
| Файл:Eulertour bereinigt.svg | Удаляем повторяющиеся вершины и получаем результирующий обход |
Примечания
Литература
Ссылки
