Метрическая задача коммивояжера: различия между версиями

Перейти к навигации Перейти к поиску

Метрическая задача коммивояжера (посмотреть исходный код)

Версия от 22:21, 21 августа 2016

52 байта добавлено ,  21 августа 2016
м
→‎Основные результаты
Строка 19: Строка 19:


== Основные результаты ==
== Основные результаты ==
Простой 2-аппроксимацией метрической задачи коммивояжера является алгоритм удвоения дерева. Он использует минимальные остовные деревья для вычисления гамильтоновых путей. Минимальное остовное дерево T графа G = (V, E, w) связный ациклические подграф G, содержащий все вершины E. Вес w(T) такого остовного дерева равен сумме весов его ребер, т.е. w(T) = Pe2T w(e). Остовное дерево является минимальным, если его вес минимален среди всех остовных деревьев G. Можно эффективно вычислить минимальное остовное дерево, например, при помощи алгоритмов Прима или Крускала (см., например, [5]).
Простой 2-аппроксимацией метрической задачи коммивояжера является алгоритм удвоения дерева. Он использует минимальные остовные деревья для вычисления гамильтоновых обходов. Минимальное остовное дерево T графа G = (V, E, w) связный ациклические подграф G, содержащий все вершины E. Вес w(T) такого остовного дерева равен сумме весов его ребер, т.е. w(T) = Pe2T w(e). Остовное дерево является минимальным, если его вес минимален среди всех остовных деревьев G. Можно эффективно вычислить минимальное остовное дерево, например, при помощи алгоритмов Прима или Крускала (см., например, [5]).




Строка 26: Строка 26:
Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и весовая функция w: E ! Q>o, удовлетворяющая неравенству треугольника.
Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и весовая функция w: E ! Q>o, удовлетворяющая неравенству треугольника.


Требуется: найти гамильтонов путь для G, являющийся 2”-аппроксимацией.
Требуется: найти гамильтонов обход для G, являющийся 2”-аппроксимацией.




Строка 33: Строка 33:
2: Продублировать каждое ребро T и получить эйлеров мультиграф T’.
2: Продублировать каждое ребро T и получить эйлеров мультиграф T’.


3: Вычислить эйлеров путь для T (например, при помощи поиска в глубину по T). При посещении вершины эйлерова пути, которая ранее уже была посещена, эта вершина пропускается, и мы переходим к следующей непосещенной вершине эйлерова пути. (Этот процесс называется сокращением пути.) Вернуть полученный гамильтонов путь H.
3: Вычислить эйлеров обход для T (например, при помощи поиска в глубину по T). При посещении вершины эйлерова обхода, которая ранее уже была посещена, эта вершина пропускается, и мы переходим к следующей непосещенной вершине эйлерова обхода. (Этот процесс называется сокращением обхода). Вернуть полученный гамильтонов обход H.


Алгоритм 1. Алгоритм удвоения дерева
Алгоритм 1. Алгоритм удвоения дерева
Строка 40: Строка 40:
Лемма 1. Пусть T – минимальное остовное дерево G = (V, E, w). Тогда w(T) < OPT.
Лемма 1. Пусть T – минимальное остовное дерево G = (V, E, w). Тогда w(T) < OPT.


Доказательство. Если удалить любое ребро гамильтонова пути G, получим остовное дерево G. □
Доказательство. Если удалить любое ребро гамильтонова обхода G, получим остовное дерево G. □




Теорема 2. Алгоритм 1 всегда возвращает гамильтонов путь, вес которого не более чем вдвое превышает вес оптимального пути. Он имеет полиномиальное время выполнения.
Теорема 2. Алгоритм 1 всегда возвращает гамильтонов обход, вес которого не более чем вдвое превышает вес оптимального обхода. Он имеет полиномиальное время выполнения.


Доказательство. Согласно лемме 1, w(T) < OPT. Поскольку мы удваиваем каждое ребро T, вес T’ составляет w(T0) = 2w(T) < 2OPT. В результате сокращения пути на шаге 3 путь в T’ заменяется одним ребром. Согласно неравенству треугольника, сумма весов ребер на таком пути не меньше веса ребра, которым он заменяется. (Для произвольных весовых функций данный алгоритм оказывается недействительным). Следовательно, w(T) < OPT. Это доказывает утверждение по поводу эффективности аппроксимации.
Доказательство. Согласно лемме 1, w(T) < OPT. Поскольку мы удваиваем каждое ребро T, вес T’ составляет w(T0) = 2w(T) < 2OPT. В результате сокращения обхода на шаге 3 путь в T’ заменяется одним ребром. Согласно неравенству треугольника, сумма весов ребер на таком пути не меньше веса ребра, которым он заменяется. (Для произвольных весовых функций данный алгоритм оказывается недействительным). Следовательно, w(T) < OPT. Это доказывает утверждение по поводу эффективности аппроксимации.
Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. □
Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. □


Строка 57: Строка 57:
Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой функцией w: E ! Q>o, удовлетворяющей неравенству треугольника.
Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой функцией w: E ! Q>o, удовлетворяющей неравенству треугольника.


Требуется: найти гамильтонов путь для G, являющийся 3/2”-аппроксимацией.
Требуется: найти гамильтонов обход для G, являющийся 3/2”-аппроксимацией.




Строка 64: Строка 64:
2: Пусть U С V – множество всех вершин, имеющих нечетную степень в T. Для графа G вычислить совершенное паросочетание с минимальным весом M на U.
2: Пусть U С V – множество всех вершин, имеющих нечетную степень в T. Для графа G вычислить совершенное паросочетание с минимальным весом M на U.


3: Вычислить эйлеров путь для T [ M (рассматриваемый как мультиграф).
3: Вычислить эйлеров обход для T [ M (рассматриваемый как мультиграф).


4: Выполнить сокращение путей этого эйлерова пути до гамильтонова пути H.
4: Выполнить сокращение обходов этого эйлерова обхода до гамильтонова обхода H.


Алгоритм 2. Алгоритм Кристофидеса
Алгоритм 2. Алгоритм Кристофидеса
Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/11768

Навигация