4551
правка
Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 00:21, 21 августа 2016
, 21 августа 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 17: | Строка 17: | ||
Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют алгоритмы аппроксимации с константным коэффициентом. Отметим, что для решения метрической задачи коммивояжера достаточно найти путь, который посещает любую вершину не менее одного раза. При наличии такого пути мы сможем найти гамильтонов путь с меньшим или равным весом за счет отбрасывания любой вершины, которую мы уже посещали. Согласно неравенству треугольника, вес нового пути не может возрастать. | Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют алгоритмы аппроксимации с константным коэффициентом. Отметим, что для решения метрической задачи коммивояжера достаточно найти путь, который посещает любую вершину не менее одного раза. При наличии такого пути мы сможем найти гамильтонов путь с меньшим или равным весом за счет отбрасывания любой вершины, которую мы уже посещали. Согласно неравенству треугольника, вес нового пути не может возрастать. | ||
== Основные результаты == | |||
Простой 2-аппроксимацией метрической задачи коммивояжера является алгоритм удвоения дерева. Он использует минимальные остовные деревья для вычисления гамильтоновых путей. Минимальное остовное дерево T графа G = (V, E, w) связный ациклические подграф G, содержащий все вершины E. Вес w(T) такого остовного дерева равен сумме весов его ребер, т.е. w(T) = Pe2T w(e). Остовное дерево является минимальным, если его вес минимален среди всех остовных деревьев G. Можно эффективно вычислить минимальное остовное дерево, например, при помощи алгоритмов Прима или Крускала (см., например, [5]). | |||
Алгоритм удвоения дерева известен с давних времен. Следующая лемма доказывает верхнюю границу гарантии эффективности алгоритма удвоения дерева. | |||
Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и весовая функция w: E ! Q>o, удовлетворяющая неравенству треугольника. | |||
Требуется: найти гамильтонов путь для G, являющийся 2”-аппроксимацией. | |||