4551
правка
Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 12:42, 21 августа 2016
, 21 августа 2016→Основные результаты
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
Требуется: найти гамильтонов путь для G, являющийся 2”-аппроксимацией. | Требуется: найти гамильтонов путь для G, являющийся 2”-аппроксимацией. | ||
1: Вычислить минимальное остовное дерево T графа G. | |||
2: Продублировать каждое ребро T и получить эйлеров мультиграф T’. | |||
3: Вычислить эйлеров путь для T (например, при помощи поиска в глубину по T). При посещении вершины эйлерова пути, которая ранее уже была посещена, эта вершина пропускается, и мы переходим к следующей непосещенной вершине эйлерова пути. (Этот процесс называется сокращением пути.) Вернуть полученный гамильтонов путь H. | |||
Алгоритм 1. Алгоритм удвоения дерева | |||
Лемма 1. Пусть T – минимальное остовное дерево G = (V, E, w). Тогда w(T) < OPT. | |||
Доказательство. Если удалить любое ребро гамильтонова пути G, получим остовное дерево G. □ | |||
Теорема 2. Алгоритм 1 всегда возвращает гамильтонов путь, вес которого не более чем вдвое превышает вес оптимального пути. Он имеет полиномиальное время выполнения. | |||
Доказательство. Согласно лемме 1, w(T) < OPT. Поскольку мы удваиваем каждое ребро T, вес T’ составляет w(T0) = 2w(T) < 2OPT. В результате сокращения пути на шаге 3 путь в T’ заменяется одним ребром. Согласно неравенству треугольника, сумма весов ребер на таком пути не меньше веса ребра, которым он заменяется. (Для произвольных весовых функций данный алгоритм оказывается недействительным). Следовательно, w(T) < OPT. Это доказывает утверждение по поводу эффективности аппроксимации. | |||
Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. □ | |||
Алгоритм Кристофидеса (алгоритм 2) представляет собой продуманное уточнение алгоритма удвоения дерева. Вначале он вычисляет минимальное остовное дерево. Затем для всех вершин, имеющих нечетную степень в T, он вычисляет совершенное паросочетание с минимальным весом. Паросочетание M для графа G называется паросочетанием на U С V, если все ребра M состоят из двух вершин подмножества U. Такое паросочетание называется совершенным, если каждая вершина из U инцидентна ребру из M. | |||
Лемма 3. Пусть U С V;#U нечетно. Пусть M –совершенное паросочетание с минимальным весом на U. Тогда w(M) < OPT/2. | |||
Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой функцией w: E ! Q>o, удовлетворяющей неравенству треугольника. | |||
Требуется: найти гамильтонов путь для G, являющийся 3/2”-аппроксимацией. | |||
1: Вычислить минимальное остовное дерево T графа G. | |||
2: Пусть U С V – множество всех вершин, имеющих нечетную степень в T. Для графа G вычислить совершенное паросочетание с минимальным весом M на U. | |||
3: Вычислить эйлеров путь для T [ M (рассматриваемый как мультиграф). | |||
4: Выполнить сокращение путей этого эйлерова пути до гамильтонова пути H. | |||
Алгоритм 2. Алгоритм Кристофидеса | |||