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

Материал из DISCOPAL
Перейти к: навигация, поиск
м (1 версия)
 
(нет различий)

Текущая версия на 16:47, 23 октября 2008

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

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

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


Файл:Alg-tsp-christofides.png