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

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

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

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

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

2: Пусть U С V – множество всех вершин, имеющих нечетную степень в T. Для графа G вычислить совершенное паросочетание с минимальным весом M на U.

3: Вычислить эйлеров путь для T [ M (рассматриваемый как мультиграф).

4: Выполнить сокращение путей этого эйлерова пути до гамильтонова пути H.

Алгоритм 2. Алгоритм Кристофидеса