Метрическая задача коммивояжера

Постановка задачи

Задачей коммивояжера (Traveling Salesman Problem, TSP) является следующая задача оптимизации:

Дано: полный неориентированный граф без циклов G = (V, E) и весовая функция w: E ! Q >o, присваивающая каждому ребру неотрицательный вес.

Допустимые решения: все гамильтоновы обходы, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2.

Целевая функция: весовая функция w(H) = Pe2H w(e) обхода. Цель: минимизация значения весовой функции.

Задача коммивояжера представляет собой NP-полную задачу. Это означает, что для ее решения не существует алгоритма с полиномиальным временем выполнения, если только не окажется верным P = NP. Одним из способов разрешения этой проблемы являются алгоритмы аппроксимации. Алгоритм аппроксимации задачи TSP с полиномиальным временем выполнения называется алгоритмом a-аппроксимации, если обход H, полученный с его помощью, удовлетворяет неравенству w(H) < a ■ OPT(G). Здесь OPT(G) – вес обхода с минимальным весом для графа G. Если граф G понятен из контекста, можно записывать его просто в виде «OPT». Алгоритм a-аппроксимации всегда дает в итоге допустимое решение, целевое значение которого не более чем в a раз отличается от оптимального значения. a также называется коэффициентом аппроксимации или гирантией эффективности. a не обязательно должно быть константой; оно может быть функцией, зависящей от размера входного экземпляра или количества вершин n.

Если существует алгоритм с полиномиальным временем выполнения для решения задачи TSP, коэффициент аппроксимации которого зависит от n, то P = NP. Таким образом, следует рассматривать ограниченные экземпляры. Наиболее естественным ограничением является неравенство треугольника, которое выглядит следующим образом: w(u, v) < w(u, x) + w(x, v) для всех u, v, x 2 V.

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

Основные результаты

Простой 2-аппроксимацией метрической задачи коммивояжера является алгоритм удвоения дерева. Он использует минимальные остовные деревья для вычисления гамильтоновых обходов. Минимальное остовное дерево T графа G = (V, E, w) связный ациклические подграф G, содержащий все вершины E. Вес w(T) такого остовного дерева равен сумме весов его ребер, т.е. w(T) = Pe2T w(e). Остовное дерево является минимальным, если его вес минимален среди всех остовных деревьев G. Можно эффективно вычислить минимальное остовное дерево, например, при помощи алгоритмов Прима или Крускала (см., например, [5]).

Алгоритм удвоения дерева известен с давних времен. Следующая лемма доказывает верхнюю границу гарантии эффективности алгоритма удвоения дерева.

Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и весовая функция w: E ! Q>o, удовлетворяющая неравенству треугольника.

Требуется: найти гамильтонов обход для G, являющийся 2”-аппроксимацией.

1: Вычислить минимальное остовное дерево T графа G.

2: Продублировать каждое ребро T и получить эйлеров мультиграф T’.

3: Вычислить эйлеров обход для T (например, при помощи поиска в глубину по T). При посещении вершины эйлерова обхода, которая ранее уже была посещена, эта вершина пропускается, и мы переходим к следующей непосещенной вершине эйлерова обхода. (Этот процесс называется сокращением обхода). Вернуть полученный гамильтонов обход H.

Алгоритм 1. Алгоритм удвоения дерева

Лемма 1. Пусть T – минимальное остовное дерево G = (V, E, w). Тогда w(T) < OPT.

Доказательство. Если удалить любое ребро гамильтонова обхода G, получим остовное дерево G. □

Теорема 2. Алгоритм 1 всегда возвращает гамильтонов обход, вес которого не более чем вдвое превышает вес оптимального обхода. Он имеет полиномиальное время выполнения.

Доказательство. Согласно лемме 1, w(T) < OPT. Поскольку мы удваиваем каждое ребро T, вес T’ составляет w(T0) = 2w(T) < 2OPT. В результате сокращения обхода на шаге 3 путь в T’ заменяется одним ребром. Согласно неравенству треугольника, сумма весов ребер на таком пути не меньше веса ребра, которым он заменяется. (Для произвольных весовых функций данный алгоритм оказывается недействительным). Следовательно, w(T) < OPT. Это доказывает утверждение по поводу эффективности аппроксимации. Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. □

Алгоритм Кристофидеса (алгоритм 2) представляет собой продуманное уточнение алгоритма удвоения дерева. Вначале он вычисляет минимальное остовное дерево. Затем для всех вершин, имеющих нечетную степень в T, он вычисляет совершенное паросочетание с минимальным весом. Паросочетание M для графа G называется паросочетанием на U С V, если все ребра M состоят из двух вершин подмножества U. Такое паросочетание называется совершенным, если каждая вершина из U инцидентна ребру из M.

Лемма 3. Пусть U С V;#U нечетно. Пусть M –совершенное паросочетание с минимальным весом на U. Тогда w(M) < OPT/2.

Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой функцией w: E ! Q>o, удовлетворяющей неравенству треугольника.

Требуется: найти гамильтонов обход для G, являющийся 3/2”-аппроксимацией.

1: Вычислить минимальное остовное дерево T графа G.

2: Пусть U С V – множество всех вершин, имеющих нечетную степень в T. Для графа G вычислить совершенное паросочетание с минимальным весом M на U.

3: Вычислить эйлеров обход для T [ M (рассматриваемый как мультиграф).

4: Выполнить сокращение обходов этого эйлерова обхода до гамильтонова обхода H.

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

Доказательство. Пусть H – оптимальный гамильтонов обход на G. Выполняем сокращение в H, получая обход H0 на G|U следующим образом: H порождает перестановку вершин в U, представляющую собой порядок, в котором они посещаются по ходу H. Соединим вершины U в порядке, заданном перестановкой. Каждому ребру в H0 соответствует путь в H, соединяющий две вершины этого ребра. Согласно неравенству треугольника, w(H0) < w(H). Поскольку #U является четным, H0 представляет собой объединение двух паросочетаний. Вес более легкого из них не превышает w(H0)/2 < OPT/2. □

Можно вычислить совершенное паросочетание с минимальным весом за время O(n3); см., например, [5].

Теорема 4. Алгоритм 2 представляет собой алгоритм 3/2-аппроксимации с полиномиальным временем выполнения.

Доказательство. Вначале отметим, что количество вершин с нечетной степенью в остовном дереве является четным, поскольку сумма степеней всех вершин равна 2(n — 1), а это четное число. Таким образом, совершенное паросочетание на U существует. Вес эйлерова обхода, очевидно, составляет w(T) + w(M). Согласно лемме 1, w(T) < OPT. Согласно лемме 3, w(M) < OPT/2. Вес w(H) вычисленного обхода H не превышает веса эйлерова обхода согласно неравенству треугольника, т.е. w(H) < |OPT. Таким образом, полученный алгоритм представляет собой алгоритм 3/2-аппроксимации, время выполнения которого составляет O(n3). □