4551
правка
Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 15:44, 24 августа 2016
, 24 августа 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
1: Вычислить минимальное остовное дерево T графа G. | 1: Вычислить минимальное остовное дерево T графа G. | ||
2: Продублировать каждое ребро T и получить эйлеров мультиграф T’. | 2: Продублировать каждое ребро T и получить эйлеров мультиграф T’. | ||
3: Вычислить эйлеров обход для T (например, при помощи поиска в глубину по T). При посещении вершины эйлерова обхода, которая ранее уже была посещена, эта вершина пропускается, и мы переходим к следующей непосещенной вершине эйлерова обхода. (Этот процесс называется сокращением обхода. | 3: Вычислить эйлеров обход для T (например, при помощи поиска в глубину по T). При посещении вершины эйлерова обхода, которая ранее уже была посещена, эта вершина пропускается, | ||
и мы переходим к следующей непосещенной вершине эйлерова обхода. (Этот процесс называется сокращением обхода). | |||
Вернуть полученный гамильтонов обход H. | |||
Алгоритм 1. Алгоритм удвоения дерева | Алгоритм 1. Алгоритм удвоения дерева | ||
| Строка 46: | Строка 48: | ||
'''Теорема 2. Алгоритм 1 всегда возвращает гамильтонов обход, вес которого не более чем вдвое превышает вес оптимального обхода. Он имеет полиномиальное время выполнения.''' | '''Теорема 2. Алгоритм 1 всегда возвращает гамильтонов обход, вес которого не более чем вдвое превышает вес оптимального обхода. Он имеет полиномиальное время выполнения.''' | ||
Доказательство. Согласно лемме 1, <math>w(T) \le OPT \;</math>. Поскольку мы удваиваем каждое ребро T, вес T’ составляет <math>w(T') = 2w(T) \le 2 OPT \;</math>. В результате сокращения обхода на шаге 3 путь в | Доказательство. Согласно лемме 1, <math>w(T) \le OPT \;</math>. Поскольку мы удваиваем каждое ребро T, вес T’ составляет <math>w(T') = 2w(T) \le 2 OPT \;</math>. В результате сокращения обхода на шаге 3 путь в T' заменяется одним ребром. Согласно неравенству треугольника, сумма весов ребер на таком пути не меньше веса ребра, которым он заменяется. (Для произвольных весовых функций данный алгоритм оказывается недействительным). Следовательно, <math>w(H) \le w(T') \;</math>. Это доказывает утверждение по поводу эффективности аппроксимации. | ||
Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. | Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. | ||
Алгоритм Кристофидеса (алгоритм 2) представляет собой продуманное уточнение алгоритма удвоения дерева. Вначале он вычисляет минимальное остовное дерево. Затем для всех вершин, имеющих нечетную степень в T, он вычисляет совершенное паросочетание с минимальным весом. Паросочетание M для графа G называется паросочетанием на U | Алгоритм Кристофидеса (алгоритм 2) представляет собой продуманное уточнение алгоритма удвоения дерева. Вначале он вычисляет минимальное остовное дерево. Затем для всех вершин, имеющих нечетную степень в T, он вычисляет совершенное паросочетание с минимальным весом. Паросочетание M для графа G называется паросочетанием на <math>U \subseteq V \;</math>, если все ребра M состоят из двух вершин подмножества U. Такое паросочетание называется [[совершенное паросочетание|совершенным]], если каждая вершина из U инцидентна ребру из M. | ||