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

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

Задачей коммивояжера (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”-аппроксимацией.