4551
правка
Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 22:24, 21 августа 2016
, 21 августа 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 69: | Строка 69: | ||
Алгоритм 2. Алгоритм Кристофидеса | Алгоритм 2. Алгоритм Кристофидеса | ||
Доказательство. Пусть H – оптимальный гамильтонов обход на G. Выполняем сокращение в H, получая обход H0 на G|U следующим образом: H порождает перестановку вершин в U, представляющую собой порядок, в котором они посещаются по ходу H. Соединим вершины U в порядке, заданном перестановкой. Каждому ребру в H0 соответствует путь в H, соединяющий две вершины этого ребра. Согласно неравенству треугольника, w(H0) < w(H). Поскольку #U является четным, H0 представляет собой объединение двух паросочетаний. Вес более легкого из них не превышает w(H0)/2 < OPT/2. □ | |||
Можно вычислить совершенное паросочетание с минимальным весом за время O(n3); см., например, [5]. | |||
Теорема 4. Алгоритм 2 представляет собой алгоритм 3/2-аппроксимации с полиномиальным временем выполнения. | |||
Доказательство. Вначале отметим, что количество вершин с нечетной степенью в остовном дереве является четным, поскольку сумма степеней всех вершин равна 2(n — 1), а это четное число. Таким образом, совершенное паросочетание на U существует. Вес эйлерова обхода, очевидно, составляет w(T) + w(M). Согласно лемме 1, w(T) < OPT. Согласно лемме 3, w(M) < OPT/2. Вес w(H) вычисленного обхода H не превышает веса эйлерова обхода согласно неравенству треугольника, т.е. w(H) < |OPT. Таким образом, полученный алгоритм представляет собой алгоритм 3/2-аппроксимации, время выполнения которого составляет O(n3). □ | |||