Персональные инструменты
 

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

Материал из CustisWiki

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

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


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

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