4551
правка
Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
м
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 22:58, 29 августа 2016
, 29 августа 2016→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
== Основные результаты == | == Основные результаты == | ||
Простой 2-аппроксимацией метрической задачи коммивояжера является ''алгоритм удвоения дерева''. Он использует минимальные остовные деревья для вычисления гамильтоновых обходов. [[Остовное дерево]] T графа G = (V, E, w) представляет собой связный ациклический подграф G, содержащий все вершины V. Вес w(T) такого остовного дерева равен сумме весов его ребер, т.е. <math>w(T) = \sum_{e \in | Простой 2-аппроксимацией метрической задачи коммивояжера является ''алгоритм удвоения дерева''. Он использует минимальные остовные деревья для вычисления гамильтоновых обходов. [[Остовное дерево]] T графа G = (V, E, w) представляет собой связный ациклический подграф G, содержащий все вершины V. Вес w(T) такого остовного дерева равен сумме весов его ребер, т.е. <math>w(T) = \sum_{e \in T} w(e) \;</math>. Остовное дерево является минимальным, если его вес минимален среди всех остовных деревьев G. Можно эффективно вычислить минимальное остовное дерево, например, при помощи алгоритмов Прима или Крускала (см., к примеру, [5]). | ||
Алгоритм удвоения дерева известен с давних времен. Следующая лемма | Алгоритм удвоения дерева известен с давних времен. Следующая лемма необходима для доказательства верхней границы гарантии эффективности алгоритма удвоения дерева. | ||
Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и весовая функция <math>w: E \to \mathbb{Q}_{ \ge 0}</math>, удовлетворяющая неравенству треугольника. | Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и весовая функция <math>w: E \to \mathbb{Q}_{ \ge 0}</math>, удовлетворяющая неравенству треугольника. | ||
Требуется: найти гамильтонов обход для G, являющийся | Требуется: найти гамильтонов обход для G, являющийся 2-аппроксимацией. | ||
1: Вычислить минимальное остовное дерево T графа G. | 1: Вычислить минимальное остовное дерево T графа G. | ||
2: Продублировать каждое ребро T и получить эйлеров мультиграф T’. | 2: Продублировать каждое ребро T и получить эйлеров мультиграф T’. | ||
3: Вычислить эйлеров обход для T (например, при помощи поиска в глубину по T). При посещении вершины эйлерова обхода, которая ранее уже была посещена, | 3: Вычислить эйлеров обход для T' (например, при помощи поиска в глубину по T). При посещении вершины эйлерова обхода, которая ранее уже была посещена, пропускаем эту вершину | ||
и | и переходим к следующей непосещенной вершине эйлерова обхода. (Этот процесс называется ''сокращением обхода''). | ||
Вернуть полученный гамильтонов обход H. | Вернуть полученный гамильтонов обход H. | ||
| Строка 58: | Строка 58: | ||
Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой функцией <math>w: E \to \mathbb{Q}_{ \ge 0}</math>, удовлетворяющей неравенству треугольника. | Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой функцией <math>w: E \to \mathbb{Q}_{ \ge 0}</math>, удовлетворяющей неравенству треугольника. | ||
Требуется: найти гамильтонов обход для G, являющийся 3/ | Требуется: найти гамильтонов обход для G, являющийся 3/2-аппроксимацией. | ||
1: Вычислить минимальное остовное дерево T графа G. | 1: Вычислить минимальное остовное дерево T графа G. | ||