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

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

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

Спасибо!


c algorithm traveling-salesman minimum-spanning-tree kruskals-algorithm
person Junaid    schedule 02.12.2011    source источник
comment
Действительно ли MST помогает решить TSP?   -  person Daniel Fischer    schedule 02.12.2011
comment
Да, это так. Вы должны использовать другие алгоритмы после нахождения MST в графе.   -  person Junaid    schedule 02.12.2011
comment
Я не совсем понимаю твою проблему, Джунаид. Вы просто хотите знать, как получить решение проблемы TSP с помощью эвристики MST? Поскольку Kruskal уже сортирует ребра, вам просто нужно пройти MST, используя алгоритм DFS. Если вам нужна дополнительная информация, скажите мне.   -  person Fatso    schedule 03.02.2012
comment
Алгоритм DFS прост, потому что ваши ребра уже отсортированы.   -  person Fatso    schedule 03.02.2012

Ответы (1)


arrow_upward
1
arrow_downward

Шаг «сокращения» работает путем вырезания из эйлерова тура всех узлов, которые уже появлялись в туре хотя бы один раз. Например, если у вас был тур

А Б А Д А Е А

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

А Б Г Д А

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

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

person templatetypedef    schedule 24.05.2014