Алгоритм Кристофидеса — различия между версиями

Версия 12:55, 4 августа 2008

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

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

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

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