Как реализовать шаг ярлыка в алгоритме Christofides?

Question

Я реализую алгоритм Christofides для получения 3/2-приближения к TSP в графах, которые подчиняются неравенству треугольника. У меня уже есть код для вычисления минимального остовного дерева с использованием алгоритма Крускала и матрицы смежности.

Теперь я хочу реализовать Christofides, удвоив ребра и найдя тур Эйлера, а затем сократив дубликаты узлов. Как мне выполнить этот шаг? Я хотел бы алгоритм и (необязательно) код C.

Спасибо!

Answer 1

Этап «ярлык» работает, вырезая из тура Эйлера все узлы, которые уже были хотя бы раз в туре. Например, если у вас был тур

A & rarr; B & rarr; A & rarr; D & rarr; A & rarr; E & rarr; A

Вы бы закончили цикл

A & rarr; B & rarr; D & rarr; E & rarr; A

Один из способов сделать это заключается в следующем. Поддерживайте набор всех узлов, которые вы посетили до сих пор в туре. Во время прогулки по маршруту, если вы встретите не посещенный узел, добавьте его в свой цикл и добавьте его в набор. Если вы встретили посещенный узел, пропустите его. В самом конце добавьте ребро из последнего найденного узла обратно в начальный узел.

Надеюсь, это поможет!