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

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

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показаны 3 промежуточные версии 2 участников)
Строка 1: Строка 1:
Алгоритм Кристофидеса предназначен для решения [[Задача коммивояжера#метрическая задача коммивояжера|метрической версии задачи о коммивояжере]].
+
#REDIRECT [[discopal:{{PAGENAME}}]]
 
+
Пусть на входе мы имеем ''m x n'' матрицу расстояний ''d<sub>ij</sub>'' для графа ''G''.
+
Тогда алгоритм будет состоять из следующих шагов:
+
# Найти [[минимальное остовное дерево]] ''T'' с матрицей весов ''d<sub>ij</sub>'';
+
# Выделить множество ''N(T)'' всех вершин нечетной степени в ''T'' и найти кратчайшее совершенное паросочетание ''M'' в полном графе ''G'' с множеством вершин ''N(T)'';
+
 
+
# Построить [[эйлеров цикл|эйлеров граф]] ''G<sub>E</sub>'' с множеством вершин <math>\{v_1, \ldots, v_n\}</math> и множеством ребер <math>T \cup M</math>;
+
# Найти [[эйлеров цикл|эйлеров обход]] ''P<sub>E</sub>'' в ''G<sub>E</sub>'';
+
# Построить гамильтонов цикл (соответствующий вложенный тур) ''P<sub>H</sub>'' из ''P<sub>E</sub>'', последовательным вычеркиванием посещенных вершин.
+
 
+
 
+
[[Image:Alg-tsp-christofides.png]]
+
 
+
[[Category:Алгоритмы]]
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:43, 13 июня 2011

  1. REDIRECT discopal:Алгоритм Кристофидеса