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

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

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

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

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

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

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

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