Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 56: | Строка 56: | ||
Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой функцией w: E | Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой функцией <math>w: E \to \mathbb{Q}_{ \ge 0}</math>, удовлетворяющей неравенству треугольника. | ||
Требуется: найти гамильтонов обход для G, являющийся 3/2”-аппроксимацией. | Требуется: найти гамильтонов обход для G, являющийся 3/2”-аппроксимацией. | ||
1: Вычислить минимальное остовное дерево T графа G. | 1: Вычислить минимальное остовное дерево T графа G. | ||
2: Пусть U | 2: Пусть <math>U \subseteq V \;</math> – множество всех вершин, имеющих нечетную степень в T. Для графа G вычислить совершенное паросочетание с минимальным весом M на U. | ||
3: Вычислить эйлеров обход для T | 3: Вычислить эйлеров обход для <math>T \cup M \;</math> (рассматриваемый как мультиграф). | ||
4: Выполнить сокращение путей этого эйлерова обхода до гамильтонова обхода H. | 4: Выполнить сокращение путей этого эйлерова обхода до гамильтонова обхода H. | ||
Алгоритм 2. Алгоритм Кристофидеса | Алгоритм 2. Алгоритм Кристофидеса | ||
| Строка 69: | Строка 69: | ||
Лемма 3. Пусть U | Лемма 3. Пусть <math>U \subseteq V \;</math>, #U нечетно. Пусть M – совершенное паросочетание с минимальным весом на U. Тогда <math>w(M) \le OPT/2 \;</math>. | ||
Доказательство. Пусть H – оптимальный гамильтонов обход на G. Выполняем сокращение в H, получая обход H0 на G|U следующим образом: H порождает перестановку вершин в U, представляющую собой порядок, в котором они посещаются по ходу H. Соединим вершины U в порядке, заданном перестановкой. Каждому ребру в H0 соответствует путь в H, соединяющий две вершины этого ребра. Согласно неравенству треугольника, w(H0) < w(H). Поскольку #U является четным, H0 представляет собой объединение двух паросочетаний. Вес более легкого из них не превышает w(H0)/2 < OPT/2. □ | Доказательство. Пусть H – оптимальный гамильтонов обход на G. Выполняем сокращение в H, получая обход H0 на G|U следующим образом: H порождает перестановку вершин в U, представляющую собой порядок, в котором они посещаются по ходу H. Соединим вершины U в порядке, заданном перестановкой. Каждому ребру в H0 соответствует путь в H, соединяющий две вершины этого ребра. Согласно неравенству треугольника, w(H0) < w(H). Поскольку #U является четным, H0 представляет собой объединение двух паросочетаний. Вес более легкого из них не превышает w(H0)/2 < OPT/2. □ | ||