Задача коммивояжера с неравенством треугольника.

Напомним, что задача состоит в том, чтобы в полном неориентированном графе G = (V, E), для каждого ребра которого известна его стоимость, найти гамильтонов цикл минимальной стоимости. Стоимость любого множества ребер A Í E есть сумма стоимостей его ребер

c(A) = å c (u, v)

(u, v) ÎA

На практике функция стоимости ребер обычно удовлетворяет неравенству треугольника: с (u, v) £ c (u, w) + c (w, v), для любых трех вершие u, v, w Î V. Даже в предположении неравенства треугольника задача коммивояжера остается NP-полной. Тем самым нет шансов найти полиномиальный алгоритм, дающий оптимальное решение, и есть смысл искать приближенные алгоритмы. Известен полиномиальный алгоритм, решающий задачу с ошибкой не более чем в 2 раза.

Приближенный алгоритм TSP. Воспользуемся алгоритмом Прима (Prim)[] отыскания минимального покрывающего дерева, а затем переделаем это дерево в цикл.

TSP (G, e)

1. возьмем за корень дерева произвольную вершину a Î V

2. построим минимальное полкрывающее дерево T для графа G

с помощью алгоритма Prim (G, c, a)

3. returnцикл обхода вдоль ребер дерева T с выброшенными

повторениями

Рис.37.2.

На рис. 37.2 показана работа алгоритма. Для данной системы точек на плоскости (a) строится минимальное остовное дерево T; a – корень (б). Путь, обходящий все вершины дерева (в), не является циклом. Удаляя повторения, получим гамильтонов цикл (г), который примерно на 23% длиннее оптимального цикла (д). Время работы алгоритма TSP равно O(E)=O(V²), поскольку алгоритм применялся к полному графу. Приверим, что найденный цикл не более чем вдвое длиннее оптимального.

Теорема.Алгоритм TSP решает задачу коммивояжера с ошибкой не более чем в 2 раза, если выполнено неравенство треугольника.

Доказательство. Пусть H* - гамильтонов цикл наимньшей стоимости. Покажем, что с (H) £ 2c (H*) для цикла H, найденного с помощью алгоритма TSP. Удаляя любое ребро из цикла H*, мы получим покрывающее дерево. Его стоимость не превосходит c (H*), тем более это верно для оптимального покрывающего дерева T: c (T) £ c(H*).

Совершим полный обход W оптимального дерева T, при этом каждое ребро проходится дважды, поэтому c (W) = 2c (T). Так что c (W) £ 2c (H*).

Осталось заметить, что при удалении повторно проходимых вершин стоимость может только уменьшиться. Таким образом, с (H) £ c (W).