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

Материал из DISCOPAL
Версия от 16:47, 23 октября 2008; WikiSysop (обсуждение) (1 версия)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Пусть на входе мы имеем 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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.