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

Ссылки сюда (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, последовательным вычеркиванием посещенных вершин.

---

Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.