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

Ссылки сюда (1) →

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

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

1. Найти минимальное остовное дерево T с матрицей весов d_ij;
2. Выделить множество N(T) всех вершин нечетной степени в T и найти кратчайшее совершенное паросочетание M в полном графе G с множеством вершин N(T);

1. Построить эйлеров граф G_E с множеством вершин и множеством ребер ;
2. Найти эйлеров обход P_E в G_E;
3. Построить гамильтонов цикл (соответствующий вложенный тур) P_H из P_E, последовательным вычеркиванием посещенных вершин.

---

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

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