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

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

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

Дано: полный неориентированный граф без циклов G = (V, E) и весовая функция [math]\displaystyle{ w: E \to \mathbb{Q}_{ \ge 0} }[/math], присваивающая каждому ребру неотрицательный вес.

Допустимые решения: все гамильтоновы обходы, т.е. подграфы 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.

Дано: полный неориентированный граф без циклов 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. Алгоритм Кристофидеса

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

Применение

Экспериментальный анализ показывает, что алгоритм Кристофидеса сам отклоняется от оптимального обхода на величину от 10 до 15% [ ]. Однако он может служить хорошей отправной точкой для других эвристик обхода – таких как эвристика Лина-Кернигана.

Рисунок 1. Пример для алгоритма Кристофидеса. В графе 2n + 1 вершин. Сплошные ребра имеют вес 1, пунктирные – вес 1 + e.

Открытые вопросы

Анализ алгоритма 2 несложен. Примером может служить метрическое пополнение графа, изображенного на рис. 1. Его единственное минимальное остовное дерево состоит из всех склошных ребер. Оно содержит только две вершины с нечетными степенями. Ребро между этими двумя вершинами имеет вес (1 + е)(и + 1). Сокращений не требуется; вес обхода, вычисленного алгоритмом, равен £rf n. Оптимальный обход состоит из всех пунктирных ребер, а также самого левого и самого правого сплошных ребер. Вес этого обхода составляет (2n - 1)(1 + e) + 2 & 2n.

Вопрос о существовании алгоритма аппроксимации с лучшей гарантией эффективности является главным нерешенным вопросом а теории алгоритмов аппроксимации.

Хельд и Карп [ ] разработали алгоритм на основе линейного программирования, вычисляющий нижнюю границу веса оптимального обхода для задачи коммивояжера. Была предложена гипотеза, что вес оптимального обхода для задачи коммивояжера не более чем в 4/3 раза превышает его нижнюю границу; однако эта гипотеза уже более 30 лет остается недоказанной. Алгоритмическое доказательство гипотезы позволило бы получить алгоритм 4/3-аппроксимации для метрической задачи коммивояжера.

Экспериментальные результаты

В работе [3] было отмечено отклонение в 10-15% от оптимального (говоря точнее – от границы Хельда-Карпа) на различных экземплярах задачи.

Наборы данных

На странице 8-го тура задач по реализации DIMACS по адресу www.research.att.com/~dsj/chtsp/ можно найти множество экземпляров.

См. также

• Минимальные остовные деревья

Литература

Кристофидес не публиковал самостоятельно свой алгоритм. Он обычно цитируется как один из двух технических отчетов Университета Карнеги-Меллона – TR 388 Института индустриальных исследований (теперь он называется Школой бизнеса Теппера) и CS-93-13. Ни один из них в настоящее время не доступен в Университете Карнеги-Меллона [из личной переписки с Фрэнком Бальбахом Balbach, 2006 г.]. В материалах конференции были приведены тезисы объемом в 1 страницу. Однако алгоритм быстро проложил себе дорогу в учебники по теории алгоритмов; см., например, [7].

1. Christofides, N.: Worst case analysis of a new heuristic for the traveling salesman problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, (1976). Also: Carnegie-Mellon University Technical Report CS-93-13, 1976. Abstract in Traub, J.F. (ed.) Symposium on new directions and recent results in algorithms and complexity, pp. 441. Academic Press, New York (1976)

2. Held, M., Karp, R.M.: The traveling salesman problem and minimum spanning trees. Oper. Res. 18,1138-1162 (1970)

3. Johnson, D.S., McGeoch, L.A.: Experimental analysis of heuristics for the STSP. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and its Variations. Kluwer, Dordrecht (2002)

4. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.): The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)

5. Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs (1982)

6. Sahni, S., Gonzalez, T.: P-complete approximation problems. J.ACM 23, 555-565 (1976)

7. Vazirani,V.V.: Approximation Algorithms. Springer, Berlin (2001)

8. Traveling Salesman Problem. www.tsp.gatech.edu (2006). Accessed 28 Mar 2008