Приближенные алгоритмы решения сложных задач

Это вводная статья в приближенные алгоритмы. В ней мы рассмотрим лишь самые простые и известные алгоритмы для приближенного решения NP-трудных задач.

На данный момент не известно полиномиальных алгоритмов для точного решения NP-трудных задач. Более того, специалисты по теории сложности склоняются к варианту, что таких алгоритмов не существует. Однако, NP-трудные задачи часто встречаются в жизни. Одним из подходов борьбы с NP-трудными задачами на практике является разработка приближенных алгоритмов.

Рассмотрим следующие задачи.

1) Задача о вершинном покрытии (Vertex Cover).
Задача заключается в том, чтобы выбрать в неориентированном графе G=(V, E) минимальное (по количеству вершин) множество вершин S так, чтобы оно покрывало все рёбра графа. То есть так, чтобы у каждого из рёбер графа хотя бы один из концов принадлежал S.

Построим простой алгоритм решения этой задачи, ошибающийся не более чем в два раза. Это означает, что если есть оптимальное решение — множество вершин T, то |S| <= 2|T|. Алгоритм: Выбираем случайное ребро графа e=(u, v). Добавляем в решение S обе вершины u и v. Удаляем из множества рёбер все рёбра, инцидентные вершинам u или v. Повторяем этот шаг пока рёбра не закончатся. Очевидно, что построенное множество покрывает все рёбра графа. Докажем, что наш алгоритм ошибается не более, чем в 2 раза. Все рассматриваемые алгоритмом рёбра e не имеют общих вершин. Следовательно, из каждого из этих рёбер в оптимальное решение T должна входить хотя бы одна вершина. Это значит, что 2|T|>=|S|. Интересно, что не известно полиномиальных приближенных алгоритмов для Vertex Cover значительно улучшающих ошибку. То есть, не известно полиномиального алгоритма, который ошибается не более, чем в 1.999 раза. Таким образом, мы получили простой алгоритм с небольшой ошибкой.
2) Задача о коммивояжёре (Travelling salesman problem).
Вероятно, самая знаменитая NP-трудная задача. Задача заключается в том, чтобы пройти все вершины неориентированного графа ровно по одному разу и вернуться в исходную вершину. Кроме того, для каждого ребра указан его вес. И нам необходимо найти такой обход графа с минимальной суммой весов пройденных рёбер.

Интересно то, что для данной задачи не известно никакого полиномиального приближенного алгоритма, ошибающегося в C раз. Более того, доказано, что в предположении P != NP, такого алгоритма не существует. Доказательство этого простого факта и 2-приближенный алгоритм для метрического пространства можно найти в огромном количестве книг. К примеру, в книге Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ /Introduction to Algorithms.
Мы же остановимся на более интересном алгоритме. 3/2 приближенный алгоритм для задачи коммивояжёра в метрическом пространстве. Метрическое пространство в названии задачи означает, что для любых трёх вершин графа выполняется неравенство треугольника:
w(a, b) <= w(a, c) + w(c, b). Алгоритм начинается также, как в 2-приближении. Мы строим минимальное остовное дерево T исходного графа G. Выберем в T все вершины нечётной степени. На найденных вершинах нечётной степени построим минимальное полное паросочетание и добавим все полученные рёбра в дерево T. В пополненном рёбрами дереве мы можем найти эйлеров цикл (так как степени всех вершин уже стали чётными). Теперь просто удаляем из полученного цикла все повторения вершин и получаем ответ. Несложно показать, что полученный алгоритм является 3/2 приближением. Для этого достаточно показать, что вес минимального паросочетания вершин нечётной степени из T не превосходит половины оптимального ответа. Это лучший известный приближенный алгоритм задачи коммивояжёра в метрическом пространстве. 3) Покрытие множествами (Set Cover) Задача покрытия множествами является обобщением задачи о вершинном покрытии. Дано множество U. Задано B — множество подмножеств U. Необходимо выбрать минимальный набор множеств из B так, чтобы покрыть всё множество U. Приближенный алгоритм решения данной задачи является жадным алгоритмом. То есть на каждом шаге алгоритм выбирает «наиболее выгодное в данный момент» множество. То есть на каждом шаге алгоритм должен выбирать то множество, которое покроет наибольшее количество ещё не покрытых элементов множества U. Легко показать, что ошибка данного алгоритма O(log |U|). Также можно построить пример с логарифмической ошибкой. Доказана теорема, говорящая о том, что в предположении P != NP, значительно улучшить ошибку полиномиальным алгоритмом не удастся.