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

Материал из CustisWiki

Версия от 19: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


Репликация: База Знаний «Заказных Информ Систем» → «Алгоритм Кристофидеса»

Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».