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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

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

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

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