Это снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений.
Алгоритм Кристофидеса предназначен для решения метрической версии задачи о коммивояжере .
Пусть на входе мы имеем m x n матрицу расстояний dij для графа G .
Тогда алгоритм будет состоять из следующих шагов:
Найти минимальное остовное дерево T с матрицей весов dij ;
Выделить множество N(T) всех вершин нечетной степени в T и найти кратчайшее совершенное паросочетание M в полном графе G с множеством вершин N(T) ; Построить эйлеров граф GE с множеством вершин
Найти эйлеров обход PE в GE ;
Построить гамильтонов цикл (соответствующий вложенный тур) PH из PE , последовательным вычеркиванием посещенных вершин.
Репликация: База Знаний «Заказных Информ Систем» → «Алгоритм Кристофидеса »
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion» .
