|
|
| Строка 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>'' с множеством вершин <m>\{v_1, \ldots, v_n\}</m> и множеством ребер <m>T \cup M</m>;
| + | |
| − | # Найти [[эйлеров цикл|эйлеров обход]] ''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}} | + | |
