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

Алгоритм Кристофидеса предназначен для решения метрической версии задачи о коммивояжёре.

Пусть на входе мы имеем m x n матрицу расстояний d_ij для графа G. Тогда алгоритм будет состоять из следующих шагов:

1. Найти минимальное остовное дерево T с матрицей весов d_ij;
2. Выделить множество N(T) всех вершин нечетной степени в T и найти кратчайшее совершенное паросочетание M в полном графе G с множеством вершин N(T);

1. Построить эйлеров граф G_E с множеством вершин $\{v_1, \ldots, v_n\}$ и множеством ребер $T \cup M$;
2. Найти эйлеров обход P_E в G_E;
3. Построить гамильтонов цикл (соответствующий вложенный тур) P_H из P_E, последовательным вычеркиванием посещенных вершин.

Файл:Alg-tsp-christofides.png
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.